Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
Содержание
Описание алгоритма
Пусть у нас есть граф теоремы Оре или теоремы Дирака, и требуется найти в нем гамильтонов цикл. Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа(не важно в каком порядке). Теперь раз будем делать следующую операцию:
, удовлетворяющий условию- Если между первой (здесь и далее первая вершина - вершина в голове очереди) и второй вершиной в очереди есть ребро в графе , то перемещаем первую вершину в конец очереди и переходим к следующей итерации.
- Если между первой и второй вершиной в очереди ребра нет, то найдем вершину теорема Оре, либо теорема Дирака, то такая вершина обязательно найдется; чуть позже мы это докажем явно). После чего поменяем в очереди местами вершины и , и , и , и так далее, пока (то есть пробегает все значения от 0 до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на -й позиции), а так же, гарантированно существует ребро между -й и -й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди. , такую что, ребра (так как у нас для графа выполнена либо
Таким образом после
итераций, мы получаем последовательность (вершины лежащие в очереди), где любые 2 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а так же существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу.Псевдокод
for i = 1 to n // перебираем все вершины перестановкиif // если нет ребра между for // перебираем все остальные вершины if && // если есть ребра reverse_subsequence( ) // разворачиваем часть перестановки от i+1 позиции до j break // переходим к следующей итерации внешнего for |
Доказательство алгоритма
На
-ой итерации внешнего цикла рассматриваются вершины . Возможно 2 случая:- между ними есть ребро, и тогда делать ничего не надо;
- между ними ребра нет, и тогда надо найти такую вершину , что ;
Покажем, что такая вершина обязательно найдется. Пусть теоремы Оре или теоремы Дирака, в зависимости от наших начальных условий. А значит , следовательно искомая вершина обязательно найдется. Теперь заметим, что после -ой итерации внешнего цикла между всеми парами вершин , где существует ребро, а значит после итераций мы найдем цикл.
и . Тогда , откуда . Но по условиюСложность алгоритма
Алгоритм работает за
. Действительно, количество итераций внешнего цикла всегда равно . Во внутреннем цикле в худшем случае будет выполнено итерации, получаем время работы .