Алгоритм построения Эйлерова цикла — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
(Доказательство)
Строка 20: Строка 20:
 
Заметим, что рано или поздно алгоритм закончит свое выполнение, так как количество вершин, которое добавится в стек, не превышает количества ребер. А на каждой итерации цикла, в стек либо добавляется вершина, либо удаляется. Ясно, что в стеке всегда лежит какой-то путь и оператор ''print'' напечатает какой-то путь.  
 
Заметим, что рано или поздно алгоритм закончит свое выполнение, так как количество вершин, которое добавится в стек, не превышает количества ребер. А на каждой итерации цикла, в стек либо добавляется вершина, либо удаляется. Ясно, что в стеке всегда лежит какой-то путь и оператор ''print'' напечатает какой-то путь.  
  
Пусть <tex>P</tex> - это напечатанный после окончания работы алгоритма путь. Заметим, что вершина <tex>w</tex> напечатается только в том случае, если все ребра, инцидентные <tex>w</tex>, уже пройдены. Отсюда следует, что для любой вершины из <tex> P </tex> все инцидентные ей ребра содержатся в <tex> P </tex>. Поскольку эйлеров граф содержит не больше одной компоненты связности с более чем одной вершиной, то <tex> P </tex> содержит все ребра графа. А значит напечатанный путь эйлеров. <tex> \Box </tex>
+
Пусть <tex>P</tex> - это напечатанный после окончания работы алгоритма путь. Заметим, что вершина <tex>w</tex> напечатается только в том случае, если все ребра, инцидентные <tex>w</tex>, уже пройдены. Отсюда следует, что для любой вершины из <tex> P </tex> все инцидентные ей ребра содержатся в <tex> P </tex>. В ходе алгоритма для каждой вершины в стек попадают все смежные с ней вершины, а так как алгоритм работает до опустошения стека, все они в итоге попадут в <tex> P </tex>. Поскольку эйлеров граф содержит не больше одной компоненты связности с более чем одной вершиной, то <tex> P </tex> содержит все ребра графа. А значит напечатанный путь эйлеров. <tex> \Box </tex>
  
 
== Рекурсивная реализация ==  
 
== Рекурсивная реализация ==  

Версия 10:26, 30 ноября 2011

Описание алгоритма

Приведенный ниже псевдокод алгоритма находит Эйлеров цикл как в ориентированном графе, так и в неориентированном графе. Перед запуском алгоритма необходимо проверить граф на эйлеровость. Чтобы построить Эйлеров путь, нужно запустить функцию из вершины с нечетной степенью.

Псевдокод

 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:
       stack.pop()
       print w

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

Заметим, что рано или поздно алгоритм закончит свое выполнение, так как количество вершин, которое добавится в стек, не превышает количества ребер. А на каждой итерации цикла, в стек либо добавляется вершина, либо удаляется. Ясно, что в стеке всегда лежит какой-то путь и оператор print напечатает какой-то путь.

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

Рекурсивная реализация

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

Время работы

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

См. также