В теории графовчисло пересеченийcr(G) графа G — это наименьшее число пересечений рёбер плоского рисунка графа G. Например, граф является планарнымтогда и только тогда, когда его число пересечений равно нулю.
Рисунок графа Хивуда с тремя пересечениями. Это минимальное число пересечений среди всех возможных рисунков этого графа, так что число пересечений графа равно cr(G) = 3.
Если не указано другое, число пересечений относится к представлениям графов с помощью любых кривых. Условие прямолинейных пересечений требует, чтобы все рёбра были отрезками прямых, что может изменить ответ. В частности, число прямолинейных пересечений полного графа равно минимальному числу выпуклых четырёхугольников, определённых множеством 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] (графы, которые становятся планарными после удаления одного ребра). В частности, определение числа прямолинейных пересечений является полной[en] для экзистенциальной теории вещественных чисел[17].
Однако существуют эффективные алгоритмы определения, что число пересечений не превосходит фиксированной константы k. Другими словами, задача является разрешимой с фиксированным параметром[en][18][19]. Она остаётся сложной для больших k, таких как |V|/2. Существуют также эффективные аппроксимационные алгоритмы для оценки cr(G) на графах с ограниченной степенью[20]. На практике используются эвристистические алгоритмы, такие как простой алгоритм, начинающий с графа без рёбер и постепенно добавляющий рёбра так, чтобы получить минимально возможное добавочное число пересечений. Этот алгоритм используется в программе проекта распределённых вычислений «Число прямолинейных пересечений»[21].
Очень полезное неравенство для числа пересечений обнаружили независимо Аитаи[en], Хватал[en], Ньюборн (Newborn) и Семереди[25] и Лейтон[26]:
Для неориентированных простых графовG с n вершинами и e рёбрами, таких что e > 7n имеем:
Константа 29 является наилучшей известной. Согласно Акерману[27] константу 7 можно понизить до 4, но это будет стоить заменой константы 29 на 64.
Причиной интереса Лейтона к изучению числа пересечений было приложение к разработке СБИС микросхем в теоретической информатике. Позднее Секей[28] также понял, что это неравенство даёт очень простые доказательства некоторых важных теорем геометрии инцидентности, таких как теорема Бека и теорема Семереди — Троттера, а Тамал Дей (Tamal Dey) использовал неравенство для доказательства верхней границы геометрических k-множеств[en][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].
Urie Bronfenbrenner. The graphic presentation of sociometric data // Sociometry. — 1944. — Т. 7, вып. 3. — JSTOR2785096.
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. — JSTOR2975158.
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.
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.
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.
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.
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).
![\mathbf{E}[\operatorname{cr}_H] \geq \mathbf{E}[e_H] - 3 \mathbf{E}[n_H].](https://xn--b1aeclack5b4j.su/save/svg/rest_v1/media/math/render/svg/542f8642914f6175d04439b15faa6155d2083d2c.svg)
