Изменения

Если между ними есть ребро, то переходим к следующей паре вершин Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа (не важно в каком порядке). Пусть <tex> n = \mathrm{v}_{i+1} left | V \mathrm{v}_{i+2}right |</tex>. Тогда <tex>n(n -1)</tex> раз будем делать следующую операцию:

* Пусть <tex> v_1 </tex> {{---}} это голова очереди, <tex> v_2 </tex> {{---}} следующая за ней вершина и так далее. Если же между первой и второй вершиной в очереди есть ребро в графе <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>v_2</tex> и существуют ребра <tex> \mathrm{v}_i \mathrm{v}_jv_i</tex>, <tex>v_3</tex> и <tex> \mathrm{v}_v_{i+-1} \mathrm</tex>, <tex>v_{v2+j}_</tex> и <tex>v_{i-j+1} </tex>.После чего перевернем часть перестановки от , и так далее, пока <tex>2 + j < i+1 - j</tex> до (то есть <tex> j </tex> включительнопробегает все значения от <tex>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 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а также существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу.

i = 1 for i < n //перебираем все пары соседних вершин в перестановке if '''function''' findHamiltonianCycle(<tex> v_i v_{i+1} \in left \mathbblangle {V, E} \right \rangle</tex> //если есть ребро continue //переходим к следующей паре else //иначе): '''for ''' <tex>v_j v \in \mathbb{V} \setminus \{v_i, v_{i + 1}\}</tex> : <font color = "green">//перебираем Добавляем все вершиныграфа в очередь</font> if queue.pushBack(<tex>v</tex>v_i v_j \in \mathbb{E}\ \mid \mid v_{i+) '''for''' k = 0..n * (n - 1} v_{j+) '''if''' (queue.at(0), queue.at(1} )) <tex> \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> swap(\notin E</tex> '''or''' (queue.at(1), queue.at(i+1, j</tex>) //разворачиваем часть перестановки от ) <tex>\mathrm{i}+1 notin E</tex> до i++ <texfont color = "green">\mathrm{j} // Ищем индекс удовлетворяющую условию вершины</texfont> continue queue.swapSubQueue(1, i) <font color = "green">//переходим к следующей паре вершин Разворачиваем часть перестановки от 1-й до найденной позиции включительно</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 >=\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 Дискретная математика: Алгоритмы {{---}} Гамильтоновы графы] [[Категория: Алгоритмы и значит что мы нашли цикл.структуры данных]][[Категория: Обходы графов]][[Категория: Гамильтоновы графы]]