Примеры графов
•В любом циклическом графе Сn (n>2) существует ровно один гамильтонов цикл
•В графе K2 гамильтонова цикла не существует, но существует гамильтонов путь
•В случае полного графа Kn n>2 имеется (n-1)! гамильтоновых циклов.
Теорема Оре (1960 год). Пусть G – граф, построенный на n>2 вершинах. Если для любой пары несмежных вершин выполняется условие deg(x)+deg(y) ⩾n, то в графе G имеется гамильтонов цикл.
Следствие (Дирак, 1952 год). Пусть G – граф, построенный на n>2 вершинах. Если степень каждой его вершины ⩾ n/2, то в нем существует гамильтонов цикл.
Замыканием C(G) графа G называется граф, полученный из G последовательным соединением в нем ребрами пар несмежных между собой вершин, суммарные степени которых ⩾ n до тех пор, пока ни одной такой пары в графе не останется.
Утверждение. Граф C(G), полученный в результате процедуры замыкания графа G, не зависит от порядка выбора ребер, соединяющих несмежные вершины графа G.
Теорема (Бонди-Хватал, 1976 год). Простой граф является гамильтоновым тогда и только тогда, когда его замыкание является гамильтоновым графом.
Данная теорема является обобщением теорем Оре и Дирака, которые непосредственно следуют из теоремы Бонди-Хватала.
Следствие. Если C(G)= Kn, то G – гамильтонов.
Т
еорема
(Хватал, 1972 год). Пусть G – простой
граф, построенный на n вершинах,
последовательность степеней вершин
которого d1≤ d2≤... ≤dn удовлетворяет
следующему условию: .
Тогда в G существует гамильтонов цикл.
Доказательство. Покажем, что замыкание С(G) графа G является полным графом Kn.
Предположим, что С(G) не является полным графом. Выберем в графе С(G) пару таких несмежных между собой вершин х, у, для которых сумма степеней максимальная: s = deg(x)+deg(y) < n.*
Пусть i := deg(x) < deg(y).
Из * следует:
deg(у) < n – i
i < n/2 => deg(x) < n – i
Любая несмежная с у вершины имеет степень, меньшую или равную deg(x)=i, т.к. выбрали несмежную пару с максимальной суммой степеней.
Т.к. deg(y) ≤ n – 1, то в графе C(G) гарантированно имеется i несмежных с у вершин, степень которых меньше или равна i.
Любая несмежная с х вершина имеет степень, меньшую или равную deg(у) < n – i:
т.к. степень вершины x=i, то в графе существует n-i-1 несмежных с х вершин, степень которых < n - i
кроме того, сама вершина х имеет степень < n - i.
Таким образом мы нашли по меньшей мере n-i вершин в графе C(G), степени которых < n - i.
Заметим, что G есть остовной подграф графа C(G). Поэтому если в C(G) какая-то вершина имеет степень, меньшую некоторого числа, то и в G степень этой вершины не превосходит того же числа.
Следовательно, мы нашли такое i < n / 2, для которого в графе G нашлось как минимум i вершин степени, меньшей или равной i, и n-i вершин, степень которых меньше n-i, а это противоречит условию теоремы.
Действительно, последовательность (d1,…,dn) степеней вершин упорядочена по неубыванию. Значит, первые i из этих чисел меньше или равны i, а следовательно, и i-тое число этой последовательности di<=i.
Аналогично доказывается для dn-i<n-i.
Задачи, связанные с гамильтоновыми циклами
1.Задача коммивояжера
2. Задача о ходе шахматного коня
3. Задача сборки генома