Изменения

* Если между первой Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа (здесь и далее первая вершина - вершина не важно в голове очередикаком порядке) и второй вершиной в очереди есть ребро в графе <tex>\mathbb{G}</tex>, то перемещаем первую вершину в конец очереди и переходим к следующей итерации.* Если между первой и второй вершиной в очереди ребра нет, то найдем вершину <tex>v_i</tex>, где Пусть <tex>i > 2</tex>, такую что, ребра <tex>v_1v_i, v_2v_{i+1} n = \in left | V \mathbb{E}right |</tex> (так как у нас для графа выполнена либо [[Теорема Оре|теорема Оре]], либо [[Теорема Дирака|теорема Дирака]], то такая вершина обязательно найдется; чуть позже мы это докажем явно). После чего поменяем в очереди местами вершины <tex>v_2</tex> и <tex>v_i</tex>, <tex>v_3</tex> и <tex>v_{i-1}</tex>, <tex>v_{2+j} </tex> и <tex>v_{i-j}</tex>, и так далее, пока <tex>2 + j Тогда < i - j</tex> n(то есть <tex>j</tex> пробегает все значения от 0 до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на <tex>i</tex>n -й позиции), а так же, гарантированно существует ребро между <tex>i</tex>-й и <tex>(i+1)</tex>-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди.раз будем делать следующую операцию:

* Пусть <tex> v_1 </tex> {{---}} это голова очереди, <tex> v_2 </tex> {{---}} следующая за ней вершина и так далее. Если между первой и второй вершиной в очереди есть ребро в графе <tex>G</tex>, то перемещаем первую вершину в конец очереди и переходим к следующей итерации.* Если между первой и второй вершиной в очереди ребра нет, то найдем вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что, ребра <tex>v_1v_i, v_2v_{i+1} \in E</tex> (так как у нас для графа выполнена либо [[Теорема Оре|теорема Оре]], либо [[Теорема Дирака|теорема Дирака]], то такая вершина обязательно найдется; чуть позже докажем это явно). После чего поменяем в очереди местами вершины <tex>v_2</tex> и <tex>v_i</tex>, <tex>v_3</tex> и <tex>v_{i-1}</tex>, <tex>v_{2+j} </tex> и <tex>v_{i-j}</tex>, и так далее, пока <tex>2 + j < i - j</tex> (то есть <tex>j</tex> пробегает все значения от <tex>0</tex> до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на <tex>i</tex>-й позиции), а также, гарантированно существует ребро между <tex>i</tex>-й и <tex>(i+1)</tex>-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди. Таким образом после <tex>n</tex> итераций, мы получаем последовательность (вершины лежащие в очереди), где любые 2 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а так же также существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу.

Queue queue; '''function''' findHamiltonianCycle(<tex>\left \langle {V, E} \right \rangle<// создаем очередьtex>): '''for i ''' <tex> v \in V</tex>: <font color = 0 to n - 1 "green">//Добавляем все вершины графа в очередь</ font> queue.pushbackpushBack(<tex>v[i]</tex>) // добавляем в очередь все вершины графа '''for ''' k = 0 to ..n * (n - 1 // пока не проделано нужное количество итераций) '''if !exist''' (queue.at(0), queue.at(1)) <tex> \notin E</tex> <font color = "green">// проверяем Проверяем существования ребра между первой и второй вершинами очереди</font> i = 2 '''while''' (queue.at(0), queue.at(i)) <tex> \notin E</tex> '''or''' (queue.swapSubQueueat(21), find_vertexqueue.at(i + 1)) <tex> \notin E</tex> i++ <font color = "green">// Ищем индекс удовлетворяющую условию вершины</ еслиfont> queue.swapSubQueue(1, не существует, то меняем порядок вершин в очереди, со второй до i) <font color = "green">// Разворачиваем часть перестановки от 1-й до найденной, удовлетворяющей нас позициивключительно</font> queue.pushBack(queue.top())|width = "310px" | queue.pop()

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

Докажем первое. Рассмотрим множество {{Лемма|statement=После <tex>S = \{i\mid v_1v_i \in \mathbb{E}\}n(n - 1)</tex>итераций между каждой парой соседних вершин очереди существует ребро.|proof=Достаточно заметить, что каждую итерацию алгоритма, состоящее из вершинмы, в случае отсутствия ребра, смежных с между <tex>v_1</tex>, и множество <tex>T = \v_{i+1 \mid v_2v_{i+1} \in \mathbb{E}\2}</tex>, увеличиваем количество пар соседних в очереди вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \{3, 4между которыми есть ребро,...,n\}как минимум на </tex>, а <tex>T \subset \{2, 3,...,n - 1\}</tex>(это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), тогда для поиска такой пары требуется не более <tex>S\cup T\subset \{2, 3,...,n\} </tex>, а значит итераций. Таких пар изначально не более <tex>\left\vert S\cup T\right\vert \le n-1</tex>, в то же время <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \ge n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого откуда следует, что после <tex>S\cap T\ne \varnothingn</tex>итераций, а это и значит, что искомая вершина существуетвторое условие будет выполнено.}}

Для доказательства второй части, достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>v_2</tex> и <tex>v_{2}</tex> увеличиваем количество пар соседних вершин в очереди, как минимум на 1(это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), а такие пар изначально не более <tex>n</tex>{Теорема|statement=Алгоритм находит гамильтонов цикл. Откуда |proof=Из предыдущих лемм следует, что после <tex>n</tex> итераций, второе условие будет выполненокорректность алгоритма.}}

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