Русская Википедия:Минимальное число пересечений рёбер графа

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Не путать Шаблон:Seealso

Файл:3-crossing Heawood graph.svg
Рисунок графа Хивуда с тремя пересечениями. Это минимальное число пересечений среди всех возможных рисунков этого графа, так что число пересечений графа равно Шаблон:Math.

В теории графов число пересечений Шаблон:Math графа Шаблон:Mvar — это наименьшее число пересечений рёбер плоского рисунка графа Шаблон:Mvar. Например, граф является планарным тогда и только тогда, когда его число пересечений равно нулю.

Математической отправной точкой изучения числа пересечений стала задача Турана о кирпичной фабрике, поставленная Палом Тураном, в которой требовалось найти число пересечений полного двудольного графа Шаблон:MvarШаблон:Sfn. Однако та же самая задача поставлена в социологии примерно в то же самое время в связи с построением социограммШаблон:Sfn. Задача продолжает играть большую роль в визуализации графов.

Если не указано другое, число пересечений относится к представлениям графов с помощью любых кривых. Условие прямолинейных пересечений требует, чтобы все рёбра были отрезками прямых, что может изменить ответ. В частности, число прямолинейных пересечений полного графа равно минимальному числу выпуклых четырёхугольников, определённых множеством Шаблон:Mvar точек в общем положении, что тесно связано с задачей со счастливым концомШаблон:Sfn.

История

Во время Второй мировой войны венгерский математик Пал Туран вынужден работать на кирпичной фабрике, толкая тележку, гружёную кирпичами, от обжиговых печей в склады. На фабрике имелись колеи от каждой печи до каждого склада, и тележку труднее толкать в местах пересечения колей, что привело Турана к постановке задачи кирпичной фабрики: каково минимальное число пересечений рисунка полного графа?Шаблон:Sfn.

Заранкиевич (Zarankiewicz) пытался решить задачу ТуранаШаблон:Sfn. Его доказательство содержало ошибку, но он установил правильную верхнюю границу

<math>\textrm{cr}(K_{m,n}) \le \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</math>

для числа пересечений полного двудольного графа Шаблон:Mvar. Гипотеза, что это неравенство на самом деле является равенством, известна как гипотеза Заранкиевича. Нижняя граница открыта лишь одиннадцать лет спустя после публикации почти одновременно Герхардом Рингелем и Полем Кайненом (Paul Chester Kainen)Шаблон:Sfn.

Задача определения числа пересечений полного графа поставлена впервые Энтони Хиллом и появилась в печати в 1960Шаблон:Sfn. Хилл и его соавтор Джон Эрнест были двумя художниками-конструктивистами, очарованными математикой, и они не только сформулировали задачу, но и высказали для таких графов гипотезу о верхней границе числа пересечений, которую Ричард К. Гай опубликовал в 1960 годуШаблон:Sfn. А именно что эта граница равна

<math>\textrm{cr}(K_p) \le \tfrac{1}{4} \left\lfloor\tfrac{p}{2}\right\rfloor\left\lfloor\tfrac{p-1}{2}\right\rfloor\left\lfloor\tfrac{p-2}{2}\right\rfloor\left\lfloor\tfrac{p-3}{2}\right\rfloor,</math>

что даёт значения Шаблон:Math для Шаблон:Math (Шаблон:OEIS). Независимую формулировку гипотезы дал Томас Л. Саати в 1964 годуШаблон:Sfn. Саати позднее выяснил, что верхняя граница достигается для Шаблон:Math, а Пэн и Рихтер (Pan, Richter) показали, что она достигается и для Шаблон:Math

Если разрешены только прямолинейные дуги, требуется большее число пересечений. Число прямолинейных пересечений для графов Шаблон:Math — Шаблон:Math равно Шаблон:Math (Шаблон:OEIS). Значения для графов вплоть до Шаблон:Math известны. Для Шаблон:Math нужно либо 7233, либо 7234 пересечений. Дальнейшие значения собираются в проекте «Число прямолинейных пересечений»Шаблон:Sfn. Интересно, что неизвестно, являются ли обычное и прямолинейное число пересечений тем же самым для полных двудольных графов. Если гипотеза Заранкиевича верна, то формула для числа пересечений полного графа асимптотически вернаШаблон:Sfn, то есть,

<math> \lim_{p \to \infty} \textrm{cr}(K_p) \tfrac{64}{p^4} = 1. </math>

К апрелю 2015 число пересечений известно для совсем небольшого числа семейств графов. В частности, за исключением нескольких начальных случаев, число пересечений полных графов, полных двудольных графов и произведения циклов остаются неизвестными. Был некоторый успех для нижней границы, согласно сообщению де Клерка, Махарри, Пасечника и Рихтера (de Klerk, Maharry, Pasechnik, Richter)Шаблон:Sfn. Большой обзор различных вариантов приведен Шафером (Schaefer) Шаблон:Sfn.

Гипотеза Албертсона, сформулированная Михаэлем Альбертсоном (Michael O. Albertson) в 2007 году, утверждает, что среди всех графов с хроматическим числом Шаблон:Mvar полный граф Шаблон:Mvar имеет минимальное число пересечений. То есть, если гипотеза Гая — Саати о числе пересечения полного графа верна, любой Шаблон:Mvar-хроматический граф имеет число пересечений как минимум равное формуле в гипотезе. Известно, что это выполняется для Шаблон:MathШаблон:Sfn.

Сложность

В общем случае определение числа пересечений графа является сложной задачей. Гарей и Джонсон (Michael Garey, David S. Johnson) в 1983 году показали, что задача эта является NP-труднойШаблон:Sfn. Фактически, задача остаётся NP-трудной даже при сужении её на кубические графыШаблон:Sfn и почти планарные графыШаблон:Sfn (графы, которые становятся планарными после удаления одного ребра). В частности, определение числа прямолинейных пересечений является Шаблон:Не переведено 5 для экзистенциальной теории вещественных чиселШаблон:Sfn.

Однако существуют эффективные алгоритмы определения, что число пересечений не превосходит фиксированной константы Шаблон:Mvar. Другими словами, задача является Шаблон:Не переведено 5Шаблон:SfnШаблон:Sfn. Она остаётся сложной для больших k, таких как |V|/2. Существуют также эффективные аппроксимационные алгоритмы для оценки Шаблон:Math на графах с ограниченной степеньюШаблон:Sfn. На практике используются эвристистические алгоритмы, такие как простой алгоритм, начинающий с графа без рёбер и постепенно добавляющий рёбра так, чтобы получить минимально возможное добавочное число пересечений. Этот алгоритм используется в программе проекта распределённых вычислений «Число прямолинейных пересечений»[1].

Число пересечений кубических графов

Наименьшие кубические графы с числом пересечений 1—8 известны (Шаблон:OEIS).

Наименьшие кубические графы с числом пересечений:[2]

1 — полный двудольный граф Шаблон:Math с 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-клетка ТаттаШаблон:SfnШаблон:Sfn.

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

Очень полезное неравенство для числа пересечений обнаружили независимо Шаблон:Не переведено 5, Шаблон:Не переведено 5, Ньюборн (Newborn) и СемередиШаблон:Sfn и ЛейтонШаблон:Sfn:

Для неориентированных простых графов Шаблон:Mvar с Шаблон:Mvar вершинами и Шаблон:Mvar рёбрами, таких что Шаблон:Math имеем:
<math>\operatorname{cr}(G) \geq \frac{e^3}{29 n^2}.</math>

Константа Шаблон:Math является наилучшей известной. Согласно Акерману[3] константу Шаблон:Math можно понизить до Шаблон:Math, но это будет стоить заменой константы Шаблон:Math на Шаблон:Math.

Причиной интереса Лейтона к изучению числа пересечений было приложение к разработке СБИС микросхем в теоретической информатике. Позднее СекейШаблон:Sfn также понял, что это неравенство даёт очень простые доказательства некоторых важных теорем геометрии инцидентности, таких как теорема Бека и теорема Семереди — Троттера, а Тамал Дей (Tamal Dey) использовал неравенство для доказательства верхней границы Шаблон:Не переведено 5Шаблон:Sfn.

Для графов с обхватом, большим Шаблон:Math, и Шаблон:Math, Пах, Спенсер и ТотШаблон:Sfn показали улучшение этого неравенства

<math>\operatorname{cr}(G) \geq c_r\frac{e^{r+2}}{n^{r+1}}.</math>

Доказательство неравенства для числа пересечений

Сначала дадим предварительную оценку: для любого графа Шаблон:Mvar с Шаблон:Mvar вершинами и Шаблон:Mvar рёбрами имеем

<math>\operatorname{cr}(G) \geq e - 3n.</math>

Для доказательства представим рисунок графа Шаблон:Mvar с точно Шаблон:Math пересечениями. Каждое такое пересечение можно удалить вместе с удалением ребра из Шаблон:Mvar. Таким образом мы можем найти граф по меньшей мере с Шаблон:Math рёбрами и Шаблон:Mvar вершинами с нулевым числом пересечений, а следовательно, это будет планарный граф. Но из формулы Эйлера мы должны иметь Шаблон:Math, откуда получаем требуемое неравенство. (Фактически, мы имеем Шаблон:Math для Шаблон:Math).

Для получения неравенства числа пересечений мы применяем вероятностную аргументацию. Пусть Шаблон:Math — вероятностный параметр, который будет выбран позже. Построим случайный подграф Шаблон:Mvar графа Шаблон:Mvar путём расположения каждой вершины Шаблон:Mvar в Шаблон:Mvar независимо с вероятностью Шаблон:Mvar и каждое ребро Шаблон:Mvar будет находиться в Шаблон:Mvar тогда и только тогда, когда обе вершины ребра лежат в Шаблон:Mvar. Пусть Шаблон:Mvar и Шаблон:Math обозначают число рёбер, вершин и пересечений графа Шаблон:Mvar соответственно. Поскольку Шаблон:Mvar является подграфом графа Шаблон:Mvar, его диаграмма содержится в диаграмме Шаблон:Mvar. По предварительному неравенству числа пересечений имеем

<math>\operatorname{cr}_H \geq e_H - 3n_H.</math>

Вычисляя математические ожидания, получим

<math>\mathbf{E}[\operatorname{cr}_H] \geq \mathbf{E}[e_H] - 3 \mathbf{E}[n_H].</math>

Поскольку каждая из Шаблон:Mvar вершин в Шаблон:Mvar имеет вероятность Шаблон:Mvar попасть в Шаблон:Mvar, получим Шаблон:Math. Таким же образом, каждое ребро в Шаблон:Mvar имеет вероятность Шаблон:Math остаться в Шаблон:Mvar, поскольку оба конца должны находиться в Шаблон:Mvar. Таким образом, Шаблон:Math. Наконец, каждое пересечение на диаграмме Шаблон:Mvar имеет вероятность Шаблон:Math остаться в Шаблон:Mvar, поскольку каждое пересечение вовлекает четыре вершины. Чтобы это понять, представим диаграмму Шаблон:Mvar с Шаблон:Math пересечениями. Можем предположить, что любые два ребра на этой диаграмме с общей вершиной не пересекаются, в противном случае обмениваем части рёбер до пересечения и число пересечений уменьшается на одно. Таким образом, можно считать, что пересечение вовлекает четыре различные вершины графа Шаблон:Mvar. Вследствие этого, Шаблон:Math и мы получаем

<math> p^4 \operatorname{cr}(G) \geq p^2 e - 3 p n.</math>

Теперь, если мы положим Шаблон:Math (поскольку мы предположили, что Шаблон:Math), после некоторых алгебраических выкладок, получим

<math> \operatorname{cr}(G) \geq \frac{e^3}{64 n^2}.</math>

Небольшое изменение приведённой аргументации позволяет заменить Шаблон:Math на Шаблон:Math для Шаблон:MathШаблон:Sfn.

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Rectilinear Crossing Number Шаблон:Wayback, Институт Программных технологий Граца, Технологический университет (2009).
  2. ↑ Шаблон:Cite web
  3. ↑ Шаблон:Sfn0. Для более ранних результатов с другими константами смотрите Пах и ТофШаблон:Sfn0, Пах, Радчик, Тардос и ТофШаблон:Sfn0
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Минимальное_число_пересечений_рёбер_графа&oldid=10381546