Гамільтонів граф

Гамільтонів цикл у додекаедрі.

Га́мільтонів гра́ф — в математиці це граф, що містить гамільтонів цикл.

Га́мільтонів шля́х — шлях, що містить кожну вершину графу рівно один раз. Гамільтонів шлях, початкова і кінцева вершини якого збігаються, називається гамільтоновим циклом.

Гамільтонові шлях, цикл і граф названі на честь ірландського математика Вільяма Гамільтона, який вперше визначив ці класи, дослідивши задачу «навколосвітньої подорожі» по додекаедру, вузлові вершини якого символізували найбільші міста Землі, а ребра — дороги, що їх з'єднують.

Хоч вони й названі на честь Гамільтона, гамільтонові цикли в многогранниках раніше вивчав Шаблон:Нп, який, зокрема, навів приклад многогранника без гамільтонових циклів. Ще раніше гамільтонові цикли і шляхи в графі ходів коня на шахівниці, маршрути коня, вивчав індійський математик IX століття Шаблон:Нп, і приблизно в той самий час арабський математик Шаблон:Нп. У XVIII столітті в Європі маршрут коня публікували Абрахам де Муавр і Леонард Ейлер.

Задачу знаходження гамільтонового циклу можна використати як основу для доведення з нульовим пізнанням.

Умови існування

Умова Дірака (1952)

Нехай $p$ — число вершин в даному графі; якщо степінь кожної вершини не менший, ніж $\frac{p}{2}$, то граф називається графом Дірака. Граф Дірака — гамільтонів.

Умова Оре (1960)

$p$ — число вершин у даному графі. Якщо для будь-якої пари несуміжних вершин $x$, $y$ виконано нерівність $d(x)+d(y)⩾p,$ то граф називаваєтся графом Оре (словами: сума степенів будь-яких двох несуміжних вершин не менша від загального числа вершин у графі). Граф Оре — гамільтонів.

Умова Бонді — Хватала

Теорема Бонді — Хватала узагальнює твердження Дірака і Оре. Спочатку визначимо замикання графу. Нехай у графу $G$ є $p$ вершин. Тоді замикання $cl(G)$ однозначно будується за G додаванням для всіх несуміжних вершин $x$ і $y$, у яких виконується $d(x)+d(y)⩾p$, нового ребра $uv$.

Граф є гамільтоновим тоді і тільки тоді, коли його замикання — гамільтонів граф.

Приклади

• Будь-який повний граф є гамільтоновим.
• Усі цикли є гамільтоновими графами.
• Усі правильні многогранники є гамільтоновими графами.

Див. також

• Гамільтонів розклад
• Гамільтонове доповнення
• Гіпотеза Ловаса про гамільтонів цикл
• Граф ходів коня
• Ікосіан
• Панциклічний граф
• Платонів граф

Джерела

• Bollobás, B. Graph Theory: An Introductory Course. New York: Springer-Verlag, 1979.
• Chartrand, G. Introductory Graph Theory. New York: Dover, 1985.

Посилання

• Шаблон:Cite web — задачі про гамільтонові шляхи і цикли]