71
правка
Изменения
→Описание алгоритма
__TOC__
== Описание алгоритма ==
Алгоритм находит [[Гамильтоновы графы|гамильтонов цикл]] в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]] <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}_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{v}_j \in{\mathbb{V}} \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> останется на месте.
== Псевдокод ==
