38
правок
Изменения
Новая страница: «== Псевдокод == <font size=3> findPath(v): for (v, u) from E remove (v, u) findPath(u) print v </font> == Доказательств…»
== Псевдокод ==
<font size=3>
findPath(v):
for (v, u) from E
remove (v, u)
findPath(u)
print v
</font>
== Доказательство ==
Если мы запустим процедуру ''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>. И так далее, проделывая такие операции, напечатается эйлеров цикл.
Почему напечатанный цикл будет эйлеровым? Во-первых, так как все компоненты связности, кроме, может быть, одной состоят из одной вершины, то если ''findPath'' запустится от вершины с ненулевой степенью, он просмотрит все вершины и все ребра из этой компоненты связности.
Во-вторых, по каждому ребру алгоритм пройдет не более одного раза, потому что после просмотра этого ребра, оно сразу же удаляется из множества. <tex> \Box </tex>
== Время работы ==
Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>, так как каждое ребро будет просмотрено не более одного раза и запусков функции будет не больше, чем количество ребер.
== См. также ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
<font size=3>
findPath(v):
for (v, u) from E
remove (v, u)
findPath(u)
print v
</font>
== Доказательство ==
Если мы запустим процедуру ''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>. И так далее, проделывая такие операции, напечатается эйлеров цикл.
Почему напечатанный цикл будет эйлеровым? Во-первых, так как все компоненты связности, кроме, может быть, одной состоят из одной вершины, то если ''findPath'' запустится от вершины с ненулевой степенью, он просмотрит все вершины и все ребра из этой компоненты связности.
Во-вторых, по каждому ребру алгоритм пройдет не более одного раза, потому что после просмотра этого ребра, оно сразу же удаляется из множества. <tex> \Box </tex>
== Время работы ==
Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>, так как каждое ребро будет просмотрено не более одного раза и запусков функции будет не больше, чем количество ребер.
== См. также ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
