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

Основные определения

Определение:

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

Определение:

Гамильтоновым циклом называют замкнутый гамильтонов путь.

Определение:

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

Определение:

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

Очевидно, что любой гамильтонов граф также и полугамильтонов.

Достаточные условия гамильтоновости графа

Теорема Дирака

Теорема:

Если [math]n \ge 3[/math] и [math]deg\ v \ge n/2[/math] для любой вершины [math]v[/math] неориентированного графа [math]G[/math], то [math]G[/math] - гамильтонов граф.

Теорема Оре

Теорема:

Если [math]n \ge 3[/math] и [math]deg\ u + deg\ v \ge n[/math] для любых двух различных несмежных вершин [math]u[/math] и [math]v[/math] неориентированного графа [math]G[/math], то [math]G[/math] - гамильтонов граф.

Теорема Редеи-Камиона

Теорема:

Любой сильносвязный турнир - гамильтонов.

Теорема Гуйя-Ури

Теорема:

Пусть G - сильносвязный ориентированный граф. [math] \begin{matrix} deg^+ v \geq n/2 \\ deg^- v \geq n/2 \\ \end{matrix} \Bigg\} \Rightarrow [/math] G - гамильтонов.

Теорема Хватала

Теорема (Хватал):

Пусть: [math] G [/math] — связный граф, [math] n = |VG| \geq 3 [/math] — количество вершин, [math] d_1 \leq d_2 \leq \ldots \leq d_n [/math] — его последовательность степеней. Тогда если [math] \forall k \in \mathbb N [/math] верна импликация: [math] d_k \leq k \lt n/2 \rightarrow d_{n - k} \geq n - k, (*) [/math] то граф [math] G [/math] гамильтонов.

Теорема Поша

Теорема:

Пусть граф G имеет [math]n \geq 3[/math] вершин. Если для всякого [math]k,\, 1 \leq k \lt (n-1)/2[/math] число вершин со степенями, не превосходящими [math]k[/math], меньше чем [math]k[/math], и для нечетного [math]n[/math] число вершин степени [math](n-1)/2[/math] не превосходит [math](n-1)/2[/math], то G - гамильтонов граф.

Алгорит нахождения гамильтового цикла

Основан на обходе в глубину.

Псевдокод

search_cycle(0, 0, number_of_vertices);
bool search_cycle(int v, int w, int d)
{
   if(w == v)
      return (d == 0);
   visited[v] = true;
   for (t [math]\in[/math] Adj[v])
      if(!visited[t])
         if(search_cycle(t, w, d - 1))
            return true;
   visited[v] = false;
   return false;
}

Источники

• Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
• Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.