Изменения
Нет описания правки
{{В разработке}}
== Описание алгоритма ==
Приведенный ниже псевдокод алгоритма находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в неориентированном графе. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию из вершины с нечетной степенью.
== Псевдокод ==
<font size=3>
findPath(v):
</font>
== Доказательство ==
Заметим, что рано или поздно
Рассмотрим последнее выполнение оператора ''print''.
Если мы запустим процедуру ''findPath'' из какой-нибудь вершины <tex> v_1 </tex>, то самой первой она и будет напечатана, так как у всех остальных вершин изначально четная степень, если мы в какую-нибудь из них войдем по одному ребру, то сможем выйти по другому. Если записать все вершины, в порядке входа в них, то получится циклический путь <tex> v_1 v_2 v_3 \ldots v_k</tex>. При выходе из функции вершины будут напечатаны в обратном порядке, относительно того, как они шли в циклическом пути <tex> v_k v_{k - 1} \ldots v_i</tex>. Возврат из рекурсии будет осуществляться до того момента, как мы либо совсем выйдем из рекурсии (что значит, что наш алгоритм напечатал циклический путь), либо из вершины <tex>v_i </tex> будут существовать еще ребра. Во втором случае, алгоритм опустится в рекурсию (и у вершины <tex> v_i </tex> степень станет нечетной, следовательно, как и в первом случае, из нее мы выйдем в первую очередь) и найдет какой-то эйлеров цикл, который содержит вершину <tex> v_i </tex> и состоит из некоторых ребер, которые мы еще не удаляли. После этого у нас будет напечатан <tex> v_k v_{k-1} \ldots v_i \ldots v_i </tex>. И так далее, проделывая такие операции, напечатается эйлеров цикл.
