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

2018-02-27T12:34:51Z

91.144.140.113: /* Основные определения */

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

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

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

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

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

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

===[[Теорема Дирака|Теорема Дирака]]===
{{Теорема
|statement=
Если <tex>n \geqslant 3</tex> и <tex>\deg\ v \geqslant n/2</tex> для любой вершины <tex>v</tex> неориентированного графа <tex>G</tex>, то <tex>G</tex> {{---}} гамильтонов граф.
}}

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

===[[Теорема Поша|Теорема Поша]]===
{{Теорема
|about = Поша
|statement = Пусть граф <tex> G </tex> имеет <tex>n \geqslant 3</tex> вершин и выполнены следующие два условия:

*для всякого <tex>k,\, 1 \leqslant k < (n-1)/2</tex>, число вершин со степенями, не превосходящими <tex>k</tex>, меньше чем <tex>k</tex>;
*для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>,

тогда <tex> G </tex> {{---}} гамильтонов граф.
}}
===[[Теорема_Редеи-Камиона|Теорема Редеи-Камиона]]===
{{Теорема
|statement=
Любой сильносвязный [[Турниры|турнир]] {{---}} гамильтонов.
}}

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

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

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

\end{matrix} \Bigg\} \Rightarrow

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

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

== Задача о коммивояжере ==

Рассмотрим алгоритм нахождения гамильтонова цикла на примере задачи о коммивояжёре.

==== Описание задачи ====
{{Задача
|definition =
'''Задача о коммивояжере''' (англ. ''Travelling salesman problem, TSP'') — задача, в которой коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
}}

==== Варианты решения ====

Задача о коммивояжере относится к классу [[NP-полнота задач о гамильтоновом цикле и пути в графах | NP-полных задач]]. Рассмотрим два варианта решения с экспоненциальным временем работы.

===== Перебор перестановок =====
Можно решить задачу перебором всевозможных [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса | перестановок]]. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.

===== Динамическое программирование по подмножествам (по маскам) =====

Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.
Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости — путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>s = 0 </tex>.

Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>mask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mask</tex>.

Обозначим <tex>d[i][mask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>mask_j = 1</tex> (т.е. <tex>d[i][mask]</tex> уже найденный оптимальный путь от <tex>i</tex>-ой вершины до <tex>0</tex>-ой, проходящий через те вершины, где <tex>mask_j=1</tex>. Если <tex>mask_j=0</tex>,то эти вершины еще не посещены).

Алгоритм поиска цикла будет выглядеть следующим образом:

*Начальное состояние — когда находимся в <tex>0</tex>-й вершине, ни одна вершина не посещена, а пройденный путь равен <tex>0</tex> (т.е. <tex>i = 0</tex> и <tex>mask = 0</tex>).
*Для остальных состояний (<tex>i \ne 0</tex> или <tex>mask \ne 0</tex>) перебираем все возможные переходы в <tex>i</tex>-ую вершину из любой посещенной ранее и выбираем минимальный результат.
*Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).

Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> d[0][2^n-1]</tex> — стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины. Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</tex> времени.

Для того, чтобы восстановить сам путь, воспользуемся соотношением <tex> d[i][mask] = w(i, j) + d[j][mask - 2^j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex>.

===== Оптимизация решения методом динамического программирования =====

Пусть <tex>dp[mask][i]</tex> содержит булево значение — существует ли в подмножества <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.

Сама динамика будет такая: 
<tex>
d[mask][i] = \left\{\begin{array}{llcl}
1&;\ |mask| = 1,\ mask_i = 1\\
\bigvee_{mask[j]=1, (j, i) \in E}\limits d[mask \oplus 2^i][j] &;\ |mask| > 1,\ mask_i= 1 \\
0&;\ otherwise\\
\end{array}\right.
</tex>

Это решение требует <tex>O(2^nn)</tex> памяти и <tex>O(2^nn^2)</tex> времени. Эту оценку можно улучшить, если изменить динамику следующим образом.

Пусть теперь <tex>d'[mask]</tex> хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве <tex>mask</tex>, заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: <tex>d'[mask]</tex> будет равно <tex>\sum_{i \in [0..n-1]}\limits d[mask][i] \cdot 2 ^i </tex>. Для графа <tex>G</tex> выпишем <tex>n</tex> масок <tex>M_i</tex>, для каждой вершины задающие множество вершин, которые связаны ребром в данной вершиной. То есть <tex>M_i = \sum_{j \in [0..n-1]}\limits 2^j \cdot ((i, j) \in E ? 1:0) </tex>.

Тогда динамика перепишется следующим образом: 
<tex>
d'[mask] = \left\{\begin{array}{llcl}
mask &;\ |mask| = 1 \\
\sum_{i \in [0..n-1] \& mask_i=1}\limits 2^i \cdot ((d[mask \oplus 2^i] \& M_i) \neq 0?1:0) &;\ |mask| > 1 \\
0&;\ otherwise\\
\end{array}\right.
</tex>

Особое внимание следует уделить выражению <tex>d[mask \oplus 2^i] \& M_i</tex> . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве <tex>mask</tex> без вершины <tex>i</tex>, а вторая — подмножество вершин, связанных с <tex>i</tex> ребром. Если эти множества пересекаются хотя бы по одной вершине (их <tex>\&</tex> не равен <tex>0</tex>), то, как нетрудно понять, в <tex>mask</tex> существует гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.

Окончательная проверка состоит в сравнении <tex>d[2^n - 1]</tex> c <tex>0</tex>.

Это решение использует <tex>O(2^n)</tex> памяти и имеет асимптотику <tex>O(2^nn)</tex>.

==== Псевдокод ====

Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за <tex>|mask|</tex> количество единиц в маске (иначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния <tex>\langle i, mask \rangle</tex> мы смотрим на состояния

<tex>\langle j, mask - 2^j \rangle</tex>, и <tex>|mask| = |mask - 2^j| + 1</tex>, то состояния с большим <tex>|mask|</tex> должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта.
Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти).

// все переменные используются из описания алгоритма, <tex>\infty</tex> = бесконечность
'''function''' findCheapest(i, mask):
'''if''' d[i][mask] != <tex>\infty</tex>
'''return''' d[i][mask]
'''for''' j = 0 .. n - 1
'''if''' w(i, j) существует '''and''' j-ый бит mask == 1
d[i][mask] = '''min'''(d[i][mask], findCheapest(j, mask - <tex>2^j</tex>) + w(i, j))
'''return''' d[i][mask]

'''function''' start():
'''for''' i = 0 .. n - 1
'''for''' mask = 0 .. <tex>2^n</tex> - 1
d[i][mask] = <tex>\infty</tex>
d[0][0] = 0
ans = findCheapest(0, <tex>2^n</tex> - 1)
'''return''' ans
Дальше ищем сам цикл:
'''function''' findWay():
i = 0
mask = <tex>2^n</tex> - 1
path.push(0)
'''while''' mask != 0
'''for''' j = 0 .. n - 1
'''if''' w(i, j) существует '''and''' j-ый бит mask == 1 '''and''' d[i][mask] == d[j][mask - <tex>2^j</tex>] + w(i, j)
path.push(j)
i = j
mask = mask - <tex>2^j</tex>
'''continue'''

==== Алгоритм нахождения гамильтонова цикла ====
Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла.
В массиве <tex>d[i][mask]</tex> мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает <tex> true</tex>, то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.

==== Алгоритм нахождения гамильтонова пути ====
Алгоритм нахождения гамильтонова пути легко получить, используя алгоритм нахождения гамильтонова цикла. Нужно добавить в граф еще одну вершину и ребра от нее до всех остальных вершин и из всех остальных вершин до неё. И далее запустить алгоритм поиска цикла от новой вершины. В восстановлении пути учтем, что эта вершина лишняя, и не будем записывать её в путь.

== См. также ==

*[[Кратчайший путь в ациклическом графе]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о рюкзаке]]
*[[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]

==Источники информации==
*Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
*Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.
*[http://ru.wikipedia.org/wiki/Гамильтонов_граф Гамильтонов граф]
*[http://ru.wikipedia.org/wiki/Задача_коммивояжёра Задача коммивояжера в русской википедии]
*[http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Задача коммивояжера в немецкой википедии]
*''Романовский И. В.'' Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4

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

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

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