Число пересечений графов
«Числа пересечений графов» — это книга по математике, посвященная минимальному количеству пересечений ребер, необходимому для графических рисунков . Он был написан Маркусом Шефером, профессором информатики в Университете ДеПола , и опубликован в 2018 году издательством CRC Press в серии книг «Дискретная математика и ее приложения».
Темы
[ редактировать ]Основной текст книги состоит из двух частей: о номере пересечения в его традиционном определении и о вариациях числа пересечений, за которыми следуют два приложения. [1] предоставление справочного материала по топологической теории графов и теории сложности вычислений . [2]
После введения проблемы в первой главе изучаются числа пересечений полных графов (включая предполагаемую формулу Хилла для этих чисел) и полных двудольных графов ( задача кирпичного завода Турана и гипотеза числа пересечений Заранкевича), снова давая предполагаемую формулу). [2] [3] Он также включает неравенство числа пересечений и теорему Ханани – Тутте о четности пересечений. [1] Вторая глава посвящена другим специальным классам графов, включая произведения графов (особенно произведения графов циклов ) и графы гиперкубов . [2] [3] После третьей главы, связывающей число пересечений с параметрами графа, включая асимметрию , ширину пополам , толщину и (через гипотезу Альбертсона ) хроматическое число , последняя глава части I посвящена вычислительной сложности поиска рисунков графов с минимальным пересечением, включая Результаты показывают, что проблема является одновременно NP-полной и разрешимой с фиксированными параметрами . [1] [2] [3]
Во второй части книги две главы посвящены прямолинейному числу пересечений, описывая рисунки графов, в которых ребра должны быть представлены в виде отрезков прямых, а не произвольных кривых, и теорему Фари о том, что каждый плоский граф можно нарисовать таким образом без пересечений. . Другая глава посвящена 1-планарным графам и соответствующему локальному числу пересечений, наименьшему числу k, при котором граф можно нарисовать не более чем с k пересечениями на одно ребро. Две главы посвящены вложениям книг и строковым графам , а еще две главы посвящены вариациям числа пересечений, которые подсчитывают пересечения по-разному, например, по количеству пар ребер, которые пересекаются или пересекаются нечетное количество раз. Последняя глава части II посвящена траклам и проблеме нахождения рисунков с максимальным числом пересечений. [2] [3]
Аудитория и прием
[ редактировать ]Книгу можно использовать в качестве учебника для продвинутых пользователей, и для этого в ней предусмотрены упражнения. [2] [3] Однако предполагается, что его читатели уже знакомы как с теорией графов , так и с разработкой и анализом алгоритмов . [2] Рецензируя книгу, Л. В. Бейнеке называет ее «ценным вкладом» в представление многочисленных результатов в этой области.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Ву, Баойиндуренг, «Обзор чисел пересечений графов », zbMATH , Zbl 1388.05005
- ^ Перейти обратно: а б с д и ж г Дэйв, Маулик А. (март 2020 г.), «Обзор чисел пересечений графов » , MAA Reviews , Математическая ассоциация Америки
- ^ Перейти обратно: а б с д и Бейнеке, Лоуэлл (апрель 2019 г.), «Обзор чисел пересечений графов », American Mathematical Monthly , 126 (4): 379–384, doi : 10.1080/00029890.2019.1567230