28. Гамильтонов граф. Достаточные признаки существования гамильтонова цикла (связь с полнотой цикла, теоремы Оре и Дирака). Полугамильтонов граф.

Г раф называется гамильтоновым, если для каждой вершины графа найдется маршрут начинающейся и заканчивающей в этой вершине и проходящий через все вершины только один раз. Такой маршрут называется гамильтоновым циклом.

Достаточный признак существования Гам.графа – любой полный граф является гамильтоновым.

Теорема Оре. Если число вершин n≥3 и для любой пары несмежных вершин сумма степеней d(x_i)+d(x_j) ≥n, граф будет гамильтовым.

n=4≥3 d(x_i)= d(x_j)=2 d(x_i)+d(x_j)=4 достаточный признак выполнен.

Теорема Дирака. Если число вершин n≥3 степень d(x_i) ≥n/2, граф будет гамильтоновым.n=4≥3 d(a)=2, d(c)=2=4/2 d(b)= d(d)=3≥4/2 => граф гамильтоновый.

Полугамильтонов граф — граф, который содержит простую цепь, проходящую через каждую его вершину. Всякий гамильтонов граф является полугамильтоновым.