Изменения

[[Файл:Hamiltonial.png|250px300px|thumb|right|Граф додекаэдра с выделенным циклом Гамильтона]]

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

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

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

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

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

Если <tex>n \ge geqslant 3</tex> и <tex>\deg\ u + \deg\ v \ge 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> {{--- }} гамильтонов граф.

Любой сильносвязный [[Турниры|турнир]] {{- --}} гамильтонов.

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

Пусть <tex>G </tex> {{- --}} сильносвязный ориентированный граф. <br>

\deg^+ v \geq geqslant n/2 \\ \deg^- v \geq geqslant n/2 \\

\end{matrix} \Bigg\} \rightarrow Rightarrow

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

* <tex> G </tex> — {{---}} [[Отношение связности, компоненты связности|связный граф]],* <tex> n = |VG| \geq geqslant 3 </tex> — {{---}} количество вершин,* <tex> d_1 \leq leqslant d_2 \leq leqslant \ldots \leq leqslant d_n </tex> — {{---}} его последовательность степеней.

<center><tex> d_k \leq leqslant k < n/2 \Rightarrow d_{n - k} \geq geqslant n - k, (*) </tex></center>

==Задача о коммивояжере == Рассмотрим алгоритм нахождения гамильтонова цикла на примере задачи о коммивояжёре. ==== Описание задачи =Теорема Поша==={{ТеоремаЗадача|statementdefinition =Пусть граф G имеет <tex>n \geq 3</tex> вершин'''Задача о коммивояжере''' (англ. Если для всякого <tex>k,\''Travelling salesman problem, 1 \leq k < (n-1TSP'')/2</tex> число вершин со степенями, не превосходящими <tex>k</tex>— задача, меньше чем в которой коммивояжер должен посетить <tex>kN </tex>городов, побывав в каждом из них ровно по одному разу и для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>завершив путешествие в том городе, то G - гамильтонов графс которого он начал.В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?

==== Варианты решения ==== Задача о коммивояжере относится к классу [[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>d[mask][i]</tex> содержит булево значение — существует ли в подмножестве <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.  Сама динамика будет такая: <br><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>. Тогда динамика перепишется следующим образом: <br><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> мы смотрим на состояния

bool check_hamiltonian(graph g<tex>\langle j, mask - 2^j \rangle</tex>, bool[] usedи <tex>|mask| = |mask - 2^j| + 1</tex>, int vertто состояния с большим <tex>|mask|</tex> должны быть посещены позже, 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

Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины в ещё не посещённые. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером 0 и параметром count = 1=== Алгоритм нахождения гамильтонова цикла ====Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла. Если процедура возвращает true, то в В массиве next будет храниться следующая вершина на гамильтоновом цикле. Этот алгоритм в худшем случае перебирает <tex>(n - 1)!d[i][mask]</tex> путеймы хранили расстояния, что даёт сложность работы но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает <tex>O(n!)true</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.

==Источникиинформации==

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