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