Гамильтонов шлях (чорним)
Гамильтонов граф - в теорії графів це граф. містить гамільтоновим ланцюг або гамильтонов цикл.
Гамильтонов шлях (або гамільтонова ланцюг)-шлях (ланцюг), що містить кожну вершину графа рівно один раз. Гамильтонов шлях, початкова і кінцева вершини якого збігаються, називаетсягамільтоновим циклом. Гамильтонов цикл є простим остовне циклом (див. Словник термінів теорії графів).
Гамільтона шлях, цикл і граф названі в честьірландского математика У. Гамільтона. який вперше визначив ці класи, дослідивши задачу «кругосвітньої подорожі» по додекаедрів. вузлові вершини якого символізували найбільші городаЗемлі. а ребра - з'єднують їх дороги.
умови існування
Необхідна умова
Неорієнтовані граф G містить гамільтонів цикл тоді, коли в ньому не існує жодної вершини x (i) з локальної ступенем p (x (i)) <2. Доказательство следует из определения.
Умова Дірака (англ.) (1952)
Нехай p - число вершин в даному графі; якщо ступінь кожної вершини не менше, ніж, то граф називається графом Дірака. Граф Дірака - гамільтонів.
Умова Оре (1960)
p - кількість вершин в даному графі. Якщо для будь-якої пари несуміжних вершин x, y виконано нерівність, то граф називається графом Оре (словами: ступеня будь-яких двох несуміжних вершин не менше загального числа вершин в графі). Граф Оре - гамільтонів.
Теорема Бонді-Хватала
Теорема Бонді-Хватала (англ.) Узагальнює затвердження Дірака і Оре. Для графа G з n вершинами замикання визначається додаванням в G ребра (u, v) для кожної пари несуміжних вершин u і v. сума ступенів яких не менше n.
Граф є гамільтоновим тоді і тільки тоді, коли його замикання - гамільтонів граф.
Умова Пошана
Введемо наступну функцію f (x) цілого невід'ємного аргументу x на графі G = [A, B]:
.
Написане означає, що функція f (x) в кожному цілому неотрицательную x приймає значення, рівне кількості вершин графа G = [A, B], ступінь яких не перевищує x. Таку функцію f (x) називають функцією Пошана графа G.