Граф Гершеля
У теорії графів граф Гершеля — двочастковий неорієнтований граф із 11 вершинами і 18 ребрами, найменший негамільтонів поліедральний граф. Граф названо на честь британського астронома А. С. Гершеля[en], який написав ранню роботу з приводу гри «Ікосіан» Вільяма Ровена Гамільтона — граф Гершеля дає найменший опуклий многогранник, для якого гра не має розв'язку. Однак стаття Гершеля описує розв'язок для гри «Ікосіан» тільки для тетраедра та ікосаедра, і не описує графа Гершеля[1].
Властивості ред.
Граф Гершеля планарний — його можна намалювати на площині без перехрещення ребер. Він також 3-вершинно-зв'язний — видалення будь-яких двох вершин залишає підграф зв'язним. Тому, за теоремою Штайніца, граф Гершеля є багатогранним графом — існує опуклий многогранник (еннеаедр), для якого він є скелетом[2]. Граф Гершеля є також двочастковим — його вершини можна розбити на дві підмножини з п'яти і шести вершин так, що кожне ребро матиме кінцеві вершини в обох множинах (червоні та сині підмножини на малюнку).
Як і будь-який інший двочасковий граф, граф Гершеля є досконалим — хроматичне число будь-якого породженого підграфа дорівнює розміру найбільшої кліки цього підграфа. Граф має хроматичний індекс 4, обхват 4, радіус 3 та діаметр 4.
Гамільтоновість ред.
Оскільки граф двочастковий і має непарне число вершин, він не містить гамільтонового циклу (циклу з ребер, який проходить через кожну вершину рівно один раз). У будь-якому двочастковому графі будь-який цикл має поперемінно проходити обидві множини вершин, тому повинен містити однакову кількість вершин обох типів і мати парну довжину. Таким чином, цикл, що проходить через кожну з одинадцяти вершин, не може існувати. Граф є мінімальним негамільтоновим багатогранним графом, хоч би як вимірювався розмір графа — за кількістю вершин, ребер чи граней[3]. Існує інший багатограний граф з 11 вершинами, що не має гамільтонових циклів (а саме, граф Голднера — Харарі), але немає графа з меншим (або рівним) числом ребер[2].
Усі вершини графа Гершеля, крім трьох, мають степінь три. Гіпотеза Тета[4] стверджує, що багатогранний граф, у якому будь-яка вершина має степінь три, має бути гамільтоновим, але її спростував Татт, навівши контрприклад — значно більший граф Татта[5]. Оновлення гіпотези Тета, гіпотеза Барнетте, що будь-який двочастковий 3-регулярний багатогранний граф є гамільтоновим, залишається відкритою[6].
Граф Гершеля є також прикладом багатоганного графа, для якого серединний граф не можна розбити на два гамільтонових цикли, що не перетинаються по ребрах. Серединним графом графа Гершеля є 4-регулярний граф з 18 вершинами, по одній для кожного ребра графа Гершеля. Дві вершини серединного графа суміжні, якщо відповідні ребра графа Гершеля йдуть послідовно на одній із його граней[7].
Алгебричні властивості ред.
Граф Гершеля не вершинно-транзитивний і його повна група автоморфізмів ізоморфна діедральній групі 12 порядку, групі симетрій правильного шестикутника, що включає як обертання, так і відбиття. Будь-яку перестановку його вершин степеня 4 можна подати автоморфізмом графа, і існує ще нетривіальний автоморфізм, що переставляє решту вершин, не зачіпаючи вершин степеня 4.
Характеристичний многочлен графа Гершеля дорівнює .
Примітки ред.
- ↑ A. S. Herschel. Sir Wm. Hamilton's Icosian Game // The Quarterly Journal of Pure and Applied Mathematics. — 1862. — Т. 5. — С. 305.
- ↑ а б H. S. M. Coxeter. Regular Polytopes. — Dover, 1973. — С. 8.
- ↑ David Barnette, Ernest Jucovič. Hamiltonian circuits on 3-polytopes // Journal of Combinatorial Theory. — 1970. — Т. 9, вип. 1. — С. 54—59. — DOI:.
- ↑ P. G. Tait. Listing's Topologie // Philosophical Magazine (5th ser.). — 1884. — Т. 17. — С. 30—46.. Перепечатано в Scientific Papers, Vol. II, стр. 85—98.
- ↑ W. T. Tutte. On Hamiltonian circuits // Journal of the London Mathematical Society. — 1946. — Т. 21, вип. 2. — С. 98—101. — DOI:.
- ↑ Robert Samal. Barnette's conjecture. — the Open Problem Garden, 11 June 2007.
- ↑ J. A. Bondy, R. Häggkvist. Edge-disjoint Hamilton cycles in 4-regular planar graphs // Aequationes Mathematicae. — 1981. — Т. 22, вип. 1. — С. 42—45. — DOI:.
Посилання ред.
- Weisstein, Eric W. Граф Гершеля(англ.) на сайті Wolfram MathWorld.