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

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

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

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

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

История

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

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

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

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

что даёт значения 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], то есть,

К апрелю 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 имеем:

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

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

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

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

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

Для доказательства представим рисунок графа 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. По предварительному неравенству числа пересечений имеем

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

Поскольку каждая из 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) и мы получаем

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

Небольшое изменение приведённой аргументации позволяет заменить 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. 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, Институт Программных технологий Граца, Технологический университет (2009).
  22. Weisstein, Eric W. "Smallest Cubic Crossing Number Graph." From MathWorld--A Wolfram Web Resource.
  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.

Литература
  • P. Turán. A Note of Welcome // J. Graph Theory. — 1977. — Т. 1. — doi:10.1002/jgt.3190010105.
  • Urie Bronfenbrenner. The graphic presentation of sociometric data // Sociometry. — 1944. — Т. 7, вып. 3. — .
  • Edward R. Scheinerman, Herbert S. Wilf. The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability // American Mathematical Monthly. — 1994. — Т. 101, вып. 10. — doi:10.2307/2975158. — .
  • János Pach, Micha Sharir. 5.1 Crossings—the Brick Factory Problem // Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. — American Mathematical Society, 2009. — Т. 152. — (Mathematical Surveys and Monographs).
  • K. Zarankiewicz. On a Problem of P. Turán Concerning Graphs // Fund. Math. — 1954. — Т. 41.
  • R. K. Guy. Decline and fall of Zarankiewicz's Theorem // Proof Techniques in Graph Theory / ed. by F. Harary. — Academic Press, 1969.
  • R. K. Guy. A combinatorial problem // Nabla (Bulletin of the Malayan Mathematical Society). — 1960. — Т. 7.
  • T. L. Saaty. The minimum number of intersections in complete graphs // Proceedings of the National Academy of Sciences of the United States of America. — 1964. — Т. 52. — doi:10.1073/pnas.52.3.688.
  • P. C. Kainen. On a problem of P. Erdos // Journal of Combinatorial Theory. — 1968. — Т. 5. — doi:10.1016/s0021-9800(68)80013-4.
  • E. de Klerk, J. Maharry, D. V. Pasechnik, B. Richter, G. Salazar. Improved bounds for the crossing numbers of Km,n and Kn // SIAM Journal on Discrete Mathematics. — 2006. — Т. 20, вып. 1. — doi:10.1137/S0895480104442741. Архивировано 18 июля 2011 года.
  • Marcus Schaefer. The graph crossing number and its variants: a survey // The Electronic Journal of Combinatorics. — 2014.
  • M. R. Garey, D. S. Johnson. Crossing number is NP-complete // SIAM J. Alg. Discr. Meth.. — 1983. — Т. 4, вып. 3. — doi:10.1137/0604033.
  • L. A. Székely. Crossing numbers and hard Erdős problems in discrete geometry // Combinatorics, Probability and Computing. — 1997. — Т. 6, вып. 3. — doi:10.1017/S0963548397002976.
  • T. L. Dey. Improved bounds for planar k-sets and related problems // Discrete and Computational Geometry. — 1998. — Т. 19, вып. 3. — doi:10.1007/PL00009354.
  • P. Hliněný. Crossing number is hard for cubic graphs // Journal of Combinatorial Theory, Series B. — 2006. — Т. 96, вып. 4. — doi:10.1016/j.jctb.2005.09.009.
  • Cabello S., Mohar B. Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard // SIAM Journal on Computing. — 2013. — Т. 42, вып. 5. — doi:10.1137/120872310.
  • Marcus Schaefer. Complexity of some geometric and topological problems // International Symposium on Graph Drawing. — Springer-Verlag, 2010. — Т. 5849. — (Lecture Notes in Computer Science). — ISBN 978-3-642-11804-3. — doi:10.1007/978-3-642-11805-0_32.
  • M. Grohe. Computing crossing numbers in quadratic time // J. Comput. System Sci. — 2005. — Т. 68, вып. 2. — doi:10.1016/j.jcss.2003.07.008.
  • Ken-ichi Kawarabayashi, Bruce Reed. Computing crossing number in linear time // Proceedings of the 29th Annual ACM Symposium on Theory of Computing. — 2007. — ISBN 978-1-59593-631-8. — doi:10.1145/1250790.1250848.
  • Guy Even, Sudipto Guha, Baruch Schieber. Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas // SIAM Journal on Computing. — 2003. — Т. 32, вып. 1. — doi:10.1137/S0097539700373520.
  • E. T. Pegg, G. Exoo. Crossing Number Graphs // Mathematica Journal. — 2009. — Т. 11.
  • M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi. Crossing-free subgraphs // Theory and Practice of Combinatorics. — 1982. — Т. 60. — (North-Holland Mathematics Studies).
  • T. Leighton. Complexity Issues in VLSI. — Cambridge, MA: MIT Press, 1983. — (Foundations of Computing Series).
  • János Pach, Joel Spencer, Géza Tóth. New bounds on crossing numbers // Discrete and Computational Geometry. — 2000. — Т. 24, вып. 4. — doi:10.1007/s004540010011.
  • Eyal Ackerman. On topological graphs with at most four crossings per edge. — 2013. Архивировано 14 июля 2014 года.
  • János Pach, Géza Tóth. Graphs drawn with few crossings per edge // Combinatorica. — 1997. — Т. 17, вып. 3. — doi:10.1007/BF01215922.
  • János Pach, Radoš Radoičić, Gábor Tardos, Géza Tóth. Improving the crossing lemma by finding more crossings in sparse graphs // Discrete and Computational Geometry. — 2006. — Т. 36, вып. 4. — doi:10.1007/s00454-006-1264-9.
  • Oswin Aichholzer. Rectilinear Crossing Number project. Архивировано 30 декабря 2012 года.
  • G. Exoo. Rectilinear Drawings of Famous Graphs.
  • János Barát, Géza Tóth. Towards the Albertson Conjecture. — 2009.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.