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

2014-09-28T08:47:05Z

178.70.145.12: Добавлен перевод

[[Файл:Hamiltonial.png|300px|thumb|right|Граф додекаэдра с выделенным циклом Гамильтона]]
==Основные определения==
{{Определение
|definition =
'''Гамильтоновым путём''' (англ. ''Hamiltonian path'') называется простой путь, приходящий через каждую вершину графа ровно один раз.
}}

{{Определение
|definition =
'''Гамильтоновым циклом''' (англ. ''Hamiltonian cycle'') называют замкнутый гамильтонов путь.
}}

{{Определение
|definition =
Граф называется '''полугамильтоновым''' (англ. ''Semihamiltonian graph''), если он содержит гамильтонов путь.
}}

{{Определение
|definition =
Граф называется '''гамильтоновым''' (англ. ''Hamiltonian graph''), если он содержит гамильтонов цикл.
}}

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

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

===[[Теорема Дирака|Теорема Дирака]]===
{{Теорема
|statement=
Если <tex>n \ge 3</tex> и <tex>deg\ v \ge n/2</tex> для любой вершины <tex>v</tex> неориентированного графа <tex>G</tex>, то <tex>G</tex> - гамильтонов граф.
}}
===[[Теорема Оре|Теорема Оре]]===
{{Теорема
|statement=
Если <tex>n \ge 3</tex> и <tex>deg\ u + deg\ v \ge n</tex> для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> неориентированного графа <tex>G</tex>, то <tex>G</tex> - гамильтонов граф.
}}
===[[Теорема_Редеи-Камиона|Теорема Редеи-Камиона]]===
{{Теорема
|statement=
Любой сильносвязный [[Турниры|турнир]] - гамильтонов.
}}

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

{{Теорема
|about=
Ghouila-Houri
|statement=
Пусть G - сильносвязный ориентированный граф. <br>
<tex>

\begin{matrix}
deg^+ v \geq n/2 \\
deg^- v \geq n/2 \\

\end{matrix} \Bigg\} \rightarrow

</tex> G - гамильтонов.
}}

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

===Теорема Поша===
{{Теорема
|statement=
Пусть граф G имеет <tex>n \geq 3</tex> вершин. Если для всякого <tex>k,\, 1 \leq k < (n-1)/2</tex> число вершин со степенями, не превосходящими <tex>k</tex>, меньше чем <tex>k</tex>, и для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>, то G - гамильтонов граф.
}}

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

Приведём два алгоритма поиска гамильтонова цикла.

bool check_hamiltonian(graph g, bool[] used, int vert, int count, int[] next):
if (count == g.vertices):
next[vert] = 0
return (vert; 0) in g.edges
for (i = 0; i < g.vertices; i++):
if (!used[i] && (vert; i) in g.edges):
used[i] = true
next[vert] = i
if (check_hamiltonian(g, used, i, count + 1, next)):
return true
used[i] = false
return false

* used — отметки о посещении
* vert — текущая вершина
* count — количество посещённых вершин

Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины в ещё не посещённые. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером 0 и параметром count = 1. Если процедура возвращает true, то в массиве next будет храниться следующая вершина на гамильтоновом цикле. Этот алгоритм в худшем случае перебирает <tex>(n - 1)!</tex> путей, что даёт сложность работы <tex>O(n!)</tex>.

Приведём алгоритм, основанный на динамическом программировании, который работает значительно быстрее. Алгоритм основан на следующей идее: будем для каждой пары из подмножества вершин и вершины считать, существует ли гамильтонов путь для этого подмножества вершин, заканчивающихся в выделенной вершине. Суммарно таких состояний будет <tex>O(n2^n)</tex>, для обсчёта каждого из них требуется <tex>O(n)</tex> времени, то есть, суммарно алгоритм работает за <tex>O(n^22^n)</tex> времени. Псевдокод, реализующий этот алгоритм, приведён ниже:

bool[][] get_dp_table(graph g):
int n = g.vertices
bool[][] result = new int[1 << n][n];
for (int i = 0; i < n; i++):
result[1 << i][i] = (0; i) in g.edges;
for (int i = 1; i < (1 << n); i++):
if (count(i) == 1):
continue
for (int j = 0; j < n; j++):
if ((1 << j) & i != 0):
for (int k = 0; k < n; k++):
if (k != j && (1 << k) & i != 0):
result[i][j] = result[(1 << j) ^ i][k] && (k; j) in g.edges
return result

В приведённом выше коде считаем, что n меньше количества бит в числовом типе данных, для операций над множествами используются побитовые логические операции в синтаксисе языка C. Функция count считает количество единичных бит в числе (она проста в реализации, но не относится к алгоритма, поэтому не приводится). Граф гамильтонов тогда, когда dp[(1 << n) - 1][i] && (i; 0) <tex>\in</tex> g.edges для некоторого i.

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

[[Категория:Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]

Викиконспекты - Вклад участника [ru]

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