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

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

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

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

ІсторіяРедагувати

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

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

 

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

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

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

СкладністьРедагувати

У загальному випадку визначення числа схрещень графа є складним завданням. Гарей і Джонсон (Michael Garey, David S. Johnson) в 1983 році показали, що ця задача є NP-складною[14]. Фактично, завдання залишається NP-складим навіть при звуженні її на кубічні графи[15] і майже планарні графи[16] (графи, які стають планарними після видалення одного ребра). Зокрема, визначення числа прямолінійних перетинів є повною для екзистенційної теорії дійсних чисел[en][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] також зрозумів, що це нерівність дає дуже прості докази деяких важливих теорем геометрії інцидентності, таких як Теорема Бека[en] і теорема Семереді-Троттера, а Тамал Дей (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].

Див. такожРедагувати

ПриміткиРедагувати

  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.

ЛітератураРедагувати