Изменения

Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа (не важно в каком порядке). Пусть <tex> n = \left | V \right |</tex>. Тогда <tex>n(n -1)</tex> раз будем делать следующую операцию: * Если между ними есть ребро, то переходим к следующей паре вершин Пусть <tex> v_1 </tex> \mathrm{v{---}_} это голова очереди, <tex> v_2 </tex> {i+1} \mathrm{v---}_{i+2}следующая за ней вершина и так далее. Если между первой и второй вершиной в очереди есть ребро в графе <tex>G</tex>, то перемещаем первую вершину в конец очереди и переходим к следующей итерации. * Если же между первой и второй вершиной в очереди ребра нет, то найдем такую вершину <tex>\mathrm{v}_jv_i</tex>, где <tex>i > 2</tex>, такую что , ребра <tex> \mathrm{v}_j \in{\mathbb{V}} \setminus \{ \mathrm{v}_iv_1v_i, \mathrm{v}_v_2v_{i+1} \} in E</tex>(так как у нас для графа выполнена либо [[Теорема Оре|теорема Оре]], и существуют ребра либо [[Теорема Дирака|теорема Дирака]], то такая вершина обязательно найдется; чуть позже докажем это явно). После чего поменяем в очереди местами вершины <tex> \mathrm{v}_i \mathrm{v}_jv_2</tex> и <tex> \mathrm{v}_{i+1} \mathrm{v}_{j+1} v_i</tex>.** Если , <tex>i < j v_3</tex> то перевернем часть перестановки от и <tex> v_{i+-1 }</tex> до , <tex> v_{2+j } </tex> (включительно).** Если и <tex> v_{i > -j }</tex> обменяем в перестановке элементы на позициях , и так далее, пока <tex> (2 + j < i + 1 + k)\ mod\ n - j</tex> и (то есть <tex> (j - k +n)\ mod\ n </tex>, где пробегает все значения от <tex>k = \overline{0, (j + n - i)\ div\ 2}</tex>до значения заданного неравенством). НапримерТеперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, если это та, которая была до разворота на <tex>n = 10, i = 8, j = 1</tex>-й позиции), а также, то гарантированно существует ребро между <tex>\mathrm{v}_9 i</tex> -й и <tex>\mathrm{v}_1(i+1)</tex> поменяются местами-й вершинами очереди. После этого, так же как и в первом случае, а оправляем первую вершину в конец очереди. Таким образом после <tex>\mathrm{v}_{10}n</tex> останется на местеитераций, мы получаем последовательность (вершины лежащие в очереди), где любые 2 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а также существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу.

'''function''' findHamiltonianCycle(<tex>\left \langle {V, E} \right \rangle</tex>): '''for ''' <tex>v_i v \in P V</tex> : <font color = "green">//перебираем Добавляем все вершины перестановки графа в очередь</font> queue.pushBack(<tex>Pv</tex>) '''for''' k = 0..n * (n - 1) '''if ''' (queue.at(0), queue.at(1)) <tex> v_i v_{i+1} \notin \mathbb{E} </tex> <font color = "green">//если нет Проверяем существования ребра между первой и второй вершинами очереди<tex/font>v_i v_{ i = 2 '''while''' (queue.at(0), queue.at(i+1} )) </tex> for \notin E</tex>v_j \in \mathbb{V} \setminus \{v_i'''or''' (queue.at(1), v_{queue.at(i + 1}\}</tex> //перебираем все остальные вершины if )) <tex>v_i v_j \in \mathbb{notin E}\</tex> && <tex> v_{ i+1} v_{j+1} \in \mathbb{E} </texfont color = "green"> //если есть ребра <tex>v_i v_j,\ v_{i+1} v_{j+1} Ищем индекс удовлетворяющую условию вершины</texfont> reverse_subsequencequeue.swapSubQueue(<tex>P1, i+1, j) </texfont color = "green">) //разворачиваем Разворачиваем часть перестановки <tex>P</tex> от i+1 -й до найденной позиции до j break включительно<//переходим к следующей итерации внешнего for font> queue.pushBack(queue.top())|width = "310px" | queue.pop()

Пусть {{Лемма|statement=Каждый раз, когда нам надо искать вершину <tex>S=v_i</tex> { , где <tex> i| \mathrm> 2</tex>, такую что <tex>v_1v_i, v_2v_{ei+1}_i = \mathrm{v}_1 \mathrm{v}_i \in \mathbb{E}</tex>}, такая вершина действительно существует.|proof=Рассмотрим множество <tex>S = \{i\subset mid v_1v_i \{3, 4, ...,nin E\}</tex> и , состоящее из индексов вершин, смежных с <tex>T = v_1</tex> { , и множество <tex> i| f_iT =\mathrm{v}_2 i+1 \mathrm{v}_mid v_2v_{i+1} \in E\}</tex>, индексов вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \mathbb{E3, 4, \ldots, n\}</tex> }, а <tex>T \subset \{2, 3, ...\ldots,n-1\}</tex>.Тогда , тогда <tex>S \cup T \subset \{2,3,...\ldots,n\}</tex>, откуда а значит <tex>|\left\vert S \cup T |< \right\vert \leqslant n-1</tex>. Но , в то же время <tex>|\left\vert S|\right\vert +|\left\vert T| \right\vert = \operatorname{deg\ } v_1 + \operatorname{deg} v_2 \ v_2 >=geqslant n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует, в зависимости от наших начальных условий. А значит что <tex>S \cap T \ne \varnothing</tex>, следовательно а это и значит, что искомая вершина обязательно найдетсясуществует.}} {{Лемма|statement=После <tex>n(n - 1)</tex> итераций между каждой парой соседних вершин очереди существует ребро.Поскольку каждый раз|proof=Достаточно заметить, когда у нас нет ребра между двумя обрабатываемыми вершинамичто каждую итерацию алгоритма, мы переворачиваем нашу последовательность так, чтобы после переворота в случае отсутствия ребра, между <tex>\mathrm{v}_i, \mathrm{v}_{i+1}v_1</tex> и <tex>\mathrmv_{v2}_j</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, \mathrm{v}_{j+как минимум на <tex>1}</tex> становились связанными ребром(это прямое следствие условия поиска нужной вершины, тов случае отсутствия ребра), рассмотрев все для поиска такой пары вершин в последовательноститребуется не более <tex>n</tex> итераций. Таких пар изначально не более <tex>n</tex>, мы добьемся тогооткуда следует, что любые две соседние пары вершин после <tex>n</tex>\mathrmитераций, второе условие будет выполнено.}} {v}_i, \mathrm{vТеорема|statement=Алгоритм находит гамильтонов цикл.|proof=Из предыдущих лемм следует корректность алгоритма.}_{i+1} == Сложность алгоритма == Поиск вершины, удовлетворяющей заданному условию работает за <tex>O(n)</tex> будут связаны ребром, а это таких поисков будет осуществлено не более чем <tex>n</tex>. Оставшиеся <tex>n(n - 2)</tex> итерации выполняются за <tex>O(1)</tex>.Тогда алгоритм выполняется за <tex>O(n^2)</tex>. == См.также ==*[[Гамильтоновы графы]]*[[Теорема Оре]]*[[теорема Дирака|Теорема Дирака]]*[[Очередь]] == Источники информации ==*[http://rain.ifmo.ru/cat/view.php/theory/graph-circuits-cuts/hamiltonian-2005 Дискретная математика: Алгоритмы {{---}} Гамильтоновы графы] [[Категория: Алгоритмы и значит что мы нашли цикл.структуры данных]][[Категория: Обходы графов]][[Категория: Гамильтоновы графы]]