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

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

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

История

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

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

${\displaystyle {\textrm {cr}}(K_{m,n})\leq \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 }$

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

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

${\displaystyle {\textrm {cr}}(K_{p})\leq {\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 ,}$

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

Если разрешены только прямолинейные дуги, требуется большее число пересечений. Число прямолинейных пересечений для графов K ₅ — K ₁₂ равно 1, 3, 9, 19, 36, 62, 102, 153 (последовательность в OEIS ). Значения для графов вплоть до K ₂₇ известны. Для K ₂₈ нужно либо 7233, либо 7234 пересечений. Дальнейшие значения собираются в проекте «Число прямолинейных пересечений» . Интересно, что неизвестно, являются ли обычное и прямолинейное число пересечений тем же самым для полных двудольных графов. Если гипотеза Заранкиевича верна, то формула для числа пересечений полного графа асимптотически верна , то есть,

${\displaystyle \lim _{p\to \infty }{\textrm {cr}}(K_{p}){\tfrac {64}{p^{4}}}=1.}$

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

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

Сложность

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

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

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

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

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

1 — полный двудольный граф K _3,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-клетка Татта .

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

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

Для неориентированных простых графов G с n вершинами и e рёбрами, таких что e > 7 n имеем:

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}$

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

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

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

${\displaystyle \operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.}$

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

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

${\displaystyle \operatorname {cr} (G)\geq e-3n.}$

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

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

${\displaystyle \operatorname {cr} _{H}\geq e_{H}-3n_{H}.}$

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

${\displaystyle \mathbf {E} [\operatorname {cr} _{H}]\geq \mathbf {E} [e_{H}]-3\mathbf {E} [n_{H}].}$

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

${\displaystyle p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.}$

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

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{64n^{2}}}.}$

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

См. также

• 1-планарный граф

Примечания

Литература

• P. Turán. A Note of Welcome // J. Graph Theory. — 1977. — Т. 1 . — doi : .
• Urie Bronfenbrenner. The graphic presentation of sociometric data // Sociometry. — 1944. — Т. 7 , вып. 3 . — JSTOR .
• 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 : . — JSTOR .
• 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 : .
• P. C. Kainen. On a problem of P. Erdos // Journal of Combinatorial Theory. — 1968. — Т. 5 . — doi : .
• E. de Klerk, J. Maharry, D. V. Pasechnik, B. Richter, G. Salazar. // . — 2006. — Т. 20 , вып. 1 . — doi : . 18 июля 2011 года.
• Marcus Schaefer. The graph crossing number and its variants: a survey // . — 2014.
• , . Crossing number is NP-complete // SIAM J. Alg. Discr. Meth.. — 1983. — Т. 4 , вып. 3 . — doi : .
• L. A. Székely. Crossing numbers and hard Erdős problems in discrete geometry // Combinatorics, Probability and Computing. — 1997. — Т. 6 , вып. 3 . — doi : .
• T. L. Dey. Improved bounds for planar k -sets and related problems // . — 1998. — Т. 19 , вып. 3 . — doi : .
• P. Hliněný. Crossing number is hard for cubic graphs // Journal of Combinatorial Theory, Series B . — 2006. — Т. 96 , вып. 4 . — doi : .
• 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 : .
• Marcus Schaefer. Complexity of some geometric and topological problems // . — Springer-Verlag, 2010. — Т. 5849. — (Lecture Notes in Computer Science). — ISBN 978-3-642-11804-3 . — doi : .
• M. Grohe. Computing crossing numbers in quadratic time // J. Comput. System Sci. — 2005. — Т. 68 , вып. 2 . — doi : .
• 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 : .
• Guy Even, Sudipto Guha, Baruch Schieber. Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas // . — 2003. — Т. 32 , вып. 1 . — doi : .
• 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 // . — 2000. — Т. 24 , вып. 4 . — doi : .
• Eyal Ackerman. . — 2013. 14 июля 2014 года.
• János Pach, Géza Tóth. Graphs drawn with few crossings per edge // . — 1997. — Т. 17 , вып. 3 . — doi : .
• János Pach, Radoš Radoičić, Gábor Tardos, Géza Tóth. Improving the crossing lemma by finding more crossings in sparse graphs // . — 2006. — Т. 36 , вып. 4 . — doi : .
• Oswin Aichholzer. . 30 декабря 2012 года.
• G. Exoo. .
• János Barát, Géza Tóth. . — 2009.