Очікує на перевірку

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

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

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

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

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

Хоч вони й названі на честь Гамільтона, гамільтонові цикли в многогранниках раніше вивчав Томас Кіркман[en], який, зокрема, навів приклад многогранника без гамільтонових циклів.[1] Ще раніше гамільтонові цикли і шляхи в графі ходів коня на шахівниці, маршрути коня, вивчав індійський математик IX століття Рудрата[en], і приблизно в той самий час арабський математик аль-Адлі[en]. У XVIII столітті в Європі маршрут коня публікували Абрахам де Муавр і Леонард Ейлер.[2]

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

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

[ред. | ред. код]

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

[ред. | ред. код]

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

Умова Оре (1960)

[ред. | ред. код]

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

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

[ред. | ред. код]

Теорема Бонді — Хватала узагальнює твердження Дірака і Оре. Спочатку визначимо замикання графу. Нехай у графу є вершин. Тоді замикання однозначно будується за G додаванням для всіх несуміжних вершин і , у яких виконується , нового ребра .

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

Приклади

[ред. | ред. код]

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. Biggs, N. L. (1981), T. P. Kirkman, mathematician, The Bulletin of the London Mathematical Society, 13 (2): 97—120, doi:10.1112/blms/13.2.97, MR 0608093.
  2. Watkins, John J. (2004), Chapter 2: Knight's Tours, Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, с. 25—38, ISBN 978-0-691-15498-5.

Джерела

[ред. | ред. код]
  • Bollobás, B. Graph Theory: An Introductory Course. New York: Springer-Verlag, 1979.
  • Chartrand, G. Introductory Graph Theory. New York: Dover, 1985.

Посилання

[ред. | ред. код]
  • The Hamiltonian Page. web.archive.org. 31 січня 1998. Процитовано 23 червня 2022. — задачі про гамільтонові шляхи і цикли]