|
Граф Гершеля У теорії графів граф Гершеля — двочастковий неорієнтований граф із 11 вершинами і 18 ребрами, найменший негамільтонів поліедральний граф. Граф названо на честь британського астронома А. С. Гершеля[en], який написав ранню роботу з приводу гри «Ікосіан» Вільяма Ровена Гамільтона — граф Гершеля дає найменший опуклий многогранник, для якого гра не має розв'язку. Однак стаття Гершеля описує розв'язок для гри «Ікосіан» тільки для тетраедра та ікосаедра, і не описує графа Гершеля[1]. ВластивостіГраф Гершеля планарний — його можна намалювати на площині без перехрещення ребер. Він також 3-вершинно-зв'язний — видалення будь-яких двох вершин залишає підграф зв'язним. Тому, за теоремою Штайніца, граф Гершеля є багатогранним графом — існує опуклий многогранник (еннеаедр), для якого він є скелетом[2]. Граф Гершеля є також двочастковим — його вершини можна розбити на дві підмножини з п'яти і шести вершин так, що кожне ребро матиме кінцеві вершини в обох множинах (червоні та сині підмножини на малюнку). Як і будь-який інший двочасковий граф, граф Гершеля є досконалим — хроматичне число будь-якого породженого підграфа дорівнює розміру найбільшої кліки цього підграфа. Граф має хроматичний індекс 4, обхват 4, радіус 3 та діаметр 4. ГамільтоновістьОскільки граф двочастковий і має непарне число вершин, він не містить гамільтонового циклу (циклу з ребер, який проходить через кожну вершину рівно один раз). У будь-якому двочастковому графі будь-який цикл має поперемінно проходити обидві множини вершин, тому повинен містити однакову кількість вершин обох типів і мати парну довжину. Таким чином, цикл, що проходить через кожну з одинадцяти вершин, не може існувати. Граф є мінімальним негамільтоновим багатогранним графом, хоч би як вимірювався розмір графа — за кількістю вершин, ребер чи граней[3]. Існує інший багатограний граф з 11 вершинами, що не має гамільтонових циклів (а саме, граф Голднера — Харарі), але немає графа з меншим (або рівним) числом ребер[2]. Усі вершини графа Гершеля, крім трьох, мають степінь три. Гіпотеза Тета[4] стверджує, що багатогранний граф, у якому будь-яка вершина має степінь три, має бути гамільтоновим, але її спростував Татт, навівши контрприклад — значно більший граф Татта[5]. Оновлення гіпотези Тета, гіпотеза Барнетте, що будь-який двочастковий 3-регулярний багатогранний граф є гамільтоновим, залишається відкритою[6]. Граф Гершеля є також прикладом багатоганного графа, для якого серединний граф не можна розбити на два гамільтонових цикли, що не перетинаються по ребрах. Серединним графом графа Гершеля є 4-регулярний граф з 18 вершинами, по одній для кожного ребра графа Гершеля. Дві вершини серединного графа суміжні, якщо відповідні ребра графа Гершеля йдуть послідовно на одній із його граней[7]. Алгебричні властивостіГраф Гершеля не вершинно-транзитивний і його повна група автоморфізмів ізоморфна діедральній групі 12 порядку, групі симетрій правильного шестикутника, що включає як обертання, так і відбиття. Будь-яку перестановку його вершин степеня 4 можна подати автоморфізмом графа, і існує ще нетривіальний автоморфізм, що переставляє решту вершин, не зачіпаючи вершин степеня 4. Характеристичний многочлен графа Гершеля дорівнює . Примітки
Посилання
|
