Га́мільтонів гра́ф — в математиці це граф, що містить гамільтонів цикл.
Га́мільтонів шля́х — шлях, що містить кожну вершину графу рівно один раз. Гамільтонів шлях, початкова і кінцева вершини якого збігаються, називається гамільтоновим циклом.
Гамільтонові шлях, цикл і граф названі на честь ірландського математика Вільяма Гамільтона, який вперше визначив ці класи, дослідивши задачу «навколосвітньої подорожі» по додекаедру, вузлові вершини якого символізували найбільші міста Землі, а ребра — дороги, що їх з'єднують.
Хоч вони й названі на честь Гамільтона, гамільтонові цикли в многогранниках раніше вивчав [en], який, зокрема, навів приклад многогранника без гамільтонових циклів. Ще раніше гамільтонові цикли і шляхи в графі ходів коня на шахівниці, маршрути коня, вивчав індійський математик IX століття [en], і приблизно в той самий час арабський математик [en]. У XVIII столітті в Європі маршрут коня публікували Абрахам де Муавр і Леонард Ейлер.
Задачу знаходження гамільтонового циклу можна використати як основу для доведення з нульовим пізнанням.
Умови існування
Умова Дірака (1952)
Нехай — число вершин в даному графі; якщо степінь кожної вершини не менший, ніж , то граф називається графом Дірака. Граф Дірака — гамільтонів.
Умова Оре (1960)
— число вершин у даному графі. Якщо для будь-якої пари несуміжних вершин , виконано нерівність то граф називаваєтся графом Оре (словами: сума степенів будь-яких двох несуміжних вершин не менша від загального числа вершин у графі). Граф Оре — гамільтонів.
Умова Бонді — Хватала
Теорема Бонді — Хватала узагальнює твердження Дірака і Оре. Спочатку визначимо замикання графу. Нехай у графу є вершин. Тоді замикання однозначно будується за G додаванням для всіх несуміжних вершин і , у яких виконується , нового ребра .
Граф є гамільтоновим тоді і тільки тоді, коли його замикання — гамільтонів граф.
Приклади
- Будь-який повний граф є гамільтоновим.
- Усі цикли є гамільтоновими графами.
- Усі правильні многогранники є гамільтоновими графами.
Див. також
Примітки
- 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.
- Watkins, John J. (2004), Chapter 2: Knight's Tours, Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, с. 25—38, ISBN .
Джерела
- Bollobás, B. Graph Theory: An Introductory Course. New York: Springer-Verlag, 1979.
- Chartrand, G. Introductory Graph Theory. New York: Dover, 1985.
Посилання
- . web.archive.org. 31 січня 1998. Процитовано 23 червня 2022. — задачі про гамільтонові шляхи і цикли]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Ga miltoniv gra f v matematici ce graf sho mistit gamiltoniv cikl Gamiltoniv cikl u dodekaedri Ga miltoniv shlya h shlyah sho mistit kozhnu vershinu grafu rivno odin raz Gamiltoniv shlyah pochatkova i kinceva vershini yakogo zbigayutsya nazivayetsya gamiltonovim ciklom Gamiltonovi shlyah cikl i graf nazvani na chest irlandskogo matematika Vilyama Gamiltona yakij vpershe viznachiv ci klasi doslidivshi zadachu navkolosvitnoyi podorozhi po dodekaedru vuzlovi vershini yakogo simvolizuvali najbilshi mista Zemli a rebra dorogi sho yih z yednuyut Hoch voni j nazvani na chest Gamiltona gamiltonovi cikli v mnogogrannikah ranishe vivchav en yakij zokrema naviv priklad mnogogrannika bez gamiltonovih cikliv She ranishe gamiltonovi cikli i shlyahi v grafi hodiv konya na shahivnici marshruti konya vivchav indijskij matematik IX stolittya en i priblizno v toj samij chas arabskij matematik en U XVIII stolitti v Yevropi marshrut konya publikuvali Abraham de Muavr i Leonard Ejler Zadachu znahodzhennya gamiltonovogo ciklu mozhna vikoristati yak osnovu dlya dovedennya z nulovim piznannyam Umovi isnuvannyaUmova Diraka 1952 Nehaj p displaystyle p chislo vershin v danomu grafi yaksho stepin kozhnoyi vershini ne menshij nizh p 2 displaystyle frac p 2 to graf nazivayetsya grafom Diraka Graf Diraka gamiltoniv Umova Ore 1960 p displaystyle p chislo vershin u danomu grafi Yaksho dlya bud yakoyi pari nesumizhnih vershin x displaystyle x y displaystyle y vikonano nerivnist d x d y p displaystyle d x d y geqslant p to graf nazivavayetsya grafom Ore slovami suma stepeniv bud yakih dvoh nesumizhnih vershin ne mensha vid zagalnogo chisla vershin u grafi Graf Ore gamiltoniv Umova Bondi Hvatala Teorema Bondi Hvatala uzagalnyuye tverdzhennya Diraka i Ore Spochatku viznachimo zamikannya grafu Nehaj u grafu G displaystyle G ye p displaystyle p vershin Todi zamikannya c l G displaystyle cl G odnoznachno buduyetsya za G dodavannyam dlya vsih nesumizhnih vershin x displaystyle x i y displaystyle y u yakih vikonuyetsya d x d y p displaystyle d x d y geqslant p novogo rebra u v displaystyle uv Graf ye gamiltonovim todi i tilki todi koli jogo zamikannya gamiltoniv graf PrikladiBud yakij povnij graf ye gamiltonovim Usi cikli ye gamiltonovimi grafami Usi pravilni mnogogranniki ye gamiltonovimi grafami Div takozhGamiltoniv rozklad Gamiltonove dopovnennya Gipoteza Lovasa pro gamiltoniv cikl Graf hodiv konya Ikosian Panciklichnij graf Platoniv grafPrimitkiBiggs 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 Watkins John J 2004 Chapter 2 Knight s Tours Across the Board The Mathematics of Chessboard Problems Princeton University Press s 25 38 ISBN 978 0 691 15498 5 DzherelaBollobas B Graph Theory An Introductory Course New York Springer Verlag 1979 Chartrand G Introductory Graph Theory New York Dover 1985 Posilannya web archive org 31 sichnya 1998 Procitovano 23 chervnya 2022 zadachi pro gamiltonovi shlyahi i cikli