Число пересечений (теория графов)

Наименьшее количество пересечений ребер при рисовании графа

Рисунок графа Хивуда с тремя пересечениями. Это минимальное количество пересечений среди всех рисунков этого графа, поэтому граф имеет число пересечений cr( G ) = 3 .

В теории графов число пересечений cr( G ) графа G — это наименьшее количество пересечений ребер плоского рисунка графа G. Например, граф является плоским тогда и только тогда, когда его число пересечений равно нулю. Определение числа пересечений по-прежнему имеет большое значение при рисовании графиков, поскольку исследования пользователей показали, что рисование графиков с небольшим количеством пересечений облегчает людям понимание рисунка. ^[1]

Исследование количества пересечений началось с проблемы Турана с кирпичным заводом , в которой Пал Туран попросил план завода, который минимизировал бы количество пересечений между путями, соединяющими кирпичные печи со складами. Математически эту задачу можно формализовать как поиск числа пересечений полного двудольного графа . ^[2] Такая же проблема возникла независимо в социологии примерно в то же время, в связи с построением социограмм . ^[3] Предполагаемая формула Турана для чисел пересечений полных двудольных графов остается недоказанной, как и аналогичная формула для полных графов .

Неравенство числа пересечений утверждает , что для графов , в которых число ребер e достаточно больше числа вершин n , число пересечений по крайней мере пропорционально e ³ / n ² . Он находит применение в проектировании СБИС и геометрии падения .

Без дополнительных уточнений число пересечений позволяет рисовать рисунки, на которых края могут быть представлены произвольными кривыми. Вариант этой концепции, число прямолинейных пересечений , требует, чтобы все ребра были сегментами прямых линий, и может отличаться от числа пересечений. В частности, число прямолинейных пересечений полного графа по существу совпадает с минимальным количеством выпуклых четырехугольников, определяемым набором из n точек общего положения. Проблема определения этого числа тесно связана с проблемой счастливого конца . ^[4]

Определения

Для определения числа пересечений рисунок неориентированного графа представляет собой отображение вершин графа на непересекающиеся точки на плоскости, а ребер графа на кривые, соединяющие две их конечные точки. Ни одна вершина не должна быть отображена на ребро, для которого она не является конечной точкой, и всякий раз, когда два ребра имеют пересекающиеся кривые (кроме общей конечной точки), их пересечения должны образовывать конечный набор правильных пересечений, где две кривые являются трансверсальными . Пересечение считается отдельно для каждой из этих точек пересечения, для каждой пары пересекающихся ребер. Тогда число пересечений графа будет минимальным среди всех таких рисунков из числа пересечений на рисунке. ^[5]

Некоторые авторы добавляют дополнительные ограничения к определению рисунка, например, что каждая пара ребер имеет не более одной точки пересечения (общая конечная точка или пересечение). Для числа пересечений, определенного выше, эти ограничения не имеют значения, поскольку рисунок с минимальным пересечением не может иметь ребра с несколькими точками пересечения. Если два ребра с общей конечной точкой пересекаются, рисунок можно изменить локально в точке пересечения, оставив остальную часть рисунка неизменной, чтобы создать другой рисунок с одним пересечением меньше. Аналогично, если два ребра пересекаются два или более раз, рисунок можно изменить локально в двух точках пересечения, чтобы создать другой рисунок с на два пересечения меньше. Однако эти ограничения актуальны для вариантов определений числа пересечений, которые, например, учитывают только количество пар пересекающихся ребер, а не количество пересечений. ^[5]

Особые случаи

По состоянию на апрель 2015 года числа пересечений известны для очень небольшого числа семейств графов. В частности, за исключением нескольких начальных случаев, число пересечений полных графов, двудольных полных графов и произведений циклов остается неизвестным, хотя в области нижних оценок наблюдается некоторый прогресс. ^[6]

Полные двудольные графы

Оптимальный рисунок K _4,7 , показывающий, что задача кирпичного завода Турана с 4 складами (желтые точки) и 7 печами (синие точки) требует 18 пересечений (красные точки).

Во время Второй мировой войны венгерский математик Пал Туран был вынужден работать на кирпичном заводе, перевозя вагоны с кирпичами из печей на склады. На заводе были пути от каждой печи к каждому складу, а вагоны было труднее толкать в тех местах, где пути пересекались друг с другом, из-за чего Турану пришлось задать вопрос своему кирпичному заводу: как печи, места хранения и пути могут быть организованы так, чтобы свести к минимуму общее количество пересечений? Математически печи и склады можно формализовать как вершины полного двудольного графа , а дорожки — как его ребра. Планировку завода можно представить в виде рисунка этого графа, поэтому возникает проблема: каково минимально возможное количество пересечений на рисунке полного двудольного графа ? ^[7]

Казимеж Заранкевич попытался решить проблему кирпичного завода Турана; ^[8] его доказательство содержало ошибку, но он установил верную верхнюю оценку

${\displaystyle {\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor }$

для числа пересечений полного двудольного графа K _m,n . Было высказано предположение, что эта граница представляет собой оптимальное количество пересечений для всех полных двудольных графов. ^[9]

Полные графики и раскраска графиков

Проблема определения числа пересечений полного графа была впервые поставлена ​​Энтони Хиллом и появилась в печати в 1960 году. ^[10] Хилл и его сотрудник Джон Эрнест были двумя художниками-конструкторами, увлеченными математикой. Они не только сформулировали эту проблему, но и вывели предположительное уравнение для этого числа пересечений, которое Ричард К. Гай опубликовал в 1960 году. ^[10] А именно, известно, что всегда существует рисунок с

${\displaystyle {\textrm {cr}}(K_{p})\leq {\frac {1}{4}}\left\lfloor {\frac {p}{2}}\right\rfloor \left\lfloor {\frac {p-1}{2}}\right\rfloor \left\lfloor {\frac {p-2}{2}}\right\rfloor \left\lfloor {\frac {p-3}{2}}\right\rfloor }$

переправы. Эта формула дает значения 1, 3, 9, 18, 36, 60, 100, 150 для p = 5,..., 12 ; см. последовательность A000241 в Электронной энциклопедии целочисленных последовательностей . Гипотеза состоит в том, что лучшего рисунка и быть не может, чтобы эта формула давала оптимальное количество пересечений для полных графов. Независимая формулировка той же гипотезы была сделана Томасом Л. Саати в 1964 году. ^[11]

Саати далее подтвердил, что эта формула дает оптимальное количество пересечений для p ≤ 10 , а Пан и Рихтер показали, что она также оптимальна для p = 11, 12 . ^[12]

Гипотеза Альбертсона , сформулированная Майклом О. Альбертсоном в 2007 году, утверждает, что среди всех графов с хроматическим числом n полный граф K _n имеет минимальное количество пересечений. То есть, если предполагаемая формула числа пересечений полного графа верна, то каждый n -хроматический граф имеет число пересечений, по крайней мере, равное той же формуле. Теперь известно, что гипотеза Альбертсона справедлива для n ≤ 16 . ^[13]

Кубические графы

Известны наименьшие кубические графы с номерами пересечений 1–8 и 11 (последовательность A110507 в OEIS ). Наименьший кубический граф с 1 пересечением — это полный двудольный граф K _3,3 с 6 вершинами. Самый маленький кубический граф с двумя пересечениями — это граф Петерсена с 10 вершинами. Самый маленький кубический граф с 3 пересечениями — это граф Хивуда с 14 вершинами. Самый маленький кубический граф с 4 пересечениями — это граф Мёбиуса-Кантора с 16 вершинами. Самый маленький кубический граф с 5 пересечениями — это граф Паппуса с 18 вершинами. Самый маленький кубический граф с 6 пересечениями — это граф Дезарга с 20 вершинами. Ни один из четырех кубических графов с 7 пересечениями и 22 вершинами не известен. ^[14] Наименьшие кубические графы с 8 пересечениями включают граф Науру и граф МакГи или граф (3,7) -клеток с 24 вершинами. ^[15] К самым маленьким кубическим графам с 11 пересечениями относится граф Коксетера с 28 вершинами. ^[16]

В 2009 году Пегг и Эксу предположили, что наименьший кубический граф с номером пересечения 13 — это граф Тутта-Коксетера , а самый маленький кубический граф с номером пересечения 170 — это 12-клетка Тутта . ^{[15] [17]}

Соединения с шириной пополам

Ширина простого графа, равная 2/3 деления пополам, — это минимальное количество ребер, удаление которых приводит к разделению набора вершин на два отдельных набора, так что ни в одном наборе не больше вершин. Вычисления NP-сложны. Лейтон доказал, что , при условии, что имеет ограниченные степени вершин. ^[18] Это фундаментальное неравенство можно использовать для получения асимптотической нижней границы для , когда , или его оценка известны. Кроме того, это неравенство имеет алгоритмическое применение. В частности, Бхат и Лейтон использовали его (впервые) для получения верхней границы количества пересечений ребер на рисунке, которая получается с помощью аппроксимационного алгоритма «разделяй и властвуй» для вычисления . ^[19] ${\displaystyle b(G)}$ ${\displaystyle G}$ ${\displaystyle 2n/3}$ ${\displaystyle b(G)}$ ${\displaystyle cr(G)+n=\Omega (b^{2}(G))}$ ${\displaystyle G}$ ${\displaystyle cr(G)}$ ${\displaystyle b(G)}$ ${\displaystyle cr(G)}$

Сложность и приближение

В общем, определить число пересечений графа сложно; Гэри и Джонсон показали в 1983 году, что это NP-сложная задача. ^[20] На самом деле проблема остается NP-трудной, даже если ограничиться кубическими графами ^[21] и почти плоскими графами (графами, которые становятся плоскими после удаления одного ребра). ^[22] Тесно связанная проблема, определение числа прямолинейных пересечений, является полной для экзистенциальной теории реальности . ^[23]

Положительным моментом является то, что существуют эффективные алгоритмы определения того, меньше ли число пересечений фиксированной константы k . Другими словами, проблема разрешима с фиксированными параметрами . ^{[24] [25]} Это остается трудным для больших k , таких как k = | В |/2 . Существуют также эффективные аппроксимационные алгоритмы для аппроксимации на графах ограниченной степени ^[26], которые используют общую и ранее разработанную структуру Бхата и Лейтона. ^[19] На практике используются эвристические алгоритмы, такие как простой алгоритм, который начинается без ребер и постоянно добавляет каждое новое ребро таким образом, чтобы произвести наименьшее количество возможных дополнительных пересечений. Эти алгоритмы используются в проекте распределенных вычислений Rectilinear Crossing Number . ^[27] ${\displaystyle cr(G)+n}$

Неравенство числа пересечений

Для неориентированного простого графа G с n вершинами и e ребрами, такими что e > 7 n, число пересечений всегда не менее

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}$

Эта связь между ребрами, вершинами и числом пересечений была открыта независимо Айтаи , Хваталом , Ньюборном и Семереди [ ^28] и Лейтоном. ^[18] Это известно как неравенство числа пересечений или лемма о пересечении.

Константа 29 на сегодняшний день является наиболее известной и принадлежит Акерману. ^[29] Константу 7 можно понизить до 4 , но за счет замены 29 худшей константой 64 . ^{[28] [18]}

Мотивацией Лейтона в изучении чисел пересечений было применение к проектированию СБИС в теоретической информатике. ^[18] Позже Секели также понял, что это неравенство дало очень простые доказательства некоторых важных теорем в геометрии инцидентности , таких как теорема Бека и теорема Семереди-Троттера , ^[30] и Тамал Дей использовал его для доказательства верхних границ геометрического k - наборы . ^[31]

Вариации

Если требуется, чтобы ребра отображались как отрезки прямых линий, а не как произвольные кривые, то в некоторых графах требуется больше пересечений. Число прямолинейных пересечений определяется как минимальное количество пересечений чертежа данного типа. Оно всегда не меньше числа пересечений, а для некоторых графов даже больше. Известно, что, вообще говоря, число прямолинейных пересечений не может быть ограничено функцией числа пересечений. ^[32] Номера прямолинейных пересечений для K ₅ через K ₁₂ составляют 1, 3, 9, 19, 36, 62, 102, 153 , (A014540), и известны значения до K _{27 , при этом для} K ₂₈ требуется либо 7233, либо 7234. переправы. Дополнительные значения собираются в рамках проекта «Число прямолинейных пересечений». ^[27]

Граф имеет локальное число пересечений k, если его можно нарисовать не более чем с k пересечениями на каждом ребре, но не меньше. Графы, которые можно нарисовать не более чем с k пересечениями на каждом ребре, также называются k -планарными. ^[33]

Другие варианты числа пересечений включают число попарных пересечений (минимальное количество пар ребер, которые пересекаются на любом рисунке) и нечетное число пересечений (количество пар ребер, которые пересекаются нечетное количество раз на любом рисунке). Нечетное число пересечений не более чем равно числу попарных пересечений, которое не более чем равно числу пересечений. Однако по теореме Ханани–Татте , когда одно из этих чисел равно нулю, все они равны нулю. ^[5] Шефер (2014, 2018) рассматривает множество таких вариантов. ^{[34] [35]}

Смотрите также

• Планаризация — плоский граф, образованный заменой каждого пересечения новой вершиной.
• Задача трех полезностей , головоломка, в которой спрашивается, можно ли нарисовать K _{3,3 с 0 пересечениями.}

Рекомендации

1. Покупка, Хелен С.; Коэн, Роберт Ф.; Джеймс, Мюррей И. (1995). «Проверка эстетики рисования графиков». В Бранденбурге, Франц-Иосиф (ред.). Рисование графов, Симпозиум по рисованию графов, GD '95, Пассау, Германия, 20-22 сентября 1995 г., Труды . Конспекты лекций по информатике. Том. 1027. Спрингер. стр. 435–446. дои : 10.1007/BFb0021827 ..
2. Туран, П. (1977). «Приветственное письмо». Журнал теории графов . 1 :7–9. дои : 10.1002/jgt.3190010105.
3. Бронфенбреннер, Ури (1944). «Графическое представление социометрических данных». Социометрия . 7 (3): 283–289. дои : 10.2307/2785096. JSTOR  2785096. Расположение предметов на диаграмме, хотя и частично случайное, определяется в основном методом проб и ошибок с целью минимизировать количество пересекающихся линий.
4. Шайнерман, Эдвард Р .; Уилф, Герберт С. (1994). «Прямолинейное число пересечений полного графа и «задача четырех точек» геометрической вероятности Сильвестра». Американский математический ежемесячник . 101 (10): 939–943. дои : 10.2307/2975158. JSTOR  2975158.
5. Пах, Дж .; Тот, Г. (1998). «И вообще, какой это номер перехода?». Материалы 39-го ежегодного симпозиума по основам информатики (FOCS 1998) . стр. 617–626. дои : 10.1109/SFCS.1998.743512..
6. де Клерк, Э.; Махарри, Дж.; Пасечник, Д.В.; Рихтер, Б.; Салазар, Г. (2006). «Улучшенные оценки чисел пересечения Km,n и Kn». SIAM Journal по дискретной математике . 20 (1): 189–202. arXiv : math/0404142 . дои : 10.1137/S0895480104442741. S2CID  1509054.
7. Пач, Янош ; Шарир, Миша (2009). «5.1 Переезды — проблема кирпичного завода». Комбинаторная геометрия и ее алгоритмические приложения: Лекции в Алькале . Математические обзоры и монографии. Том. 152. Американское математическое общество . стр. 126–127.
8. Заранкевич, К. (1954). «К проблеме П. Турана о графах». Фундамента Математика . 41 : 137–145. дои : 10.4064/fm-41-1-137-145 .
9. Гай, Ричард К. (1969). «Упадок и падение теоремы Заранкевича». Методы доказательства в теории графов (Труды Второй конференции по теории графов в Анн-Арборе, Анн-Арбор, Мичиган, 1968) . Академик Пресс, Нью-Йорк. стр. 63–69. МР  0253931..
10. Гай, РК (1960). «Комбинаторная задача». Набла (Бюллетень Малайского математического общества) . 7 : 68–72.
11. Саати, TL (1964). «Минимальное количество пересечений в полных графах». Труды Национальной академии наук Соединенных Штатов Америки . 52 (3): 688–690. Бибкод : 1964PNAS...52..688S. дои : 10.1073/pnas.52.3.688 . ПМК 300329 . ПМИД  16591215. 
12. Пан, Шэнцзюнь; Рихтер, Р. Брюс (2007). «Номер пересечения К ₁₁ равен 100 ». Журнал теории графов . 56 (2): 128–134. дои : 10.1002/jgt.20249. MR  2350621. S2CID  37155969..
13. Барат, Янош; Тот, Геза (2009). «К гипотезе Альбертсона». arXiv : 0909.0413 [math.CO].
14. Вайсштейн, Эрик В. «Число пересечения графика». Математический мир .
15. Пегг, ET ; Эксу, Г. (2009). «Пересечение графов чисел». Журнал Математика . 11 (2). дои : 10.3888/tmj.11.2-2 .
16. Клэнси, Киран; Хейторп, Майкл; Ньюкомб, Алекс; Пегг, Эд младший (2020). «Не существует кубических графов на 26 вершин с номером пересечения 10 или 11». Графы и комбинаторика . 36 (6): 1713–1721. arXiv : 1804.10336 . дои : 10.1007/s00373-020-02204-6. MR  4163409. S2CID  253889498.
17. Эксу, Г. «Прямолинейные рисунки известных графов».
18. Лейтон, Т. (1983). Проблемы сложности в СБИС . Основы вычислительной техники. Серия. Кембридж, Массачусетс: MIT Press.
19. Бхатт, Сандип Н.; Лейтон, Фрэнк Томсон (1 апреля 1984 г.). «Среда для решения проблем компоновки графов СБИС». Журнал компьютерных и системных наук . 28 (2): 300–343. дои : 10.1016/0022-0000(84)90071-0. ISSN  0022-0000.
20. Гэри, MR ; Джонсон, DS (1983). «Номер пересечения NP-полный». SIAM Journal по алгебраическим и дискретным методам . 4 (3): 312–316. дои : 10.1137/0604033. МР  0711340.
21. Хлинены, П. (2006). «Число пересечения сложно для кубических графов». Журнал комбинаторной теории . Серия Б. 96 (4): 455–471. дои : 10.1016/j.jctb.2005.09.009 . МР  2232384.
22. Кабельо С. и Мохар Б. (2013). «Добавление одного ребра к планарным графам затрудняет число пересечений и 1-планарность». SIAM Journal по вычислительной технике . 42 (5): 1803–1829. arXiv : 1203.5944 . дои : 10.1137/120872310. S2CID  6535755.
23. Шефер, Маркус (2010). Сложность некоторых геометрических и топологических задач (PDF) . Рисование графиков, 17-й Международный симпозиум, GS 2009, Чикаго, Иллинойс, США, сентябрь 2009 г., Пересмотренные статьи . Конспекты лекций по информатике. Том. 5849. Шпрингер-Верлаг. стр. 334–344. дои : 10.1007/978-3-642-11805-0_32 . ISBN 978-3-642-11804-3..
24. Гроэ, М. (2005). «Вычисление чисел пересечений за квадратичное время». Журнал компьютерных и системных наук . 68 (2): 285–302. arXiv : cs/0009010 . дои : 10.1016/j.jcss.2003.07.008. МР  2059096.
25. Каварабаяси, Кен-ичи ; Рид, Брюс (2007). Вычисление числа пересечений за линейное время . Материалы 29-го ежегодного симпозиума ACM по теории вычислений . стр. 382–390. дои : 10.1145/1250790.1250848. ISBN 978-1-59593-631-8.
26. Даже, Гай; Гуха, Судипто; Шибер, Барух (2003). «Улучшенная аппроксимация пересечений в графических рисунках и областях макета СБИС». SIAM Journal по вычислительной технике . 32 (1): 231–252. дои : 10.1137/S0097539700373520.
27. Освин Айххольцер. «Проект «Прямолинейный перекресток». Архивировано из оригинала 30 декабря 2012 г.и прямолинейное число пересечений в Институте программных технологий Граца, Технологический университет (2009).
28. Аджтай, М .; Хватал, В. ; Ньюборн, М.; Семереди, Э. (1982). Беспересекающиеся подграфы . Теория и практика комбинаторики. Математические исследования Северной Голландии. Том. 60. стр. 9–12. МР  0806962.
29. Акерман, Эяль (2013). «О топологических графах с не более чем четырьмя пересечениями на ребро» (PDF) . Архивировано из оригинала (PDF) 14 июля 2014 г.
30. Секели, Луизиана (1997). «Числа пересечения и сложные задачи Эрдеша в дискретной геометрии». Комбинаторика, теория вероятностей и вычисления . 6 (3): 353–358. дои : 10.1017/S0963548397002976. MR  1464571. S2CID  36602807.
31. Дей, ТК (1998). «Улучшенные оценки для плоских k-множеств и связанных с ними проблем». Дискретная и вычислительная геометрия . 19 (3): 373–382. дои : 10.1007/PL00009354 . МР  1608878.
32. Бьенсток, Дэниел; Дин, Натаниэль (июль 1993 г.). «Границы для прямолинейных чисел пересечений». Журнал теории графов . 17 (3): 333–348. дои : 10.1002/jgt.3190170308.
33. Рингель, Герхард (1965). «Ein Sechsfarbenproblem auf der Kugel». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (на немецком языке). 29 (1–2): 107–117. дои : 10.1007/BF02996313. MR  0187232. S2CID  123286264.
34. Шефер, Маркус (2014). «Число пересечений графа и его варианты: обзор». Электронный журнал комбинаторики . ДС21.
35. Шефер, Маркус (2018). Числа пересечений графов . ЦРК Пресс.