Изменения

Алгоритм находит [[Гамильтоновы графы|Гамильтонов цикл]] в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]] <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>.

{| width = 100%

|-

|}

Заметим, что поскольку мы сделали нашу перестановку в виде зацикленного списка, то мы можем рассматривать перебор все пар соседних в перестановке вершин, как сдвиг указателя на начало списка. Тогда будем сдвигать указатель на нашу перестановку так, чтобы она начиналась с рассматриваемой пары <tex>\mathrm{v}_i \mathrm{v}_{i+1}</tex>. Если теперь между первыми двумя вершинами есть ребро, то можем переходить к рассмотрению следующей пары, так как в этом случае мы ничего не делаем. Если же ребра нет, то докажем, что обязательно найдется вершина <tex> \mathrm{v}_j \in \mathbb{V} \setminus \{\mathrm{v}_1, \mathrm{v}_{2}\}</tex>, такая что <tex>\mathrm{v}_1 \mathrm{v}_j,\ \mathrm{v}_2 \mathrm{v}_{j+1} \in \mathbb{E} </tex>.