В теории графов число пересечений графа — это наименьшее число пересечений рёбер плоского рисунка графа . Например, граф является планарным тогда и только тогда, когда его число пересечений равно нулю.
Математической отправной точкой изучения числа пересечений стала задача Турана о кирпичной фабрике, поставленная Палом Тураном, в которой требовалось найти число пересечений полного двудольного графа . Однако та же самая задача поставлена в социологии примерно в то же самое время в связи с построением социограмм. Задача продолжает играть большую роль в визуализации графов.
Если не указано другое, число пересечений относится к представлениям графов с помощью любых кривых. Условие прямолинейных пересечений требует, чтобы все рёбра были отрезками прямых, что может изменить ответ. В частности, число прямолинейных пересечений полного графа равно минимальному числу выпуклых четырёхугольников, определённых множеством точек в общем положении, что тесно связано с задачей со счастливым концом.
История Во время Второй мировой войны венгерский математик Пал Туран вынужден работать на кирпичной фабрике, толкая тележку, гружёную кирпичами, от обжиговых печей в склады. На фабрике имелись колеи от каждой печи до каждого склада, и тележку труднее толкать в местах пересечения колей, что привело Турана к постановке задачи кирпичной фабрики: каково минимальное число пересечений рисунка полного графа?.
Заранкиевич (Zarankiewicz) пытался решить задачу Турана. Его доказательство содержало ошибку, но он установил правильную верхнюю границу
для числа пересечений полного двудольного графа . Гипотеза, что это неравенство на самом деле является равенством, известна как гипотеза Заранкиевича. Нижняя граница открыта лишь одиннадцать лет спустя после публикации почти одновременно Герхардом Рингелем и Полем Кайненом (Paul Chester Kainen).
Задача определения числа пересечений полного графа поставлена впервые Энтони Хиллом и появилась в печати в 1960. Хилл и его соавтор Джон Эрнест были двумя художниками-конструктивистами, очарованными математикой, и они не только сформулировали задачу, но и высказали для таких графов гипотезу о верхней границе числа пересечений, которую Ричард К. Гай опубликовал в 1960 году. А именно что эта граница равна
что даёт значения для (). Независимую формулировку гипотезы дал Томас Л. Саати в 1964 году. Саати позднее выяснил, что верхняя граница достигается для , а Пэн и Рихтер (Pan, Richter) показали, что она достигается и для
Если разрешены только прямолинейные дуги, требуется большее число пересечений. Число прямолинейных пересечений для графов — равно (). Значения для графов вплоть до известны. Для нужно либо 7233, либо 7234 пересечений. Дальнейшие значения собираются в проекте «Число прямолинейных пересечений». Интересно, что неизвестно, являются ли обычное и прямолинейное число пересечений тем же самым для полных двудольных графов. Если гипотеза Заранкиевича верна, то формула для числа пересечений полного графа асимптотически верна, то есть,
К апрелю 2015 число пересечений известно для совсем небольшого числа семейств графов. В частности, за исключением нескольких начальных случаев, число пересечений полных графов, полных двудольных графов и произведения циклов остаются неизвестными. Был некоторый успех для нижней границы, согласно сообщению де Клерка, Махарри, Пасечника и Рихтера (de Klerk, Maharry, Pasechnik, Richter). Большой обзор различных вариантов приведен Шафером (Schaefer) .
Гипотеза Албертсона, сформулированная Михаэлем Альбертсоном (Michael O. Albertson) в 2007 году, утверждает, что среди всех графов с хроматическим числом полный граф имеет минимальное число пересечений. То есть, если гипотеза Гая — Саати о числе пересечения полного графа верна, любой -хроматический граф имеет число пересечений как минимум равное формуле в гипотезе. Известно, что это выполняется для .
Сложность В общем случае определение числа пересечений графа является сложной задачей. Гарей и Джонсон (Michael Garey, David S. Johnson) в 1983 году показали, что задача эта является NP-трудной. Фактически, задача остаётся NP-трудной даже при сужении её на кубические графы и почти планарные графы (графы, которые становятся планарными после удаления одного ребра). В частности, определение числа прямолинейных пересечений является для экзистенциальной теории вещественных чисел.
Однако существуют эффективные алгоритмы определения, что число пересечений не превосходит фиксированной константы . Другими словами, задача является . Она остаётся сложной для больших k, таких как |V|/2. Существуют также эффективные аппроксимационные алгоритмы для оценки на графах с ограниченной степенью. На практике используются эвристистические алгоритмы, такие как простой алгоритм, начинающий с графа без рёбер и постепенно добавляющий рёбра так, чтобы получить минимально возможное добавочное число пересечений. Этот алгоритм используется в программе проекта распределённых вычислений «Число прямолинейных пересечений»Rectilinear Crossing Number , Институт Программных технологий Граца, Технологический университет (2009)..
Число пересечений кубических графов Наименьшие кубические графы с числом пересечений 1—8 известны ().
Наименьшие кубические графы с числом пересечений: 1 — полный двудольный граф с 6 вершинами. 2 — граф Петерсена с 10 вершинами. 3 — граф Хивуда с 14 вершинами. 4 — граф Мёбиуса — Кантора с 16 вершинами. 5 — граф Паппа с 18 вершинами. 6 — Граф Дезарга c 20 вершинами. 7 — 4 графа с 22 вершинами (CNG 7A, CNG 7B, CNG 7C, CNG 7D). 8 — граф Науру и граф МакГи (или (3,7)-клетка) с 24 вершинами.
В 2009 году Икзу (Exoo) предположил, что наименьшим кубическим графом с числом пересечений 11 является граф Коксетера, с числом пересечений 13 — граф Татта — Коксетера, с числом пересечений 170 — 12-клетка Татта.
Неравенство для числа пересечений Очень полезное неравенство для числа пересечений обнаружили независимо , , Ньюборн (Newborn) и Семереди и Лейтон:
Для неориентированных простых графов с вершинами и рёбрами, таких что имеем:
Константа является наилучшей известной. Согласно Акерману. Для более ранних результатов с другими константами смотрите Пах и Тоф, Пах, Радчик, Тардос и Тоф константу можно понизить до , но это будет стоить заменой константы на .
Причиной интереса Лейтона к изучению числа пересечений было приложение к разработке СБИС микросхем в теоретической информатике. Позднее Секей также понял, что это неравенство даёт очень простые доказательства некоторых важных теорем геометрии инцидентности, таких как теорема Бека и теорема Семереди — Троттера, а Тамал Дей (Tamal Dey) использовал неравенство для доказательства верхней границы .
Для графов с обхватом, большим , и , Пах, Спенсер и Тот показали улучшение этого неравенства
Доказательство неравенства для числа пересечений Сначала дадим предварительную оценку: для любого графа с вершинами и рёбрами имеем
Для доказательства представим рисунок графа с точно пересечениями. Каждое такое пересечение можно удалить вместе с удалением ребра из . Таким образом мы можем найти граф по меньшей мере с рёбрами и вершинами с нулевым числом пересечений, а следовательно, это будет планарный граф. Но из формулы Эйлера мы должны иметь , откуда получаем требуемое неравенство. (Фактически, мы имеем для ).
Для получения неравенства числа пересечений мы применяем вероятностную аргументацию. Пусть — вероятностный параметр, который будет выбран позже. Построим случайный подграф графа путём расположения каждой вершины в независимо с вероятностью и каждое ребро будет находиться в тогда и только тогда, когда обе вершины ребра лежат в . Пусть и обозначают число рёбер, вершин и пересечений графа соответственно. Поскольку является подграфом графа , его диаграмма содержится в диаграмме . По предварительному неравенству числа пересечений имеем
Вычисляя математические ожидания, получим
Поскольку каждая из вершин в имеет вероятность попасть в , получим . Таким же образом, каждое ребро в имеет вероятность остаться в , поскольку оба конца должны находиться в . Таким образом, . Наконец, каждое пересечение на диаграмме имеет вероятность остаться в , поскольку каждое пересечение вовлекает четыре вершины. Чтобы это понять, представим диаграмму с пересечениями. Можем предположить, что любые два ребра на этой диаграмме с общей вершиной не пересекаются, в противном случае обмениваем части рёбер до пересечения и число пересечений уменьшается на одно. Таким образом, можно считать, что пересечение вовлекает четыре различные вершины графа . Вследствие этого, и мы получаем
Теперь, если мы положим (поскольку мы предположили, что ), после некоторых алгебраических выкладок, получим
Небольшое изменение приведённой аргументации позволяет заменить на для .
См. также 1-планарный граф
Примечания
Литература
Категория:Топологическая теория графов Категория:Неравенства Категория:Инварианты графов Категория:Визуализация графов