Число схрещень

В теорії графів число схрещень cr(G) графа G — це найменше число перетинів ребер плоского зображення графа G. Наприклад, граф є планарним тоді і тільки тоді, коли число його схрещень дорівнює нулю.

Число схрещень
Досліджується в	теорія графів
Формула	${\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$
Підтримується Вікіпроєктом	Вікіпедія:Проєкт:Математика

Рисунок графа Хівуда з трьома перетинами. Це мінімальне число схрещень поміж усіх можливих малюнків цього графа, так що число перетинів графа дорівнює cr(G) = 3.

Математичною відправною точкою вивчення числа схрещень стала задача Турана про цегельну фабрику, поставлена Палом Тураном. У цій задачі потрібно знайти число схрещень повного двочасткового графа K_m,n. Однак та ж сама задача поставлена в соціології приблизно в той же самий час у зв'язку з побудовою соціограм. Задача дуже важлива для візуалізації графів.

Якщо не вказано інше, число схрещень відноситься до зображень графів, у яких ребра зображаються довільними кривими. Число прямолінійних схрещень вказує, що всі ребра є відрізками прямих і може відрізнятися від числа схрещень. Зокрема, число прямолінійних схрещень повного графа дорівнює мінімальному числу опуклих чотирикутників, визначених множиною n точок загального положення, що тісно пов'язано з задачею зі щасливим кінцем.

Історія

Під час Другої світової війни угорський математик Пал Туран був змушений працювати на цегляній фабриці, штовхаючи візок, навантажену цеглою, від випалювальних печей у склади (на фабриці були колії від кожної печі до кожного складу) Саме те, що візок важче штовхати в місцях перетину колій і привело Турана до постановки задачі цегляної фабрики: «Яке мінімальне число перетинів малюнка повного графа?».

Заранкевич намагався вирішити завдання Турана. Його доказ містив помилку, але він встановив правильну верхню межу:

${\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. Існує гіпотеза, відома як гіпотеза Заранкевича, що ця нерівність насправді є рівністю. Нижня межа відкрита лише через одинадцять років після публікації, майже одночасно з Герхардом Рингелем (Gerhard Ringel) та Полом Кайненом (Paul Chester Kainen).

Задача визначення кількості схрещень повного графа поставлена вперше Ентоні Хіллом і з'явилася друком у 1960. Хілл і його співавтор Джон Ернест (John_Ernest) були двома художниками-конструктивістами, зачарованими математикою, і вони не тільки сформулювали завдання, але й висловили для таких графів гіпотезу про верхню межу числа перетинів, яку Річард К. Гай опублікував у 1960 році. А саме, що ця межа дорівнює:

${\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 (послідовність A000241 з Онлайн енциклопедії послідовностей цілих чисел, OEIS). Незалежне формулювання гіпотези дав Томас Сааті в 1964 році. Томас Сааті пізніше з'ясував, що верхня межа досягається для p ≤ 10, а Пен і Ріхтер (Pan, Richter) показали, що вона досягається і для p = 11, 12.

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

$\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 відомі (послідовність A110507 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Найменші кубічні графи з числом перетинів

1 — Повний дводольний граф K_3,3 із 6 вершинами.

2 — граф Петерсена з 10 вершинами.

3 — граф Хивуда з 14 вершинами.

4 — граф Мебіуса — Кантора з 16 вершинами.

5 — граф Паппа з 18 вершинами.

6 — Граф Дезарга c 20 вершинами.

7 — Немає (22 вершин).

8 — граф Науру і граф Маꥳ (або (3,7)-клітина) з 24 вершинами.

У 2009 році Икзу (Exoo) припустив, що найменшим кубічним графом з числом перетинів 11 є граф Коксетера, з числом перетинів 13 — граф Татта — Коксетера, з числом перетинів 170 — 12-клітка Татта.

Нерівність числа схрещень

Дуже корисну «нерівність числа схрещень» виявили незалежно Айтай, Вацлав Хватал, Ньюборн (Newborn) і Семереді і Лейтон:

Для неорієнтованих простих графів G з n вершинами та e ребрами, таких що e > 7n маємо:

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

Константа 29 є найбільш відомою. Відповідно до Акермана константу 7 можна знизити до 4, але це буде коштувати заміною константи 29 на 64.

Причиною інтересу Лейтона до вивчення числа перетинів було застосування до розробки НВІС мікросхем у теоретичній інформатиці. Пізніше Секей також зрозумів, що це нерівність дає дуже прості докази деяких важливих теорем геометрії інцидентності, таких як Теорема Бека і теорема Семереді — Троттера, а Тамал Дей (Tamal Dey) використовував нерівність для доведення верхньої межі геометричних k-множин.

Для графів з великим обхватом 2r, e ≥ 4n, Пах, Спенсер і Той показали поліпшення цієї нерівності.

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

Доведення нерівності для числа схрещень

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

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

Для доказу уявімо малюнок графа 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. Нехай e_H, n_H і cr_H позначають число ребер, вершин і перетинів графа H відповідно. Оскільки H є підграфом графа G, його діаграма міститься в діаграмі G. За попередньою нерівністю числа перетинів маємо:

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

Обчислюючи математичні сподівання, отримаємо:

$\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) і ми отримуємо:

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

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

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

Невелика зміна наведеної аргументації дозволяє замінити 64 33.75 e> 7.5n.

Див. також

• 1-планарний граф
• Максимальна планарна проблема підграфа

Література

• P. Турана. A Note of Welcome // J. Теорія Графів. — 1977. — Т. 1. — DOI:10.1002/jgt.3190010105.
• Urie Bronfenbrenner. Графічна презентація Социометрические даних // 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) — ISBN 978-0-8218-4691-9.
• K. Zarankiewicz. On a Problem of P. Турана Concerning Graphs // Fund. Math. — 1954. — Т. 41.
• R. K. Guy. Decline and fall of Zarankiewicz's Theorem / ed. by F. Harary // Proof Techniques in Graph Theory. — Academic Press, 1969.
• R. K. Guy. A problem комбінаторної // Nabla (Bulletin of the Malayan Mathematical Society). — 1960. — Т. 7.
• T. L. Saaty. Мінімальна кількість перетинів в повних графах // 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 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 "K_m,n" and "K_n" // SIAM Journal on Discrete Mathematics. — 2006. — Т. 20, вип. 1. — DOI:10.1137/S0895480104442741.
• Marcus Schaefer. The graph crossing number and its variants: a survey // The Electronic Journal of Комбінаторики. — 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 // Комбінаторики, 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 // Журнал комбінаторної теорії. — 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 time quadratic // 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 Crossings of 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 Комбінаторики. — 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 crossing on 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.
• 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.
• G. Exoo. Rectilinear Drawings of Famous Graphs.
• János Barát, Géza Tóth. Towards the Albertson Гіпотезу. — 2009.