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

Рисунок графа Хівуда з трьома перетинами. Це мінімальне число схрещень поміж усіх можливих малюнків цього графа, так що число перетинів графа дорівнює Шаблон:Math.

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

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

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

Історія

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

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

$\text{cr}(K_{m,n})\le \lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor$

для числа схрещень повного двочасткового графа Шаблон:Mvar. Існує гіпотеза, відома як гіпотеза Заранкевича, що ця нерівність насправді є рівністю. Нижня межа відкрита лише через одинадцять років після публікації, майже одночасно з Шаблон:Нп (Gerhard Ringel) та Шаблон:Нп (Paul Chester Kainen)Шаблон:Sfn.

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

$\text{cr}(K_p)\le \frac{1}{4}\lfloor \frac{p}{2}\rfloor \lfloor \frac{p-1}{2}\rfloor \lfloor \frac{p-2}{2}\rfloor \lfloor \frac{p-3}{2}\rfloor ,$

що дає значення Шаблон:Math для Шаблон:Math (Шаблон:OEIS). Незалежне формулювання гіпотези дав Томас Сааті в 1964 роціШаблон:Sfn. Томас Сааті пізніше з'ясував, що верхня межа досягається для Шаблон:Math, а Пен і Ріхтер (Pan, Richter) показали, що вона досягається і для Шаблон:Math

Якщо дозволені тільки прямолінійні дуги, потрібна більша кількість схрещень. Число прямолінійних перетинів для графів Шаблон:Math — Шаблон:Math одно — Шаблон:Math (Шаблон:OEIS). Значення для графів відомі аж до Шаблон:Math . Для Шаблон:Math потрібно або 7233, або 7234 перетинів. Подальші значення збираються в проєкті «Число прямолінійних схрещень»Шаблон:Sfn. Цікаво, що невідомо, чи є звичайне і прямолінійне число схрещень тим же самим для повних двочасткових графів. Якщо гіпотеза Заранкевича вірна, то формула для числа схрещень повного графа асимптотично вірнаШаблон:Sfn, тобто,

$\underset{p\to \mathrm{\infty }}{\lim }\text{cr}(K_p)\frac{64}{p^4}=1.$

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

Шаблон:Нп, сформульована Міхаелем Альбертсоном (Michael O. Albertson) в 2007 році, стверджує, що серед всіх графів з хроматичним числом Шаблон:Mvar, повний граф Шаблон:Mvar має мінімальне число схрещень. Тобто, якщо гіпотеза Гая — Сааті про число перетинів повного графа вірна, будь-який Шаблон:Mvar-хроматичний граф має число перетинів як мінімум рівне з формулою в гіпотезі. Відомо, що це виконується для Шаблон:MathШаблон:Sfn.

Складність

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

Однак існують ефективні алгоритми визначення, що число схрещень не перевищує фіксованої константи Шаблон:Mvar. Іншими словами, задача є вирішуваною з фіксованим параметромШаблон:SfnШаблон:Sfn. Вона залишається складною для великих k, таких як |V|/2. Існують також ефективні апроксимаційні алгоритми для оцінки Шаблон:Math на графах з обмеженим ступенемШаблон:Sfn. На практиці використовуються евристистичні алгоритми, такі як простий алгоритм, починаючи з графа без ребер і поступово додаючи ребра так, щоб отримати мінімальне можливе додаткове число перетинів. Цей алгоритм використовується в програмі проекту розподілених обчислень «Число прямолінійних перетинів».

Число перетинів кубічних графів

Найменші кубічні графи з числом перетинів 1-8 відомі (Шаблон:OEIS).

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

1 — Повний дводольний граф Шаблон:Math із 6 вершинами.

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

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

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

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

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

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

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

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

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

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

Для неорієнтованих простих графів Шаблон:Mvar з Шаблон:Mvar вершинами та Шаблон:Mvar ребрами, таких що Шаблон:Math маємо:

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

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

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

Для графів з великим обхватом Шаблон:Math, Шаблон:Math, Пах, Спенсер і ТойШаблон:Sfn показали поліпшення цієї нерівності.

$\mathrm{cr}(G)\ge c_r\frac{e^{r+2}}{n^{r+1}}.$

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

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

$\mathrm{cr}(G)\ge e-3n.$

Для доказу уявімо малюнок графа Шаблон:Mvar з Шаблон:Math схрещеннями. Кожний такий перетин можна видалити разом з видаленням ребра з Шаблон:Mvar схрещеннями. Таким чином ми можемо знайти граф щонайменше з Шаблон:Math ребрами і Шаблон:Mvar вершинами з нульовим числом перетинів, а отже, це буде планарний граф. Але з формули Ейлера, ми повинні мати Шаблон:Math, звідки отримуємо необхідну нерівність. (Фактично, ми маємо Шаблон:Math Шаблон:Math).

Для отримання нерівності числа перетинів ми застосовуємо вірогідну аргументацію. Нехай Шаблон:Math — імовірний параметр, який буде обраний пізніше. Побудуємо випадковий підграф Шаблон:Mvar графа Шаблон:Mvar шляхом розташування кожної вершини Шаблон:Mvar в Шаблон:Mvar незалежно з імовірністю Шаблон:Mvar і кожне ребро Шаблон:Mvar буде перебувати в Шаблон:Mvar тоді і тільки тоді, коли обидві вершини ребра лежать в Шаблон:Mvar. Нехай Шаблон:Mvar і Шаблон:Math позначають число ребер, вершин і перетинів графа Шаблон:Mvar відповідно. Оскільки Шаблон:Mvar є підграфом графа Шаблон:Mvar, його діаграма міститься в діаграмі Шаблон:Mvar. За попередньою нерівністю числа перетинів маємо:

${\mathrm{cr}}_H\ge e_H-3n_H.$

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

$𝐄[{\mathrm{cr}}_H]\ge 𝐄[e_H]-3𝐄[n_H].$

Оскільки кожна з Шаблон:Mvar вершин Шаблон:Mvar має ймовірність Шаблон:Mvar потрапити в Шаблон:Mvar, отримаємо Шаблон:Math. Таким же чином, кожне ребро Шаблон:Mvar має ймовірність Шаблон:Math залишитися в Шаблон:Mvar, оскільки обидва кінці повинні знаходитися в Шаблон:Mvar. Таким чином, Шаблон:Math. Нарешті, кожен перетин на діаграмі Шаблон:Mvar має ймовірність Шаблон:Math залишитися в Шаблон:Mvar, оскільки кожний перетин залучає чотири вершини. Щоб це зрозуміти, наведемо діаграму Шаблон:Mvar Шаблон:Math перетинами. Можемо припустити, що будь-які два ребра на цій схемі із загальною вершиною не перетинаються, в іншому випадку обмінюємо частини ребер до перетину і число перетинів зменшується на одне. Таким чином, можна вважати, що перетин залучає чотири різні вершини графа Шаблон:Mvar. Внаслідок цього, Шаблон:Math і ми отримуємо:

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

Тепер, якщо ми покладемо Шаблон:Math (оскільки ми припустили, що Шаблон:Math), після деяких алгебраїчних викладок, отримаємо:

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

Невелика зміна наведеної аргументації дозволяє замінити Шаблон:Math Шаблон:Math Шаблон:MathШаблон:Sfn.

Див. також

• 1-планарний граф
• Шаблон:Нп

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття