Веретено Мозера
| Веретено Мозера | |
|---|---|
 | |
| Названо на честь | Лео Мозера[en] |
| Вершин | 7 |
| Ребер | 11 |
| Радіус | 2 |
| Діаметр | 2 |
| Обхват | 3 |
| Автоморфізм | 8 |
| Хроматичне число | 4 |
| Хроматичний індекс | 4 |
| Властивості | планарний Граф одиничних відстаней Граф Ламана |
Веретено Мозера (веретено Мозерів, граф Мозера) — неорієнтований граф, названий на честь математиків Лео Мозера[en] та його брата Вільяма[1], має сім вершин і одинадцять ребер. Він є графом одиничних відстаней, що потребує чотири кольори при будь-якому розфарбуванні, і його існування доводить те, що хроматичне число площини не дорівнює трьом.[2]
Називають також на честь Дьєрдя Хайоша[ru], оскільки його можна отримати в результаті побудови Хайоша[en][3], проте назва «граф Хайоша» відноситься також і до інших графів, що мають вигляд трикутника вписаного в шестикутник[4].
Як граф одиничних відстаней, веретено Мозера утворюється двома ромбами з кутами 60 і 120 градусів, так що сторони і короткі діагоналі ромбів утворюють рівносторонні трикутники. Два ромби розташовуються на площині так, що дві вершини їх гострих кутів збігаються, а інша пара вершин гострих кутів розташовується на відстані одиниці. Одинадцять ребер графу — це вісім ребер ромбів, дві короткі діагоналі і ребро між двома гострими вершинами ромбів.
Веретено Мозера можна побудувати тільки з точки зору теорії графів, без посилання на геометричне вкладення, за допомогою конструкції Хайоша, почавши з двох повних графів по чотири вершини в кожному. Побудова видаляє по ребру з кожного повного графу, об'єднує дві вершини віддалених ребер в одну вершину, і додає нове ребро, що з'єднує дві кінцеві вершини віддалених ребер, які залишилися.
Інший спосіб побудови веретена Мозера — це доповнення графу, утвореного із графу шляхом поділу одного з його ребер[5].
Проблема Нельсона — Ердеша — Гадвігера розв'язує задачу, як багато кольорів потрібно для розмальовки точок евклідової площини таким чином, що будь-які дві точки площини, що лежать на відстані одиниця, матимуть різні кольори. Тобто, вона запитує про хроматичне число нескінченного графу, вершини якого — всі точки площини і ребра якого — всі пари точок, що лежать на відстані одиниця.
Веретено Мозера вимагає чотири кольори для будь-якого розфарбування — при будь-якому розфарбуванні в три кольори гострі вершини ромбів матимуть один і той же колір, а тоді ребро, що з'єднує дві гострі вершини ромбів, буде з'єднувати вершини одного кольору. Це протиріччя показує, що трьох кольорів недостатньо і потрібно щонайменше чотири кольори. Достатність чотирьох кольорів для розмальовки веретена Мозера слідує з того факту, що його виродженість дорівнює трьом.
Інше доведення того, що для розмальовки веретена Мозера потрібно чотири кольори, випливає з побудови Хайоша. Обидва повних графи, з яких веретено Мозера утворено, вимагають чотири кольори, а побудова Хайоша зберігає цю властивість. Більш того, будь-яка незалежна множина в веретені Мозера має максимум дві вершини, так що потрібно не менше чотирьох незалежних множин для покриття всіх семи вершин.
Оскільки веретено Мозера є підграфом нескінченного графу одиничних відстаней площини, для розмальовки площини потрібно щонайменше чотири кольори. За теоремою де Брьойна - Ердеша (у припущенні, що аксіома вибору вірна) хроматичне число площини дорівнює максимальному хроматичному числу всіх кінцевих підграфів. До теперішнього часу не знайдено жодного нескінченного графу одиничної довжини, що вимагає більше кольорів для розфарбовки, ніж веретено Мозера. Найбільша верхня межа хроматичного числа площини дорівнює семи, що істотно більше числа кольорів, необхідних для розмальовки веретена Мозера.
Веретено Мозера є планарним, що означає, що його можна намалювати на площині без перетинань. Однак неможливо намалювати веретено Мозера таким чином, що воно буде планарним і графом одиничних відстаней одночасно. Веретено Мозера є також ламановим, що означає, що він утворює мінімальну жорстку систему при вкладенні в площину. Як планарний ламановий граф цей граф є графом з гострокутною псевдотріангуляцією, що означає, що він може бути вкладений в площину таким чином, що зовнішня грань є опуклою оболонкою вкладення і всі внутрішні грані є псевдотрикутниками тільки з трьома опуклими вершинами.[6]
Доповненням графу Мозера є граф без трикутників. Таким чином, вкладення графу Мозера у вигляді графу одиничних відстаней може бути використано для вирішення завдання розташування семи точок на площині таким чином, що будь-які три точки містять щонайменше одну пару, що знаходиться на відстані одиниця.
Додавання будь-якого ребра до веретена Мозера приведе до графу, який не можна вкласти в площину у вигляді графу одиничних відстаней, і в якому не буде існувати гомоморфізму графів веретена Мозера в будь-який менший граф одиничних відстаней. Ці дві властивості веретена Мозера були використані в 2011 році[7], щоб показати, що перевірка графу на існування двовимірного подання у вигляді графу одиничних відстаней є NP-важкою задачею. Доведення використовує перетворення з 3SAT, в якому веретено Мозера використовується як вирішальний пристрій, що встановлює істинність формули.
Веретено Мозера може бути використано також в доведенні результатів в теорії Рамсея для евклідової площині — якщо T є трикутником на площині і всі крапки площини пофарбовані у два кольори (білий і чорний), то або існує трикутник з чорними вершинами, що отримується з T рухом, або існує пара білих точок, що знаходяться на відстані одиниця. Для доведення використовується вкладення M веретена Мозера в площину, при якому всі ребра мають довжину одиниця. Нехай М+Т — це сума Мінковського множини М та вершин трикутника Т. Якщо в М+Т немає білих точок, що знаходяться на відстані одиниця, то кожна з трьох копій веретена Мозера в M + T повинна мати максимум дві білі вершини, оскільки білі вершини повинні утворити незалежну множину, а максимальна незалежна множина в веретені Мозера має розмір два. Таким чином, серед семи вершин веретена Мозера максимум шість можуть мати білі вершини з M + T, так що щонайменше всі копії однієї з вершин повинні бути чорними. Ось вони і утворюють трикутник, що виходить з T рухом.
- ↑ L. Moser. Solution to problem 10 // Can. Math. Bull.. — 1961. — Т. 4. — С. 187–189.
- ↑ Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, New York: Springer, с. 14—15, ISBN 978-0-387-74640-1.
- ↑ J. A. Bondy, U. S. R. Murty. Graph Theory // Springer. — 2008. — С. 358. — DOI:.
- ↑ Claude Berge. Minimax relations for the partial q-colorings of a graph // Discrete Mathematics. — 1989. — Т. 74. — С. 3–14. — DOI:.
- ↑ Severino V. Gervacio, Yvette F. Lim, Hiroshi Maehara. Planar unit-distance graphs having planar unit-distance complement // Discrete Mathematics. — 2008. — Т. 308. — С. 1973–1984. — DOI:.
- ↑ Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley. Planar minimally rigid graphs and pseudo-triangulations // Computational Geometry Theory and Applications. — 2005. — Т. 31. — С. 31–61. — DOI:.
- ↑ Horvat, Kratochvíl, Pisanski, 2011.
- Soifer, Alexander. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. — New York : Springer, 2008. — С. 14–15. — ISBN 978-0-387-74640-1.
- G. Hajós. Über eine Konstruktion nicht n-färbbarer Graphen // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. — 1961. — С. 116-117.
- Jeffrey Burkert, Peter Johnson. Ramsey theory. — New York : Birkhäuser/Springer, New York, 2011. — С. 97–113.
- Boris Horvat, Jan Kratochvíl, Tomaž Pisanski. Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers. — 2011. — Т. 6460. — С. 274–285. — ISBN 10.1007/978-3-642-19222-7_28.
- Peter Winkler. Puzzled: Distances Between Points on the Plane // Communications of the ACM. — 2011. — Т. 54. — DOI:.
- Weisstein, Eric W. Moser Spindle(англ.) на сайті Wolfram MathWorld.