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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Гамільтонів цикл у додекаедрі.

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

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

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

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

Умови існування[ред.ред. код]

Умова Дірака (англ.) (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.