17
правок
Изменения
м
Нет описания правки
</font>
== Доказательство корректности ==
1. Данный алгоритм проходит по каждому ребру, причем ровно один раз. Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из <tex>S</tex>, и <tex>S</tex> не мог стать пустым.<br>
Так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может. <br>
2. Напечатанный путь <tex>P</tex> {{---}} маршрут, содержащий все ребра графа, при этом не содержит ребра, не лежащие на пути графа. Будем говорить, что ребро <tex>(w,u)</tex> представлено в <tex>S</tex> или <tex>P</tex>, если в какой-то момент работы алгоритма вершины <tex>w</tex> и <tex>u</tex> находятся рядом. Каждое ребро графа представлено в <tex>S</tex>. Рассмотрим случай, когда из <tex>S</tex> в <tex>P</tex> перемещена вершина <tex>w</tex>, а следующей в <tex>S</tex> лежит <tex>u</tex>. Возможны 2 варианта:#На следующем шаге <tex>u</tex> перемещена в <tex>SP</tex>. Тогда <tex>(w,u)</tex> представлено в <tex>P</tex>.
#Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине <tex>u</tex>. Ввиду четности степеней эта последовательность может закончиться только в вершине <tex>u</tex>, а значит она следующей попадет в <tex>P</tex> и <tex>(w,u)</tex> будет представлено в <tex>P</tex>.
Из пунктов 1 и 2 следует, что <tex>P</tex> {{- --}} искомый эйлеров путь.
<tex> \Box </tex>
== Время работы ==
Если реализовать поиск ребер инцидентных вершине и удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.<br>
Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство <tex>\mathtt{deleted }</tex> бинарного типа.
== См. также ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы Гамильтоновы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
== Источники информации ==
