Изменения

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

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

Если <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> {{--- }} гамильтонов граф.

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

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

Пусть <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| \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} \geqslant n - k, (*) </tex></center>

Приведём == Задача о коммивояжере == Рассмотрим алгоритм нахождения гамильтонова цикла на примере задачи о коммивояжёре. ==== Описание задачи ===={{Задача|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>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 '''to''' g.vertices '''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''' i = 0 '''to''' n '''result'''[1 << i][i] = (0; i) '''in''' gСм.edges; '''for''' i = 1 '''to''' 1 << n '''if''' (count(i) также == 1) '''continue''' '''for''' j = 0 '''to''' n '''if''' ((1 << j) & i != 0) '''for''' k = 0 '''to''' n '''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.

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

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