Изменения

Заметим, что рано или поздно алгоритм закончит свое выполнение, так как количество вершин, которое добавится в стек, не превышает количества ребер. А на каждой итерации цикла, в стек либо добавляется вершина, либо удаляется. Ясно, что в стеке всегда лежит какой-то путь и оператор ''print'' напечатает какой-то путь.  Пусть <tex>P</tex> - это напечатанный после окончания работы алгоритма путь. Заметим, что первой в <tex>S</tex> помещается вершина <tex>wv</tex> напечатается только , и она будет последней перемещена из <tex>S</tex> в <tex>P</tex>. Следовательно, она будет последней вершиной в том случае<tex>P</tex>. Далее, как было отмечено выше, если первый раз, когда обнаружится, что все инцидентные активной вершине ребрапройдены, инцидентные активной будет стартовая вершина <tex>wv</tex>, уже пройдены. Отсюда следует Значит, что для любой вершины эта вершина будет первой перемещена из <tex> P S</tex> все инцидентные ей ребра содержатся в <tex> P </tex>. В ходе Итак, по окончании работы алгоритма для каждой вершины в стек попадают все смежные с ней вершины, а так как алгоритм работает до опустошения стеканачале и в конце последовательности вершин, все они в итоге попадут содержащейся в <tex> P </tex>, находится вершина <tex>v</tex>. Иначе говоря, если эта последовательность представляет маршрут, то этот маршрут замкнут.<br>Покажем, что маршрут замкнут.<br>Отметим, что в конечном итоге каждое ребро будет пройдено. Действительно, допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку эйлеров граф содержит связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не больше одной компоненты связности с более чем одной вершиноймогла быть удалена из <tex>S</tex>, то и <tex> P S</tex> содержит все ребра графа. А значит напечатанный путь эйлеровне мог стать пустым. <tex> \Box </tex>