Изменения

Вершина <tex>v</tex>, с которой начат обход графа, будет последней помещена в путь P. Так как изначально стек пуст, и вершина <tex>v</tex> входит в стек первой, то после прохода по инцидентным ребрам, алгоритм возвращается к данной вершине, выводит ее и опустошает стек, затем выполнение программы завершается.<br>Напечатанный путь <tex>P</tex> {{---}} корректный маршрут в графе, в котором каждые два ребра подряд инцидентны одной вершинедве соседние вершины <tex>u_i</tex> и <tex>u_{i+1}</tex> будут образовывать ребро <tex>(u_i, u_{i+1})</tex>, принадлежащее <tex>E</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>wu</tex>, а следующей в <tex>S</tex> лежит <tex>uw</tex>. Возможны 2 варианта:#На следующем шаге <tex>uw</tex> перемещена в <tex>P</tex>. Тогда <tex>(w,u)</tex> представлено в <tex>P</tex>.#Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине <tex>uw</tex>, и проходящая по ребру <tex>(w, u_1)</tex>. Докажем, что данный проход <tex>T</tex>{<tex>u_1, u_2, .. Ввиду четности степеней эта последовательность может закончиться только ., u_k</tex>} закончится в вершине <tex>uw</tex>: ребро не может <tex>(u_{k-1}, u_k)</tex>быть инцидентно вершинам <tex>u_1, ... , а значит она следующей попадет в u_{k-2}</tex>. Иначе степень вершины <tex>Pu_k</tex> и будет нечетной. Предположим, что <tex>(wu_{k-1},uu_k)</tex> будет представлено в инцидентно вершине, пройденной при обходе графа из вершины <tex>Pu</tex>.Так Но это неверно, так как алгоритм проходит по каждому ребрутогда бы данные вершины пройдены ранее. Из этого следует, причем ровно 1 разчто мы закончим обход в вершине <tex>w</tex>. Следовательно, а путь данная вершина первой поместится в <tex>P</tex> корректенвслед за <tex>u</tex>, и ребро <tex>(w, u)</tex> будет представлено в <tex>P</tex>.Из этого следует, что <tex>P</tex> {{---}} искомый эйлеров путь.