Число схрещувань

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

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

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

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

Історія

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

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

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

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

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

1 — Повний дводольний граф K3,3 із 6 вершинами.
2 — граф Петерсена з 10 вершинами.
3 — граф Хивуда з 14 вершинами.
4 — граф Мебіуса — Кантора з 16 вершинами.
5 — граф Паппа з 18 вершинами.
6 — Граф Дезарга c 20 вершинами.
7 — Немає (22 вершин).[22]
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-планарний граф
  • Максимальна планарна проблема підграфу

Примітки
  1. Turán, P. (1977). A Note of Welcome. Journal of Graph Theory 1: 7–9. doi:10.1002/jgt.3190010105.
  2. Bronfenbrenner, Urie (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. Scheinerman, Edward R.; Wilf, Herbert S. (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. JSTOR 2975158. doi:10.2307/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. Графічнa презентація Социометрические даних // 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 "Km,n" and "Kn" // 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.