Изменения

Алгоритм находит [[Гамильтоновы графы|гамильтонов цикл]] в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]] <tex> \mathbb{G} = (\mathbb{V}, \mathbb{E}) </tex>, если выполняются условия [[Теорема Оре|теоремы Оре]] или выполнена [[теорема Дирака]]. Рассмотрим перестановку вершин <tex> \mathrm{v}_1 \mathrm{v}_2 ... \mathrm{v}_n</tex>, где <tex>n = | \mathbb{V} |</tex>. Если между каждой парой соседних вершин в перестановке существует ребро, то мы получили [[Гамильтоновы графы|Гамильтонов цикл]]. В противном случае, начиная с пары <tex> \mathrm{v}_1 \mathrm{v}_2 </tex>, начнем последовательно рассматривать пары соседних вершин <tex> \mathrm{v}_i \mathrm{v}_{i+1} </tex>, пока <tex>i \ge n</tex> (Когда < tex>i = n</tex>, за <tex>\mathrm{v}_{i+1}</tex> считаем <tex>\mathrm{v}_{1}</tex>).

** Если <tex> i > j </tex> обменяем в перестановке элементы на позициях <tex> (i + 1 + k)\ \operatorname{mod}\ n </tex> и <tex> (j - k +n)\ \operatorname{mod}\ n </tex>, где <tex>k = \overline{0, (j + n - i)\ \operatorname{div}\ 2}</tex>, то есть считаем <tex>\mathrm{v}_{i}...\mathrm{v}_{j}</tex> равным равной <tex>\mathrm{v}_{i}...\mathrm{v}_{n}\mathrm{v}_{1}...\mathrm{v}_{j}</tex>. Например, если <tex>n = 10, i = 8, j = 1</tex>, то <tex>\mathrm{v}_9 </tex> и <tex>\mathrm{v}_1</tex> поменяются местами, а <tex>\mathrm{v}_{10}</tex> останется на месте.