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

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

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

Не плутати з числом перетинів графа.

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

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

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

Історія

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

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

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

Задача визначення кількості схрещень повного графа поставлена вперше ^[en] і з'явилася друком у 1960. Хілл і його співавтор ^[en] (John_Ernest) були двома художниками-конструктивістами, зачарованими математикою, і вони не тільки сформулювали завдання, але й висловили для таких графів гіпотезу про верхню межу числа перетинів, яку Річард К. Гай опублікував у 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 (послідовність 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 перетинів. Подальші значення збираються в проєкті «Число прямолінійних схрещень». Цікаво, що невідомо, чи є звичайне і прямолінійне число схрещень тим же самим для повних двочасткових графів. Якщо гіпотеза Заранкевича вірна, то формула для числа схрещень повного графа асимптотично вірна, тобто,

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

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

^[en], сформульована Міхаелем Альбертсоном (Michael O. Albertson) в 2007 році, стверджує, що серед всіх графів з хроматичним числом n, повний граф K_n має мінімальне число схрещень. Тобто, якщо гіпотеза Гая — Сааті про число перетинів повного графа вірна, будь-який n-хроматичний граф має число перетинів як мінімум рівне з формулою в гіпотезі. Відомо, що це виконується для n ≤ 16.

Складність

У загальному випадку визначення числа схрещень графа є складним завданням. Гарей і Джонсон (Michael Garey, David S. Johnson) в 1983 році показали, що ця задача є NP-складною. Фактично, завдання залишається NP-складим навіть при звуженні її на кубічні графи і майже планарні графи (графи, які стають планарними після видалення одного ребра). Зокрема, визначення числа прямолінійних перетинів є повною для ^[en].

Однак існують ефективні алгоритми визначення, що число схрещень не перевищує фіксованої константи 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 маємо:

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

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

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

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

${\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) ≤ 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. За попередньою нерівністю числа перетинів маємо:

${\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 = 4n/e < 1 (оскільки ми припустили, що e > 4n), після деяких алгебраїчних викладок, отримаємо:

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

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

Див. також

• 1-планарний граф
• ^[en]

Примітки

1. (1977). A Note of Welcome. . 1: 7—9. doi:10.1002/jgt.3190010105.
2. (1944). The graphic presentation of sociometric data. Sociometry. 7 (3): 283—289. JSTOR 2785096. The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines.
3. ; (1994). The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability. American Mathematical Monthly. 101 (10): 939—943. doi:10.2307/2975158. JSTOR 2975158.
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.
18. Grohe, 2005, с. 285-302.
19. Kawarabayashi, Reed, 2007.
20. Even, Guha, Schieber, 2003.
21. Rectilinear Crossing Number, Інститут Програмних технологій Граца, Технологічний університет (2009).
22. Weisstein, Eric W. Graph Crossing Number(англ.) на сайті Wolfram MathWorld.
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.
31. Ackerman, 2013.

Література

• 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) — .
• 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 // . — 2014.
• , 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 // . — 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) — . — 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. — . — DOI:10.1145/1250790.1250848.
• Guy Even, Sudipto Guha, Baruch Schieber. Improved Approximations Crossings of in Graph Drawings and VLSI Layout Areas // . — 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 // . — 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 // . — 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 // . — 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.