Минимальное число пересечений рёбер графа

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Не следует путать с числом пересечений графа — наименьшим числом элементов в представлении графа как графа пересечений.
См. также: Число пересечений (теория узлов)
Рисунок графа Хивуда с тремя пересечениями. Это минимальное число пересечений среди всех возможных рисунков этого графа, так что число пересечений графа равно cr(G) = 3.

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

Математической отправной точкой изучения числа пересечений стала задача Турана о кирпичной фабрике, поставленная Палом Тураном, в которой требовалось найти число пересечений полного двудольного графа Km,n[1]. Однако та же самая задача поставлена в социологии примерно в то же самое время в связи с построением социограмм[2]. Задача продолжает играть большую роль в визуализации графов.

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

История

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

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

[math]\displaystyle{ \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]

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

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

[math]\displaystyle{ \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]

что даёт значения 1, 3, 9, 18, 36, 60, 100, 150 для p = 5, ..., 12 (последовательность A000241 в OEIS). Независимую формулировку гипотезы дал Томас Л. Саати в 1964 году[8]. Саати позднее выяснил, что верхняя граница достигается для p ≤ 10, а Пэн и Рихтер (Pan, Richter) показали, что она достигается и для p = 11, 12

Если разрешены только прямолинейные дуги, требуется большее число пересечений. Число прямолинейных пересечений для графов K5 — K12 равно 1, 3, 9, 19, 36, 62, 102, 153 (последовательность A014540 в OEIS). Значения для графов вплоть до K27 известны. Для K28 нужно либо 7233, либо 7234 пересечений. Дальнейшие значения собираются в проекте «Число прямолинейных пересечений»[9]. Интересно, что неизвестно, являются ли обычное и прямолинейное число пересечений тем же самым для полных двудольных графов. Если гипотеза Заранкиевича верна, то формула для числа пересечений полного графа асимптотически верна[10], то есть,

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

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

Гипотеза Албертсона, сформулированная Михаэлем Альбертсоном (Michael O. Albertson) в 2007 году, утверждает, что среди всех графов с хроматическим числом n полный граф Kn имеет минимальное число пересечений. То есть, если гипотеза Гая — Саати о числе пересечения полного графа верна, любой n-хроматический граф имеет число пересечений как минимум равное формуле в гипотезе. Известно, что это выполняется для n ≤ 16[13].

Сложность

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

Однако существуют эффективные алгоритмы определения, что число пересечений не превосходит фиксированной константы k. Другими словами, задача является разрешимой с фиксированным параметром[англ.][18][19]. Она остаётся сложной для больших k, таких как |V|/2. Существуют также эффективные аппроксимационные алгоритмы для оценки cr(G) на графах с ограниченной степенью[20]. На практике используются эвристистические алгоритмы, такие как простой алгоритм, начинающий с графа без рёбер и постепенно добавляющий рёбра так, чтобы получить минимально возможное добавочное число пересечений. Этот алгоритм используется в программе проекта распределённых вычислений «Число прямолинейных пересечений»[21].

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

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

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

1 — полный двудольный граф K3,3 с 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-клетка Татта[23][24].

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

Очень полезное неравенство для числа пересечений обнаружили независимо Аитаи[англ.], Хватал[англ.], Ньюборн (Newborn) и Семереди[25] и Лейтон[26]:

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

Константа 29 является наилучшей известной. Согласно Акерману[27] константу 7 можно понизить до 4, но это будет стоить заменой константы 29 на 64.

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

Для графов с обхватом, большим 2r, и e ≥ 4n, Пах, Спенсер и Тот[30] показали улучшение этого неравенства

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

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

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

[math]\displaystyle{ \operatorname{cr}(G) \geq e - 3n. }[/math]

Для доказательства представим рисунок графа G с точно cr(G) пересечениями. Каждое такое пересечение можно удалить вместе с удалением ребра из G. Таким образом мы можем найти граф по меньшей мере с e − cr(G) рёбрами и n вершинами с нулевым числом пересечений, а следовательно, это будет планарный граф. Но из формулы Эйлера мы должны иметь e − cr(G) ≤ 3n, откуда получаем требуемое неравенство. (Фактически, мы имеем e − cr(G) ≤ 3n − 6 для n ≥ 3).

Для получения неравенства числа пересечений мы применяем вероятностную аргументацию. Пусть 0 < p < 1 — вероятностный параметр, который будет выбран позже. Построим случайный подграф H графа G путём расположения каждой вершины G в H независимо с вероятностью p и каждое ребро G будет находиться в H тогда и только тогда, когда обе вершины ребра лежат в H. Пусть eH, nH и crH обозначают число рёбер, вершин и пересечений графа H соответственно. Поскольку H является подграфом графа G, его диаграмма содержится в диаграмме G. По предварительному неравенству числа пересечений имеем

[math]\displaystyle{ \operatorname{cr}_H \geq e_H - 3n_H. }[/math]

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

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

Поскольку каждая из n вершин в G имеет вероятность p попасть в H, получим E[nH] = pn. Таким же образом, каждое ребро в G имеет вероятность p2 остаться в H, поскольку оба конца должны находиться в H. Таким образом, E[eH] = p2e. Наконец, каждое пересечение на диаграмме G имеет вероятность p4 остаться в H, поскольку каждое пересечение вовлекает четыре вершины. Чтобы это понять, представим диаграмму G с cr(G) пересечениями. Можем предположить, что любые два ребра на этой диаграмме с общей вершиной не пересекаются, в противном случае обмениваем части рёбер до пересечения и число пересечений уменьшается на одно. Таким образом, можно считать, что пересечение вовлекает четыре различные вершины графа G. Вследствие этого, E[crH] = p4cr(G) и мы получаем

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

Теперь, если мы положим p = 4n/e < 1 (поскольку мы предположили, что e > 4n), после некоторых алгебраических выкладок, получим

[math]\displaystyle{ \operatorname{cr}(G) \geq \frac{e^3}{64 n^2}. }[/math]

Небольшое изменение приведённой аргументации позволяет заменить 64 на 33.75 для e > 7.5n[31].

См. также

Примечания

  1. ↑ Turán, 1977, с. 7—9.
  2. ↑ Bronfenbrenner, 1944, с. 283—289.
  3. ↑ Scheinerman, Wilf, 1994, с. 939—943.
  4. ↑ Pach, Sharir, 2009, с. 126—127.
  5. ↑ Zarankiewicz, 1954, с. 137—145.
  6. ↑ Guy, 1969, с. 63—69.
  7. ↑ 7,0 7,1 Guy, 1960, с. 68—72.
  8. ↑ Saaty, 1964, с. 688—690.
  9. ↑ Aichholzer.
  10. ↑ Kainen, 1968, с. 374—377.
  11. ↑ Klerk, Maharry, Pasechnik, Richter, Salazar, 2006, с. 189—202.
  12. ↑ Schaefer, 2014, с. #DS21.
  13. ↑ Barát, Tóth, 2009.
  14. ↑ Garey, Johnson, 1983, с. 312—316.
  15. ↑ Hliněný, 2006, с. 455—471.
  16. ↑ Cabello, Mohar, 2013, с. 1803—1829.
  17. ↑ Schaefer, 2010, с. 334—344.
  18. ↑ Grohe, 2005, с. 285—302.
  19. ↑ Kawarabayashi, Reed, 2007, с. 382—390.
  20. ↑ Even, Guha, Schieber, 2003, с. 231—252.
  21. ↑ Rectilinear Crossing Number Архивная копия от 25 июня 2008 на Wayback Machine, Институт Программных технологий Граца, Технологический университет (2009).
  22. ↑ Weisstein, Eric W. "Smallest Cubic Crossing Number Graph." From MathWorld--A Wolfram Web Resource.. Дата обращения: 20 сентября 2020. Архивировано 19 марта 2020 года.
  23. ↑ Exoo.
  24. ↑ Pegg, Exoo, 2009.
  25. ↑ Ajtai, Chvátal, Newborn, Szemerédi, 1982, с. 9—12.
  26. ↑ Leighton, 1983.
  27. ↑ Ackerman, 2013. Для более ранних результатов с другими константами смотрите Пах и ТофPach, Tóth, 1997, с. 427—439, Пах, Радчик, Тардос и ТофPach, Radoičić, Tardos, Tóth, 2006, с. 527—552
  28. ↑ Székely, 1997, с. 353—358.
  29. ↑ Dey, 1998, с. 373—382.
  30. ↑ Pach, Spencer, Tóth, 2000, с. 623—644.
  31. ↑ Ackerman, 2013.

Литература

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Минимальное_число_пересечений_рёбер_графа&oldid=5815628