Топологический граф - Topological graph

Эта статья о графах, вложенных в плоскость, с пересечениями. О вложениях графов на другие поверхности см. топологическая теория графов.

График с нечетным числом 13 и парным числом 15.^[1]

В математика, а топологический граф является представлением график в самолет, где вершины графика представлены различными точками и края к Иорданские дуги (соединенные части Кривые Иордании ), соединяющие соответствующие пары точек. Точки, представляющие вершины графа, и дуги, представляющие его ребра, называются вершины и края топологического графа. Обычно предполагается, что любые два ребра топологического графа пересекаются конечное число раз, никакое ребро не проходит через вершину, отличную от его концов, и никакие два ребра не касаются друг друга (без пересечения). Топологический граф также называется Рисование графа.

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

Теория топологических графов - это область теория графов, в основном касается комбинаторный свойства топологических графов, в частности, со схемами пересечения их ребер. Это тесно связано с рисунок графика, область, более ориентированная на приложения, и топологическая теория графов, который ориентирован на встраивание графов в поверхности (то есть рисунки без пересечений).

Экстремальные задачи для топологических графов

Основная проблема в экстремальная теория графов следующий: каково максимальное количество ребер, которое граф п вершин может иметь, если он не содержит подграфа, принадлежащего данному классу запрещенные подграфы? Прототипом таких результатов является Теорема Турана, где есть один запрещенный подграф: полный граф с k вершины (k фиксированный). Аналогичные вопросы могут быть подняты для топологических и геометрических графов с той разницей, что теперь геометрические подконфигурации запрещены.

Исторически первый пример такой теоремы связан с Пол Эрдёш, который продлил результат Хайнц Хопф и Эрика Паннвиц.^[2] Он доказал, что максимальное количество ребер геометрического графа с п > 2 вершины могут иметь, не содержащие два непересекающихся ребра (который даже не может совместно использовать конечную точку) п. Джон Конвей предположил, что это утверждение можно обобщить на простые топологические графы. Топологический граф называется "простым", если любая пара его ребер имеет не более одной точки, которая является либо конечной точкой, либо общей внутренней точкой, в которой два ребра должным образом пересекаются. Конвея бить Теперь гипотезу можно переформулировать следующим образом: простой топологический граф с п > 2 вершин и никакие два непересекающихся ребра не имеют не более п края.

Первая линейная верхняя оценка числа ребер такого графа была установлена Ловас и другие..^[3]Самая известная верхняя граница 1,428п, было доказано Фулеком и Пах.^[4] Помимо геометрических графов, гипотеза Тракла, как известно, верна для Икс-монотонные топологические графы.^[5] Топологический граф называется x-монотонный если каждая вертикальная линия пересекает каждое ребро не более чем в одной точке.

Алон и Erds^[6] инициировал исследование обобщения поставленного вопроса на случай, когда запрещенная конфигурация состоит из k непересекающиеся ребра (k > 2). Они доказали, что количество ребер геометрического графа пвершин, не содержащих 3 непересекающихся ребра, О(п). Оптимальная оценка примерно 2,5п был определен Черным.^[7]Для больших значений k, первая линейная верхняя граница, ${\displaystyle O(k^{4}n)}$, была основана Пахом и Терёчиком.^[8] Тот был улучшен до ${\displaystyle O(k^{2}n)}$.^[9]Для количества ребер простых топологических графов без k непересекающиеся ребра, только ${\displaystyle O(n\log ^{4k-8}n)}$ верхняя граница известна.^[10] Отсюда следует, что каждый полный простой топологический граф с п вершин не менее ${\displaystyle c{\frac {\log n}{\log \log n}}}$ попарно пересекающиеся ребра, который был улучшен до ${\displaystyle cn^{{\frac {1}{2}}-\epsilon }}$ пользователя Ruiz-Vargas.^[11] Возможно, эту нижнюю границу можно улучшить до сп, куда c > 0 - постоянная величина.

Квазиплоские графы

Общая внутренняя точка двух ребер, в которой первое ребро переходит от одной стороны второго ребра к другому, называется точкой. пересечение. Два ребра топологического графа Пересекать друг друга, если они определяют пересечение. Для любого целого числа k > 1 топологический или геометрический граф называется k-квазипланарный если у него нет k попарно пересекающиеся ребра. Используя эту терминологию, если топологический граф является 2-квазипланарным, то это планарный граф.Это следует из Формула полиэдра Эйлера что каждый плоский граф с п > 2 вершин не более 3п - 6 граней. Следовательно, любой 2-квазипланарный граф с п > 2 вершин не более 3п - 6 граней.

Это было предположено Пахом и др.^[12] что каждый k-квазиплоский топологический граф с п вершин не более c(k)пкрая, где c(k) - константа, зависящая только от k. Как известно, эта гипотеза верна для k = 3^[13][14] и k = 4.^[15] Также известно, что это верно для выпуклые геометрические графы (то есть для геометрических графов, вершины которых образуют множество вершин выпуклой п-угольник),^[16] и для k-квазиплоские топологические графы, ребра которых нарисованы как Икс-монотонные кривые, пересекающие вертикальную линию.^[17][18]Последний результат означает, что каждый k-квазиплоский топологический граф с п вершины, ребра которых нарисованы как Икс-монотонные кривые имеют не более c(k)п бревноп края для подходящей постоянной c(k). Для геометрических графов это ранее было доказано Валтром.^[19] Самый известный генерал верхняя граница для количества ребер k-квазиплоский топологический граф ${\displaystyle n\log ^{O(\log k)}n}$.^[20]

Пересекающиеся числа

С тех пор Пал Туран выдуманный его проблема кирпичного завода^[21] в течение Вторая Мировая Война, определение или оценка числа пересечений графов было популярной темой в теории графов и теории алгоритмов.^[22] Однако в публикациях по теме (явно или неявно) использовалось несколько конкурирующих определений чисел скрещивания. На это указали Пах и Тот,^[23] который ввел следующую терминологию.

Номер перехода (графа грамм): Минимальное количество точек пересечения на всех чертежах грамм на плоскости (то есть все его представления в виде топологического графа) с тем свойством, что никакие три ребра не проходят через одну и ту же точку. Обозначается cr (грамм).

Номер парного скрещивания: Минимальное количество пар пересекающихся ребер на всех чертежах грамм. Обозначается парой-cr (грамм).

Нечетное число пересечения: Минимальное количество тех пар ребер, которые пересекаются нечетное количество раз на всех чертежах грамм. Обозначается odd-cr (грамм).

Эти параметры не связаны между собой. Один имеет odd-cr (грамм) ≤ пара-cr (грамм) ≤ cr (грамм) для каждого графа грамм. Известно, что cr (грамм) ≤ 2 (нечет-кр (грамм))^2[23] и ${\displaystyle O(\operatorname {pcr} (G)^{\frac {3}{2}}\log ^{2}\operatorname {pcr} (G))}$^[24]и что существует бесконечно много графов, для которых pair-cr (грамм) ≠ odd-cr (грамм).^[1] Не известны примеры, для которых номер скрещивания и номер парного скрещивания не совпадали. Это следует из Теорема Ханани – Тутте^[25][26] что нечетный-кр (грамм) = 0 влечет cr (грамм) = 0. Также известно, что odd-cr (грамм) = k подразумевает cr (G) = k за k = 1, 2, 3.^[27]Еще один хорошо изученный параметр графика заключается в следующем.

Номер прямолинейного пересечения: Минимальное количество точек пересечения на всех прямолинейных чертежах грамм на плоскости (то есть все его представления в виде геометрического графа) с тем свойством, что никакие три ребра не проходят через одну и ту же точку. Обозначается lin-cr (грамм).

По определению cr (грамм) ≤ lin-cr (грамм) для каждого графа грамм. Бинсток и Дин показали, что существуют графы с числом пересечения 4 и с произвольно большим числом прямолинейных пересечений.^[28]

Задачи типа Рамсея для геометрических графов

В традиционных теория графов, типичный Результат типа Рамсея утверждает, что если мы раскрасим ребра достаточно большого полного графа в фиксированное количество цветов, то мы обязательно найдем монохромный подграф определенного типа.^[29] Аналогичные вопросы можно поднять и для геометрических (или топологических) графов, за исключением того, что теперь мы ищем монохроматические (одноцветные) подструктуры, удовлетворяющие определенным геометрическим условиям.^[30]Один из первых результатов такого рода утверждает, что каждый полный геометрический граф, ребра которого раскрашены в два цвета, содержит непересекающийся монохроматический граф. остовное дерево.^[31] Также верно, что каждый такой геометрический граф содержит ${\displaystyle \left\lceil {\frac {n+1}{3}}\right\rceil }$ непересекающиеся края одного цвета.^[31] Существование непересекающегося монохроматического пути размером не менее сп, куда c > 0 - постоянная, давняя открытая проблема. Известно лишь, что каждый полный геометрический граф на п вершины содержат непересекающийся монохроматический путь длиной не менее ${\displaystyle n^{\frac {2}{3}}}$.^[32]

Топологические гиперграфы

Если мы рассматриваем топологический граф как топологическую реализацию одномерного симплициальный комплекс, естественно спросить, как обобщаются указанные выше экстремальные задачи и задачи типа Рамсея на топологические реализации d-мерные симплициальные комплексы. В этом направлении есть первые результаты, но для определения ключевых понятий и проблем необходимы дальнейшие исследования.^[33][34][35]

Два непересекающихся симплекса вершин называются Пересекать если в их относительном внутреннем мире есть что-то общее. Набор k > 3 симплекса сильно пересекать если никакие 2 из них не имеют общей вершины, но их относительные внутренности имеют общую точку.

Известно, что набор d-мерные симплексы, натянутые на п указывает в ${\displaystyle \mathbb {R} ^{d}}$ без пары пересекающихся симплексов может иметь не более ${\displaystyle O(n^{d})}$ симплексов, и эта оценка асимптотически точна.^[36] Этот результат был обобщен на наборы двумерных симплексов в ${\displaystyle \mathbb {R} ^{2}}$ без трех сильно пересекающихся симплексов.^[37]Если мы запретим k сильно пересекающиеся симплексы, соответствующая наиболее известная верхняя оценка ${\displaystyle O(n^{d+1-\delta })}$,^[36] для некоторых ${\displaystyle \delta =\delta (k,d)<1}$. Этот результат следует из окрашенных Теорема Тверберга.^[38] Это далеко от предполагаемой границы ${\displaystyle O(n^{d})}$.^[36]

Для любых фиксированных k > 1, мы можем выбрать не более ${\displaystyle O(n^{\lceil {\frac {d}{2}}\rceil })}$ d-мерные симплексы, натянутые на набор п указывает в ${\displaystyle \mathbb {R} ^{d}}$ со свойством, что нет k из них имеют общую внутреннюю точку.^[36][39] Это асимптотически жестко.

Два треугольника в ${\displaystyle \mathbb {R} ^{3}}$ как говорят почти непересекающийся если они не пересекаются или имеют только одну вершину. Это старая проблема Гил Калаи и другие, чтобы решить, можно ли выбрать наибольшее количество почти непересекающихся треугольников на некотором множестве вершин п указывает в ${\displaystyle \mathbb {R} ^{3}}$ является ${\displaystyle o(n^{2})}$. Известно, что существуют наборы п точек, для которых это число не менее ${\displaystyle cn^{\frac {2}{3}}}$ для подходящей постоянной c > 0.^[40]

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

1. Пельсмайер, Майкл Дж .; Шефер, Маркус; Штефанкович, Даниэль (2008), «Нечетный номер перекрестка и номер перекрестка не совпадают», Дискретная и вычислительная геометрия, 39 (1–3): 442–454, Дои:10.1007 / s00454-008-9058-х Предварительная версия этих результатов была рассмотрена в Proc. 13-го Международного симпозиума по графическому рисованию, 2005, стр. 386–396, Дои:10.1007/11618058_35.
2. Хопф, Хайнц; Паннвиц, Эрика (1934), "Aufgabe nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung, 43: 114
3. Ловас, Ласло; Пах, Янош; Сегеди, Марио (1997), «О догадке Конвея», Дискретная и вычислительная геометрия, Спрингер, 18 (4): 369–376, Дои:10.1007 / PL00009322
4. Фулек, Радослав; Пах, Янош (2011), "Вычислительный подход к гипотезе Тракла Конвея", Вычислительная геометрия, 44 (6–7): 345–355, arXiv:1002.3904, Дои:10.1007/978-3-642-18469-7_21, МИСТЕР  2785903
5. Пах, Янош; Стерлинг, Итан (2011), «Гипотеза Конвея для монотонных треков», Американский математический ежемесячный журнал, 118 (6): 544–548, Дои:10.4169 / amer.math.monthly.118.06.544, МИСТЕР  2812285, S2CID  17558559
6. Алон, Нога; Эрдеш, Пол (1989), «Непересекающиеся ребра в геометрических графах», Дискретная и вычислительная геометрия, 4 (4): 287–290, Дои:10.1007 / bf02187731
7. Черны, Якуб (2005), "Геометрические графы без трех непересекающихся ребер", Дискретная и вычислительная геометрия, 34 (4): 679–695, Дои:10.1007 / s00454-005-1191-1
8. Пах, Янош; Töröcsik, Jenö (1994), "Некоторые геометрические приложения теоремы Дилворта", Дискретная и вычислительная геометрия, 12: 1–7, Дои:10.1007 / BF02574361
9. Тот, Геза (2000), «Заметка о геометрических графах», Журнал комбинаторной теории, Серия А, 89 (1): 126–132, Дои:10.1006 / jcta.1999.3001
10. Пах, Янош; Тот, Геза (2003), "Непересекающиеся ребра в топологических графах", Комбинаторная геометрия и теория графов: Совместная конференция Индонезии и Японии, IJCCGGT 2003, Бандунг, Индонезия, 13-16 сентября 2003 г., Пересмотренные избранные статьи (PDF), Конспект лекций по информатике, 3330, Springer-Verlag, стр. 133–140, Дои:10.1007/978-3-540-30540-8_15
11. Дж. Руис-Варгас, Андрес (2015), Множество непересекающихся ребер в топологических графах, 50, стр. 29–34, arXiv:1412.3833, Дои:10.1016 / j.endm.2015.07.006
12. Пах, Янош; Шахрохи, Фархад; Сегеди, Марио (1996), «Применения номера пересечения», Алгоритмика, Спрингер, 16 (1): 111–117, Дои:10.1007 / BF02086610, S2CID  20375896
13. Агарвал К., Панкай; Аронов Борис; Пах, Янош; Поллак, Ричард; Шарир, Миха (1997), "Квазиплоские графы имеют линейное число ребер", Комбинаторика, 17: 1–9, Дои:10.1007 / bf01196127, S2CID  8092013
14. Акерман, Эяль; Тардос, Габор (2007), «О максимальном количестве ребер в квазиплоских графах», Журнал комбинаторной теории, Серия А, 114 (3): 563–571, Дои:10.1016 / j.jcta.2006.08.002
15. Акерман, Эйал (2009), "О максимальном количестве ребер в топологических графах без четырех попарно пересекающихся ребер", Дискретная и вычислительная геометрия, 41 (3): 365–375, Дои:10.1007 / s00454-009-9143-9
16. Capoyleas, Vasilis; Пах, Янош (1992), "Теорема типа Турана о хордах выпуклого многоугольника", Журнал комбинаторной теории, Серия B, 56 (1): 9–15, Дои:10.1016 / 0095-8956 (92) 90003-Г
17. Сук, Андрей (2011) "k-квазиплоские графы », Графический рисунок: 19-й Международный симпозиум, GD 2011, Эйндховен, Нидерланды, 21-23 сентября 2011 г., отредактированные избранные статьи, Конспект лекций по информатике, 7034, Springer-Verlag, стр. 266–277, arXiv:1106.0958, Дои:10.1007/978-3-642-25878-7_26, S2CID  18681576
18. Фокс, Джейкоб; Пах, Янош; Сук, Андрей (2013), «Количество ребер в k-квазиплоские графы », Журнал SIAM по дискретной математике, 27 (1): 550–561, arXiv:1112.2361, Дои:10.1137/110858586, S2CID  52317.
19. Валтр, Павел (1997), «Рисование графика без k попарно пересекающиеся ребра », Графический рисунок: 5-й Международный симпозиум, GD '97, Рим, Италия, 18–20 сентября 1997 г., Труды, Конспект лекций по информатике, 1353, Springer-Verlag, стр. 205–218.
20. Фокс, Джейкоб; Пах, Янош (2012), «Раскраска ${\displaystyle K_{\mbox{k}}}$-свободные графики пересечений геометрических объектов на плоскости », Европейский журнал комбинаторики, 33 (5): 853–866, Дои:10.1016 / j.ejc.2011.09.021 Предварительная версия этих результатов была объявлена ​​в Proc. симпозиума по вычислительной геометрии (PDF), 2008, стр. 346–354, Дои:10.1145/1377676.1377735, S2CID  15138458
21. Туран, Пол (1977), «Приветственное слово», Журнал теории графов, 1: 7–9, Дои:10.1002 / jgt.3190010105
22. Гарей, М.; Джонсон, Д.С. (1983), «Число пересечений NP-полное», Журнал SIAM по алгебраическим и дискретным методам, 4 (3): 312–316, Дои:10.1137/0604033, МИСТЕР  0711340
23. Пах, Янош; Тот, Геза (2000), «Какой это номер пересечения?», Журнал комбинаторной теории, Серия B, 80 (2): 225–246, Дои:10.1006 / jctb.2000.1978
24. Матушек, Иржи (2014), «Почти оптимальные разделители в строковых графах», Комбинировать. Вероятно. Comput., 23, стр. 135–139, arXiv:1302.6482, Дои:10.1017 / S0963548313000400, S2CID  2351522
25. Хойнацкий (Ханани), Хаим (Хаим) (1934), "Uber wesentlich unplattbar Kurven im dreidimensionale Raume", Fundamenta Mathematicae, 23: 135–142, Дои:10.4064 / FM-23-1-135-142
26. Тутте, Уильям Т. (1970), "К теории чисел пересечения", Журнал комбинаторной теории, 8: 45–53, Дои:10.1016 / с0021-9800 (70) 80007-2
27. Пельсмайер, Майкл Дж .; Шефер, Маркус; Штефанкович, Даниэль (2007), «Удаление четных переходов», Журнал комбинаторной теории, Серия B, 97 (4): 489–500, Дои:10.1016 / j.jctb.2006.08.001
28. Бинсток, Дэниел; Дин, Натаниэль (1993), "Границы для числа прямолинейных пересечений", Журнал теории графов, 17 (3): 333–348, Дои:10.1002 / jgt.3190170308
29. Грэм, Рональд Л .; Ротшильд, Брюс Л .; Спенсер, Джоэл Х. (1990), Теория Рэмси, Wiley
30. Каройи, Дьюла (2013), «Задачи типа Рамсея для геометрических графов», в Пах, Дж. (ред.), Тридцать очерков по геометрической теории графов, Springer
31. Károlyi, Gyula J .; Пах, Янош; Тот, Геза (1997), "Результаты типа Рамсея для геометрических графов, I", Дискретная и вычислительная геометрия, 18 (3): 247–255, Дои:10.1007 / PL00009317
32. Károlyi, Gyula J .; Пах, Янош; Тот, Геза; Валтр, Павел (1998), "Результаты типа Рамсея для геометрических графов, II", Дискретная и вычислительная геометрия, 20 (3): 375–388, Дои:10.1007 / PL00009391
33. Пах, Янош (2004), «Геометрическая теория графов», в Гудман, Джейкоб Э.; О'Рурк, Джозеф (ред.), Справочник по дискретной и вычислительной геометрии, Дискретная математика и ее приложения (2-е изд.), Chapman and Hall / CRC
34. Матушек, Иржи; Тансер, Мартин; Вагнер, Ули (2009), Трудность вложения симплициальных комплексов в ${\displaystyle \mathbb {R} ^{d}}$, стр. 855–864
35. Брасс, Питер (2004), "Задачи типа Турана для выпуклых геометрических гиперграфов", в Пах, Дж. (ред.), К теории геометрических графов, Современная математика, Американское математическое общество, стр. 25–33.
36. Дей, Тамал К.; Пах, Янош (1998), "Экстремальные задачи для геометрических гиперграфов", Дискретная и вычислительная геометрия, 19 (4): 473–484, Дои:10.1007 / PL00009365
37. Сук, Андрей (2013), "Заметка о геометрических 3-гиперграфах", в Пах, Дж. (ред.), Тридцать очерков по теории геометрических графов, Springer arXiv: 1010.5716v3
38. Живальевич, Раде Т .; Вречица, Синиша Т. (1992), "Цветная проблема Тверберга и комплексы инъективных функций", Журнал комбинаторной теории, Серия А, 61 (2): 309–318, Дои:10.1016 / 0097-3165 (92) 90028-С
39. Барань, Имре; Фюреди, Золтан (1987), "Пустые симплексы в евклидовом пространстве", Канадский математический бюллетень, 30 (4): 436–445, Дои:10.4153 / cmb-1987-064-1, HDL:1813/8573
40. Каройи, Дьюла; Солимоши, Йожеф (2002), "Почти непересекающиеся треугольники в трехмерном пространстве", Дискретная и вычислительная геометрия, 28 (4): 577–583, Дои:10.1007 / s00454-002-2888-z