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

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

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

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

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

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

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

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

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

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

Квазиплоские графы [ править ]

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

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

Номера переходов [ править ]

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

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

Число пар пересечения : Минимальное число пересечения пары ребер по всем чертежам G . Обозначается парой-cr ( G ).

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

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

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

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

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

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

Топологические гиперграфы [ править ]

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

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

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

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

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

Ссылки [ править ]