Изменения

Перейти к: навигация, поиск

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

1746 байт убрано, 19:56, 4 ноября 2010
Нет описания правки
{{В разработке}}
== Описание алгоритма ==
Приведенный ниже псевдокод алгоритма находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в неориентированном графе. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию из вершины с нечетной степенью.
remove(w, u)
else:
stack.pop()
print w
</font>
== Доказательство ==
Заметим, что рано или поздноалгоритм закончит свое выполнение, так как количество вершин, которое добавится в стек, не превышает количества ребер. А на каждой итерации цикла, в стек либо добавляется вершина, либо удаляется. Ясно, что в стеке всегда лежит какой-то путь и оператор ''print'' напечатает какой-то путь.
Рассмотрим последнее выполнение оператора ''print''.  Если мы запустим процедуру ''findPath'' из какой-нибудь вершины Пусть <tex> v_1 P</tex>, то самой первой она и будет напечатана, так как у всех остальных вершин изначально четная степень, если мы в какую-нибудь из них войдем по одному ребру, то сможем выйти по другомуэто напечатанный после окончания работы алгоритма путь. Если записать все вершиныЗаметим, в порядке входа в них, то получится циклический путь что вершина <tex> v_1 v_2 v_3 \ldots v_kw</tex>. При выходе из функции вершины будут напечатаны напечатается, только в обратном порядкетом случае, относительно тогоесли все ребра, как они шли в циклическом пути инцидентные с <tex> v_k v_{k - 1} \ldots v_iw</tex>, уже пройдены. Возврат из рекурсии будет осуществляться до того моментаОтсюда следует, как мы либо совсем выйдем из рекурсии (что значит, что наш алгоритм напечатал циклический путь), либо для любой вершины из вершины <tex>v_i P </tex> будут существовать еще все инцидентные ей ребра. Во втором случае, алгоритм опустится содержатся в рекурсию (и у вершины <tex> v_i P </tex> степень станет нечетной, следовательно, как и в первом случае, из нее мы выйдем в первую очередь) и найдет какой-то . Поскольку эйлеров цикл, который граф содержит вершину <tex> v_i </tex> и состоит из некоторых реберне больше одной компоненты связности с более чем одной вершиной, которые мы еще не удаляли. После этого у нас будет напечатан то <tex> v_k v_{k-1} \ldots v_i \ldots v_i P </tex>. И так далее, проделывая такие операции, напечатается эйлеров цикл. Почему напечатанный цикл будет эйлеровым? Во-первых, так как все компоненты связности, кроме, может быть, одной состоят из одной вершины, то если ''findPath'' запустится от вершины с ненулевой степенью, он просмотрит все вершины и содержит все ребра из этой компоненты связностиграфа. Во-вторых, по каждому ребру алгоритм пройдет не более одного раза, потому что после просмотра этого ребра, оно сразу же удаляется из множестваА значит напечатанный путь эйлеров. <tex> \Box </tex>
== Время работы ==
Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>, так как каждое ребро будет просмотрено не более одного раза и запусков функции будет не больше, чем количество ребер.
== См. также ==
Niyaz.nigmatullin
38
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/4688»

Навигация