Алгоритм построения Эйлерова цикла

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

Алгоритм находит Эйлеров цикл как в ориентированном, так и в неориентированном графе. Перед запуском алгоритма необходимо проверить граф на эйлеровость. Чтобы построить Эйлеров путь, нужно запустить алгоритм из вершины с нечетной степенью.
Алгоритм напоминает поиск в глубину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины [math]v[/math] строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в стеке [math]S[/math]. Когда наступает такой момент, что для текущей вершины [math]w[/math] все инцидентные ей ребра уже пройдены, записываем вершины из [math]S[/math] в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам.

Псевдокод

 findPath(v):
   S.clear()
   S.add(v)
   while not stack.isEmpty():
     w := S.top()
     if E contains(w, u):
       S.add(u)
       remove(w, u)
     else:
       S.pop()
       print w

Доказательство

Пусть [math]P[/math] — напечатанный путь. Заметим, что первой в [math]S[/math] помещается вершина [math]v[/math], и она будет последней перемещена из [math]S[/math] в [math]P[/math]. Следовательно, она будет последней вершиной в [math]P[/math]. Далее, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены, активной будет стартовая вершина [math]v[/math] (Так как степени всех вершин четны). Значит, эта вершина будет первой перемещена из [math]S[/math] в [math]P[/math]. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в [math]P[/math], находится вершина [math]v[/math]. Иначе говоря, если эта последовательность представляет маршрут, то этот маршрут замкнут.
Покажем, что [math]P[/math] это маршрут содержащий все ребра.
Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из [math]S[/math], и [math]S[/math] не мог стать пустым.
Будем говорить, что ребро [math](w,u)[/math] представлено в [math]S[/math] или [math]P[/math], если в какой-то момент работы алгоритма вершины [math]w[/math] и [math]u[/math] находятся рядом. Каждое ребро графа представлено в [math]S[/math]. Допустим в какой-то момент из [math]S[/math] в [math]P[/math] перемещена вершина [math]w[/math], а следующей в [math]S[/math] лежит [math]u[/math]. Возможны 2 варианта:

1. На следующем шаге [math]u[/math] перемещена в [math]S[/math]. Тогда [math](w,u)[/math] представлено в [math]P[/math].
2. Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине [math]u[/math]. Ввиду четности степеней эта последовательность может закончиться только в вершине [math]u[/math], а значит она следующей попадет в [math]P[/math] и [math](w,u)[/math] будет представлено в [math]P[/math].

Отсюда понятно, что последовательность вершин в [math]P[/math] является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз.

[math] \Box [/math]

Рекурсивная реализация

 findPath(v):
   for (v, u) from E
     remove(v, u)
     findPath(u)
   print v

Время работы

Если реализовать удаление ребер за [math]O(1)[/math], то алгоритм будет работать за [math]O(E)[/math].

См. также

• Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
• Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru