Тадан=== Описание алгоритма ===Алгоритм находит [[Гамильтоновы графы|Гамильтонов цикл]] в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]] <tex> \mathbb{G} </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> \mathrm{v}_{i+1} \mathrm{v}_{i+2}</tex>. Если же ребра нет, то найдем такую вершину <tex>\mathrm{v}_j</tex>, что <tex> \mathrm{j}, \mathrm{v}_j \in{\mathbb{G}} \setminus \{ \mathrm{v}_i, \mathrm{v}_{i+1} \} </tex>, и существуют ребра <tex> \mathrm{v}_i \mathrm{v}_j</tex> и <tex> \mathrm{v}_{i+1} \mathrm{v}_{j+1} </tex>.После чего перевернем часть перестановки от <tex>i+1 </tex> до <tex> j </tex> (считаем, что наша перестановка зациклиный список).Например, если <tex>n = 10, i = 8, j = 1</tex>, где <tex>n = | \mathbb{V} |</tex>, то <tex>\mathrm{v}_9 </tex> и <tex>\mathrm{v}_1</tex> поменяются местами, а <tex>\mathrm{v}_{10}</tex> останется на месте. === Псевдокод ==={| width = 100%|-| for(int i = 1; i < n; i++) //перебираем все пары соседних вершин в перестановке if (<tex> v_i v_{i+1} \in \mathbb{G} </tex>) //если есть ребро continue; //переходим к следующей паре else //иначе while(<tex> v_j \in \mathbb{G} \setminus \{v_i , v_{i+1} \}</tex>) //перебираем все вершины if (<tex>v_i v_j \notin \mathbb{E}\ \mid \mid v_{i+1} v_{j+1} \notin \mathbb{E}</tex>) //если есть ребра <tex>v_i v_j,\ v_{i+1} v_{j+1} </tex> swap(<tex> i+1, j+1</tex>); //разворачиваем нужную часть перестановки continue; //переходим к следующей паре вершин |width = "310px" ||} === Доказательство алгоритма ===Заметим, что поскольку мы сделали нашу перестановку в виде зацикленного списка, то мы можем рассматривать перебор все пар соседних в перестановке вершин, как сдвиг указателя на начало списка. Тогда будет сдвигать указатель на нашу перестановку так, чтобы она начиналась с рассматриваемой пары <tex>\mathrm{v}_i \mathrm{v}_{i+1}</tex>. Если теперь между первыми двумя вершинами есть ребро, то можем переходить к рассмотрению следующей пары, так как в этом случае мы ничего не делаем. Если же ребра нет, то докажем что обязательно найдется вершина <tex> \mathrm{v}_j \in \mathbb{V} \setminus \{\mathrm{v}_1, \mathrm{v}_{2+1}\}</tex>, такая что <tex>\mathrm{v}_1 \mathrm{v}_j,\ \mathrm{v}_2 \mathrm{v}_{j+1} \in \mathbb{E} </tex>. Пусть <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> будут связаны ребром, а это и значит что мы нашли цикл.
