Изменения

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

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

Пусть {{Лемма|statement=Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>S= \v_1v_i, v_2v_{ i+1} \in E</tex>, такая вершина действительно существует.| \mathrm{e}_i proof=Рассмотрим множество <tex>S = \mathrm{v}_1 i\mathrm{v}_i mid v_1v_i \in \mathbb{E}\} \subset \{3</tex>, 4состоящее из индексов вершин, ...,n\}смежных с <tex>v_1</tex> , и множество <tex>T = \{ i| f_i=+1 \mathrm{v}_2 \mathrm{v}_mid v_2v_{i+1} \in E\}</tex>, индексов вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \mathbb{E} 3, 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 \ge geqslant n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует, в зависимости от наших начальных условий. А значит что <tex>S \cap T \ne \varnothing</tex>, следовательно а это и значит, что искомая вершина обязательно найдетсясуществует.Теперь заметим}} {{Лемма|statement=После <tex>n(n - 1)</tex> итераций между каждой парой соседних вершин очереди существует ребро.|proof=Достаточно заметить, что после каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>kv_1</tex>-ой итерации внешнего цикла между всеми парами вершин и <tex>\mathrmv_{v}_{i2}</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, \mathrm{v}_{i+как минимум на <tex>1}</tex>(это прямое следствие условия поиска нужной вершины, где в случае отсутствия ребра), для поиска такой пары требуется не более <tex>n</tex> итераций. Таких пар изначально не более <tex>i \le kn</tex> существует ребро, а значит откуда следует, что после <tex>n</tex> итераций мы найдем , второе условие будет выполнено.}} {{Теорема|statement=Алгоритм находит гамильтонов цикл.|proof=Из предыдущих лемм следует корректность алгоритма.}}

Алгоритм Поиск вершины, удовлетворяющей заданному условию работает за <tex>O(n^2)</tex>. Действительно, количество итераций внешнего цикла а таких поисков будет осуществлено не более чем <tex>\mathrm{for}n</tex> всегда равно . Оставшиеся <tex>n(n - 12)</tex>, во внутреннем цикле, в худшем случае, будет выполнено итерации выполняются за <tex>n - 2O(1)</tex> итерации, получаем время работы .Тогда алгоритм выполняется за <tex>O(n^2)</tex>.