Бюрократы, editor, Администраторы
422
правки
Изменения
м
Нет описания правки
Заметим, что рано или поздно алгоритм закончит свое выполнение, так как количество вершин, которое добавится в стек, не превышает количества ребер. А на каждой итерации цикла, в стек либо добавляется вершина, либо удаляется. Ясно, что в стеке всегда лежит какой-то путь и оператор ''print'' напечатает какой-то путь.
Пусть <tex>P</tex> - это напечатанный после окончания работы алгоритма путь. Заметим, что вершина <tex>w</tex> напечатается, только в том случае, если все ребра, инцидентные с <tex>w</tex>, уже пройдены. Отсюда следует, что для любой вершины из <tex> P </tex> все инцидентные ей ребра содержатся в <tex> P </tex>. Поскольку эйлеров граф содержит не больше одной компоненты связности с более чем одной вершиной, то <tex> P </tex> содержит все ребра графа. А значит напечатанный путь эйлеров. <tex> \Box </tex>
== Рекурсивная реализация ==
