Алгоритм построения Эйлерова цикла — различия между версиями
| Строка 1: | Строка 1: | ||
| − | |||
== Описание алгоритма == | == Описание алгоритма == | ||
Приведенный ниже псевдокод алгоритма находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в неориентированном графе. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию из вершины с нечетной степенью. | Приведенный ниже псевдокод алгоритма находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в неориентированном графе. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию из вершины с нечетной степенью. | ||
| Строка 14: | Строка 13: | ||
remove(w, u) | remove(w, u) | ||
else: | else: | ||
| + | stack.pop() | ||
print w | print w | ||
</font> | </font> | ||
== Доказательство == | == Доказательство == | ||
| − | Заметим, что рано или поздно | + | Заметим, что рано или поздно алгоритм закончит свое выполнение, так как количество вершин, которое добавится в стек, не превышает количества ребер. А на каждой итерации цикла, в стек либо добавляется вершина, либо удаляется. Ясно, что в стеке всегда лежит какой-то путь и оператор ''print'' напечатает какой-то путь. |
| − | + | Пусть <tex>P</tex> - это напечатанный после окончания работы алгоритма путь. Заметим, что вершина <tex>w</tex> напечатается, только в том случае, если все ребра, инцидентные с <tex>w</tex>, уже пройдены. Отсюда следует, что для любой вершины из <tex> P </tex> все инцидентные ей ребра содержатся в <tex> P </tex>. Поскольку эйлеров граф содержит не больше одной компоненты связности с более чем одной вершиной, то <tex> P </tex> содержит все ребра графа. А значит напечатанный путь эйлеров. <tex> \Box </tex> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Время работы == | == Время работы == | ||
| − | Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex> | + | Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>. |
== См. также == | == См. также == | ||
Версия 19:56, 4 ноября 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:
stack.pop()
print w
Доказательство
Заметим, что рано или поздно алгоритм закончит свое выполнение, так как количество вершин, которое добавится в стек, не превышает количества ребер. А на каждой итерации цикла, в стек либо добавляется вершина, либо удаляется. Ясно, что в стеке всегда лежит какой-то путь и оператор print напечатает какой-то путь.
Пусть - это напечатанный после окончания работы алгоритма путь. Заметим, что вершина напечатается, только в том случае, если все ребра, инцидентные с , уже пройдены. Отсюда следует, что для любой вершины из все инцидентные ей ребра содержатся в . Поскольку эйлеров граф содержит не больше одной компоненты связности с более чем одной вершиной, то содержит все ребра графа. А значит напечатанный путь эйлеров.
Время работы
Если реализовать удаление ребер за , то алгоритм будет работать за .
