Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре

Описание алгоритма

Пусть у нас есть граф [math]\mathbb{G} = \left \langle \mathbb{V, E} \right \rangle[/math], удовлетворяющий условию теоремы Оре или теоремы Дирака, и требуется найти в нем гамильтонов цикл. Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа(не важно в каком порядке). Теперь [math]n = \left | \mathbb{V}\right |[/math] раз будем делать следующую операцию:

• Если между первой (здесь и далее первая вершина - вершина в голове очереди) и второй вершиной в очереди есть ребро в графе [math]\mathbb{G}[/math], то перемещаем первую вершину в конец очереди и переходим к следующей итерации.
• Если между первой и второй вершиной в очереди ребра нет, то найдем вершину [math]v_i[/math], где [math]i \gt 2[/math], такую что, ребра [math]v_1v_i, v_2v_{i+1} \in \mathbb{E}[/math] (так как у нас для графа выполнена либо теорема Оре, либо теорема Дирака, то такая вершина обязательно найдется; чуть позже мы это докажем явно). После чего поменяем в очереди местами вершины [math]v_2[/math] и [math]v_i[/math], [math]v_3[/math] и [math]v_{i-1}[/math], [math]v_{2+j} [/math] и [math]v_{i-j}[/math], и так далее, пока [math]2 + j \lt i - j[/math] (то есть [math]j[/math] пробегает все значения от 0 до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на [math]i[/math]-й позиции), а так же, гарантированно существует ребро между [math]i[/math]-й и [math](i+1)[/math]-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди.

Таким образом после [math]n[/math] итераций, мы получаем последовательность (вершины лежащие в очереди), где любые 2 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а так же существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу.

Псевдокод

Queue queue; // создаем очередь for i = 0 to n - 1 // queue.pushback(v[i]) // добавляем в очередь все вершины графа for k = 0 to n - 1 // пока не проделано нужное количество итераций if !exist(queue.at(0), queue.at(1)) // проверяем существования ребра между первой и второй вершинами очереди queue.swapSubQueue(2, find_vertex()) // если, не существует, то меняем порядок вершин в очереди, со второй до // найденной, удовлетворяющей нас позиции

Доказательство алгоритма

Для доказательства корректности алгоритма достаточно показать:

• Каждый раз, когда нам надо искать вершину [math]v_i[/math], где [math]i \gt 2[/math], такую что [math]v_1v_i, v_2v_{i+1} \in \mathbb{E}[/math], такая вершина действительно существует.
• После [math]n[/math] итераций между каждой парой соседних вершин очереди существует ребро.

Сложность алгоритма

Алгоритм работает за [math]O(n^2)[/math]. Действительно, количество итераций внешнего цикла [math]\mathrm{for}[/math] всегда равно [math]n[/math]. Во внутреннем цикле в худшем случае будет выполнено [math]n - 2[/math] итерации, получаем время работы [math]O(n^2)[/math].

См.также

• Гамильтоновы графы
• Теорема Оре
• Теорема Дирака