Алгоритм построения Эйлерова цикла — различия между версиями
(Новая страница: «== Псевдокод == <font size=3> findPath(v): for (v, u) from E remove (v, u) findPath(u) print v </font> == Доказательств…») |
|||
| Строка 1: | Строка 1: | ||
| + | {{В разработке}} | ||
| + | == Описание алгоритма == | ||
| + | Приведенный ниже псевдокод алгоритма находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в неориентированном графе. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию из вершины с нечетной степенью. | ||
| + | |||
== Псевдокод == | == Псевдокод == | ||
<font size=3> | <font size=3> | ||
findPath(v): | findPath(v): | ||
| − | + | stack.clear() | |
| − | + | stack.add(v) | |
| − | + | while not stack.isEmpty(): | |
| − | + | w := stack.top() | |
| + | if E contains (w, u): | ||
| + | stack.add(u) | ||
| + | remove(w, u) | ||
| + | else: | ||
| + | print w | ||
</font> | </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>. И так далее, проделывая такие операции, напечатается эйлеров цикл. | Если мы запустим процедуру ''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>. И так далее, проделывая такие операции, напечатается эйлеров цикл. | ||
Версия 20:28, 2 ноября 2010
Описание алгоритма
Приведенный ниже псевдокод алгоритма находит Эйлеров цикл как в ориентированном графе, так и в неориентированном графе. Чтобы построить Эйлеров путь, нужно запустить функцию из вершины с нечетной степенью.
Псевдокод
findPath(v):
stack.clear()
stack.add(v)
while not stack.isEmpty():
w := stack.top()
if E contains (w, u):
stack.add(u)
remove(w, u)
else:
print w
Доказательство
Заметим, что рано или поздно
Рассмотрим последнее выполнение оператора print.
Если мы запустим процедуру findPath из какой-нибудь вершины , то самой первой она и будет напечатана, так как у всех остальных вершин изначально четная степень, если мы в какую-нибудь из них войдем по одному ребру, то сможем выйти по другому. Если записать все вершины, в порядке входа в них, то получится циклический путь . При выходе из функции вершины будут напечатаны в обратном порядке, относительно того, как они шли в циклическом пути . Возврат из рекурсии будет осуществляться до того момента, как мы либо совсем выйдем из рекурсии (что значит, что наш алгоритм напечатал циклический путь), либо из вершины будут существовать еще ребра. Во втором случае, алгоритм опустится в рекурсию (и у вершины степень станет нечетной, следовательно, как и в первом случае, из нее мы выйдем в первую очередь) и найдет какой-то эйлеров цикл, который содержит вершину и состоит из некоторых ребер, которые мы еще не удаляли. После этого у нас будет напечатан . И так далее, проделывая такие операции, напечатается эйлеров цикл.
Почему напечатанный цикл будет эйлеровым? Во-первых, так как все компоненты связности, кроме, может быть, одной состоят из одной вершины, то если findPath запустится от вершины с ненулевой степенью, он просмотрит все вершины и все ребра из этой компоненты связности. Во-вторых, по каждому ребру алгоритм пройдет не более одного раза, потому что после просмотра этого ребра, оно сразу же удаляется из множества.
Время работы
Если реализовать удаление ребер за , то алгоритм будет работать за , так как каждое ребро будет просмотрено не более одного раза и запусков функции будет не больше, чем количество ребер.
