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

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

Гамільто́нів гра́ф - в математиці це граф, що містить гамільтонів шлях або гамільтонів цикл.

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

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

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

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

Умова Дірака (англ.) (1952)

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

Умова Оре (1960)

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

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

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

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

Приклади

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

Посилання

• Задачі про гамільтонові шляхи і цикли (посилання бите)

Джерела

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