Перегляд вихідного коду сторінки Гамільтонів граф

[[Файл:Hamiltonian path.svg|right|thumb|Гамільтонів цикл у додекаедрі.]]
'''Га́мільтонів гра́ф'''&nbsp;— в [[математика|математиці]] це [[граф (математика)|граф]], що містить гамільтонів цикл.

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

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

Хоч вони й названі на честь Гамільтона, гамільтонові цикли в многогранниках раніше вивчав {{нп|Томас Кіркман|||Thomas Kirkman}}, який, зокрема, навів приклад многогранника без гамільтонових циклів.<ref>{{citation
 | last = Biggs | first = N. L.
 | doi = 10.1112/blms/13.2.97
 | issue = 2
 | journal = The Bulletin of the London Mathematical Society
 | mr = 608093
 | pages = 97–120
 | title = T. P. Kirkman, mathematician
 | volume = 13
 | year = 1981}}.</ref> Ще раніше гамільтонові цикли і шляхи в [[Граф ходів коня|графі ходів коня]] на [[Шахівниця|шахівниці]], [[Задача про хід коня|маршрути коня]], вивчав індійський математик [[IX століття]] {{нп|Рудрата|||Rudrata}}, і приблизно в той самий час арабський математик {{нп|аль-Адлі|||al-Adli ar-Rumi}}. У [[XVIII століття|XVIII столітті]] в Європі маршрут коня публікували [[Абрахам де Муавр]] і [[Леонард Ейлер]].<ref>{{citation|title=Across the Board: The Mathematics of Chessboard Problems | first=John J.|last=Watkins|publisher=Princeton University Press|year=2004|pages=25–38|chapter=Chapter 2: Knight's Tours | isbn=978-0-691-15498-5}}.</ref>

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

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

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

Нехай <math>p</math>&nbsp;— число вершин в даному графі; якщо [[Степінь вершини (теорія графів)|степінь]] кожної вершини не менший, ніж <math>\frac{p}{2}</math>, то граф називається ''графом Дірака''. Граф Дірака&nbsp;— гамільтонів.

=== Умова Оре (1960) ===

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

=== Умова Бонді&nbsp;— Хватала ===

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

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

== Приклади ==
* Будь-який [[повний граф]] є гамільтоновим.
* Усі цикли є гамільтоновими графами.
* Усі [[правильний многогранник|правильні многогранники]] є гамільтоновими графами.

== Див. також ==
* [[Гамільтонів розклад]]
* [[Гамільтонове доповнення]]
* [[Гіпотеза Ловаса про гамільтонів цикл]]
* [[Граф ходів коня]]
* [[Ікосіан]]
* [[Панциклічний граф]]
* [[Платонів граф]]

== Примітки ==
{{reflist}}

== Джерела ==
* ''Bollobás, B.'' Graph Theory: An Introductory Course. New York: Springer-Verlag, 1979.
* ''Chartrand, G.'' Introductory Graph Theory. New York: Dover, 1985.

== Посилання ==
* {{Cite web|title=The Hamiltonian Page|url=https://web.archive.org/web/19980131063501/http://www.densis.fee.unicamp.br/~moscato/Hamilton.html|website=web.archive.org|date=1998-01-31|accessdate=2022-06-23}}&nbsp;— задачі про гамільтонові шляхи і цикли]

[[Категорія:Обчислювальні задачі в теорії графів]]
[[Категорія:NP-повні задачі]]
[[Категорія:Об'єкти теорії графів]]
[[Категорія:Гамільтонові шляхи та цикли| ]]