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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Описание алгоритма)
Строка 1: Строка 1:
 
== Описание алгоритма ==
 
== Описание алгоритма ==
Приведенный ниже псевдокод алгоритма находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в неориентированном графе. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию из вершины с нечетной степенью.
+
Приведенный ниже псевдокод алгоритма находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в неориентированном графе. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию из вершины с нечетной степенью.
  
 
== Псевдокод ==
 
== Псевдокод ==

Версия 09:34, 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] \Box [/math]

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

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

Время работы

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

См. также