43
правки
Изменения
→Доказательство
== Доказательство ==
Пусть <tex>P-</tex> - напечатанный путь. Заметим, что первой в <tex>S</tex> помещается вершина <tex>v</tex>, и она будет последней перемещена из <tex>S</tex> в <tex>P</tex>. Следовательно, она будет последней вершиной в <tex>P</tex>. Далее, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены, активной будет стартовая вершина <tex>v</tex> (Так как степени всех вершин четны). Значит, эта вершина будет первой перемещена из <tex>S</tex> в <tex>P</tex>. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в <tex>P</tex>, находится вершина <tex>v</tex>. Иначе говоря, если эта последовательность представляет маршрут, то этот маршрут замкнут.<br>
Покажем, что <tex>P</tex> это маршрут содержащий все ребра.<br>
Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из <tex>S</tex>, и <tex>S</tex> не мог стать пустым.<br>
