Гамильтоновы графы

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

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

Гамильтонов граф– граф, обладающий гамильтоновым циклом.

Замечание: Вопрос о существовании гамильтоновых цепей и циклов будем рассматривать на основе обыкновенных графов.

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

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

Опр. G: V₁,V₂,…,V_n

Степени вершин: d₁,d₂,…,d_n.

Упорядочены d₁≤d₂ ≤d₃≤…≤d_n.

Последовательность d₁,d₂,…,d_n – последовательность степеней графа.

d_i =deg V_i

Теория Хватала, 1972 г.

Пусть G – обыкновенный граф.

d₁≤d₂ ≤…≤d_n, n≥3.

Если для k верна импликация , то G – гамильтонов граф.

Следствия: 1) теория Дирака,1952 г.

Пусть G – обыкновенный граф. d₁,d₂,…,d_n, n≥3. Тогда d_k≥ для

2) теорема Оре, 1960 г.

Deg U + deg V ≥ n для любых двух несмежных вершин графа.

3) d_k>k для 1≤k<

Гамильтонова орцепь орграфа – его простая орцепь, которая проходит через каждую его

вершину ровно один раз.

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

раз.

Орграф называется полугамильтоновым , если он содержит гамильтонову орцепь и называется гамильтоновым, если содержит орцикл.

Теория Гуйя-Ури: Пусть G – орсвязный n-орграф.

и , то G – гамильтонов орграф.

Турнир – орграф, основанием которого является полный граф.

Теория Редеи и Камион: Любой турнир - полугамильтонов, любой орсвязный турнир – гамильтонов.