Изменения

=== Описание алгоритма ===__TOC__{{ЗадачаАлгоритм находит [[Гамильтоновы графы|Гамильтонов цикл]] в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]] definition = Пусть дан граф <tex> G = \mathbbleft \langle {GV, E} \right \rangle</tex>, если выполняются условия удовлетворяющий условию [[Теорема Оре|Теоремы теоремы Оре]] или выполнена [[Теорема Дирака|теоремы Дирака]]. Рассмотрим перестановку вершин <tex> \mathrm{v}_1 \mathrm{v}_2 ... \mathrm{v}_n</tex>. Если между каждой парой соседних вершин Требуется найти в перестановке существует ребро, то мы получили [[Гамильтоновы графы|Гамильтонов нем гамильтонов цикл]]. В противном случае начнем последовательно рассматривать пары соседних вершин <tex> \mathrm{v}_i \mathrm{v}_{i+1} </tex>, начиная с пары <tex> \mathrm{v}_1 \mathrm{v}_2 </tex>. == Описание алгоритма ==

Если между ними есть ребро, то переходим к следующей паре вершин Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа (не важно в каком порядке). Пусть <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{G}} \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{v}_{j+-1} </tex>.После чего перевернем часть перестановки от , <tex>iv_{2+1 j} </tex> до и <tex> v_{i-j }</tex> (считаем, что наша перестановка зациклиный список).Напримери так далее, если пока <tex>n = 10, 2 + j < i = 8, - j = 1</tex>, где (то есть <tex>n = | \mathbb{V} |j</tex>, то пробегает все значения от <tex>\mathrm{v}_9 0</tex> до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на <tex>\mathrm{v}_1i</tex> поменяются местами-й позиции), а также, гарантированно существует ребро между <tex>\mathrm{v}_{10}i</tex>-й и <tex>(i+1)</tex> останется на месте-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди.

=== Псевдокод ==Функция <tex>\mathtt{findHamiltonianCycle}</tex> получает на вход граф <tex> G </tex > и находит гамильтонов цикл в нем. * <tex> queue </tex> {{---}} очередь вершин графа <tex>G =\left \langle {V, E} \right \rangle</tex>

for(int i = 1; i < n; i++) //перебираем все пары соседних вершин в перестановке if '''function''' findHamiltonianCycle(<tex> v_i v_\left \langle {i+1V, E} \in right \mathbb{G} rangle</tex>) //если есть ребро: continue; '''for''' <tex> v \in V</tex>: <font color = "green">/переходим к следующей паре else /Добавляем все вершины графа в очередь</иначеfont> while queue.pushBack(<tex> v_j \in \mathbb{G} \setminus \{v_i , v_{i+1} \}v</tex>) //перебираем все вершины '''for''' k = 0..n * (n - 1) '''if ''' (queue.at(0), queue.at(1)) <tex>v_i v_j \notin \mathbb{E}\ \mid \mid v_{i+1} v_{j+1} \notin \mathbb{E}</tex>) <font color = "green">//если есть Проверяем существования ребра между первой и второй вершинами очереди</font> i = 2 '''while''' (queue.at(0), queue.at(i)) <tex>v_i v_j\notin E</tex> '''or''' (queue.at(1),\ v_{queue.at(i+1} v_{j+1} )) </tex> swap(\notin E</tex> i+1, j+1 <font color = "green">// Ищем индекс удовлетворяющую условию вершины</texfont> queue.swapSubQueue(1, i); <font color = "green">//разворачиваем нужную Разворачиваем часть перестановки continue; от 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 E</tex>, как сдвиг указателя на начало спискатакая вершина действительно существует. Тогда будем сдвигать указатель на нашу перестановку так|proof=Рассмотрим множество <tex>S = \{i\mid v_1v_i \in E\}</tex>, состоящее из индексов вершин, чтобы она начиналась смежных с рассматриваемой пары <tex>v_1</tex>, и множество <tex>T = \mathrm{v}_i i+1 \mathrm{v}_mid v_2v_{i+1} \in E\}</tex>. Если теперь между первыми двумя вершинами есть ребро, то можем переходить к рассмотрению следующей пары, так как в этом случае мы ничего не делаеминдексов вершин смежных с <tex>v_2</tex>. Если же ребра нет, то докажемЗаметим, что обязательно найдется вершина <tex> S \subset \mathrm{v}_j 3, 4, \in ldots, n\mathbb{V} </tex>, а <tex>T \setminus subset \{2, 3, \ldots, n - 1\mathrm{v}_1</tex>, тогда <tex>S\cup T\subset \mathrm{v}_{2, 3, \ldots, n\}</tex>, а значит <tex>\left\vert S\cup T\right\}vert \leqslant n-1</tex>, такая что в то же время <tex>\mathrmleft\vert S \right\vert + \left\vert T \right\vert = \operatorname{vdeg}_1 v_1 + \mathrmoperatorname{vdeg}_jv_2 \geqslant n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует,что <tex>S\ cap T\mathrmne \varnothing</tex>, а это и значит, что искомая вершина существует.}} {{v}_2 \mathrmЛемма|statement=После <tex>n(n - 1)</tex> итераций между каждой парой соседних вершин очереди существует ребро.|proof=Достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>v_1</tex> и <tex>v_{v2}_{j+</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на <tex>1</tex> (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), для поиска такой пары требуется не более <tex>n</tex> итераций. Таких пар изначально не более <tex>n</tex>, откуда следует, что после <tex>n</tex> итераций, второе условие будет выполнено.}} \in \mathbb {{EТеорема|statement=Алгоритм находит гамильтонов цикл.|proof=Из предыдущих лемм следует корректность алгоритма.}}  == Сложность алгоритма == Поиск вершины, удовлетворяющей заданному условию работает за <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 Дискретная математика: Алгоритмы {{---}} Гамильтоновы графы]

Пусть <tex>S=</tex> { <tex> i| \mathrm{e}_i = \mathrm{v}_1 \mathrm{v}_i \in \mathbb{E}</tex>}<tex>\subset \{3, 4, ...,n\}</tex> [[Категория: Алгоритмы и <tex>T = </tex> { <tex> i| f_i=\mathrm{v}_2 \mathrm{v}_{i+1} \in \mathbb{E}</tex> }<tex>\subset \{2, 3, ...,n-1\}</tex>.структуры данных]]Тогда <tex>S \cup T \subset \{2,3,...,n\}</tex>, откуда <tex>|S \cup T |< n</tex>. Но <tex>|S|+|T| = deg v_1 + deg v_2 >=n</tex> по условию [[Теорема Оре|теоремы ОреКатегория: Обходы графов]] или [[Теорема Дирака|теоремы ДиракаКатегория: Гамильтоновы графы]], в зависимости от наших начальных условий. А значит <tex>S \cap T \ne \varnothing</tex>, следовательно искомая вершина обязательно найдется.Поскольку каждый раз, когда у нас нет ребра между двумя обрабатываемыми вершинами, мы переворачиваем нашу последовательность так, чтобы после переворота <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> и <tex>\mathrm{v}_j, \mathrm{v}_{j+1}</tex> становились связанными ребром, то, рассмотрев, все пары вершин в последовательности, мы добьемся того, что любые две соседние пары вершин <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> будут связаны ребром, а это и значит что мы нашли цикл.