Топологический граф - 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 О (к ^ {4} п)}$, была основана Пахом и Терёчиком.^[8] Тот был улучшен до ${ Displaystyle О (к ^ {2} п)}$.^[9]Для количества ребер простых топологических графов без k непересекающиеся ребра, только ${ Displaystyle О (п журнал ^ {4k-8} п)}$ верхняя граница известна.^[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 п журнал ^ {О ( журнал к)} п}$.^[20]

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

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

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

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

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

Эти параметры не связаны между собой. Один имеет odd-cr (грамм) ≤ пара-cr (грамм) ≤ cr (грамм) для каждого графа грамм. Известно, что cr (грамм) ≤ 2 (нечет-кр (грамм))^2[23] и ${ Displaystyle О ( 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 О (п ^ {d})}$ симплексов, и эта оценка асимптотически точна.^[36] Этот результат был обобщен на наборы двумерных симплексов в ${ Displaystyle mathbb {R} ^ {2}}$ без трех сильно пересекающихся симплексов.^[37]Если мы запретим k сильно пересекающиеся симплексы, соответствующая наиболее известная верхняя оценка ${ Displaystyle О (п ^ {d + 1- delta})}$,^[36] для некоторых ${ Displaystyle дельта = дельта (к, d) <1}$. Этот результат следует из окрашенных Теорема Тверберга.^[38] Это далеко от предполагаемой границы ${ Displaystyle О (п ^ {d})}$.^[36]

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

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

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