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

Псевдокод

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

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

Если мы запустим процедуру findPath из какой-нибудь вершины [math] v_1 [/math], то самой первой она и будет напечатана, так как у всех остальных вершин изначально четная степень, если мы в какую-нибудь из них войдем по одному ребру, то сможем выйти по другому. Если записать все вершины, в порядке входа в них, то получится циклический путь [math] v_1 v_2 v_3 \ldots v_k[/math]. При выходе из функции вершины будут напечатаны в обратном порядке, относительно того, как они шли в циклическом пути [math] v_k v_{k - 1} \ldots v_i[/math]. Возврат из рекурсии будет осуществляться до того момента, как мы либо совсем выйдем из рекурсии (что значит, что наш алгоритм напечатал циклический путь), либо из вершины [math]v_i [/math] будут существовать еще ребра. Во втором случае, алгоритм опустится в рекурсию (и у вершины [math] v_i [/math] степень станет нечетной, следовательно, как и в первом случае, из нее мы выйдем в первую очередь) и найдет какой-то эйлеров цикл, который содержит вершину [math] v_i [/math] и состоит из некоторых ребер, которые мы еще не удаляли. После этого у нас будет напечатан [math] v_k v_{k-1} \ldots v_i \ldots v_i [/math]. И так далее, проделывая такие операции, напечатается эйлеров цикл.

Почему напечатанный цикл будет эйлеровым? Во-первых, так как все компоненты связности, кроме, может быть, одной состоят из одной вершины, то если findPath запустится от вершины с ненулевой степенью, он просмотрит все вершины и все ребра из этой компоненты связности. Во-вторых, по каждому ребру алгоритм пройдет не более одного раза, потому что после просмотра этого ребра, оно сразу же удаляется из множества. [math] \Box [/math]

Время работы

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

См. также

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