Изменения

'''return''' ''false'' <font color=darkgreen> // то граф не является эйлеровым</font>

'''Код построения эйлерова циклапути:''' '''function''' findEulerPath(v : Vertex): <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font> Stack stack<tex>S</tex> stack<tex>S</tex>.push(v) '''while not''' stack<tex>S</tex>.isEmpty() w = stack<tex>S</tex>.top()

stack<tex>S</tex>.push(u)

stack<tex>S</tex>.pop()

Пусть <tex>P</tex> {{---}} напечатанный путь1. Заметим, что первой в <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>Так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может. <br>2. Напечатанный путь <tex>P</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>w</tex>, а следующей в <tex>S</tex> лежит <tex>u</tex>. Возможны 2 варианта:

 Отсюда понятноИз пунктов 1 и 2 следует, что последовательность вершин в <tex>P</tex> является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз- искомый эйлеров путь.<br> 

Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство deleted бинарного типа. Тогда удаление ребер будет выглядеть следующим образом:<font size=2> '''function''' remove(v : Vertex, index : '''int'''): graph[v][index] = graph[v].back() graph[v].pop()</font>