17
правок
Изменения
Нет описания правки
'''boolean''' checkForEulerPath():
'''int''' numberOfOdd = 0
'''for''' <tex>v</tex> '''<tex>\in''' </tex> <tex>V</tex>
'''if''' <tex>\operatorname{deg} v</tex> '''mod''' 2 == 1
numberOfOdd = numberOfOdd + 1
'''if''' numberOfOdd > 2 <font color=darkgreen>// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым</font>
'''return''' ''false''
'''boolean''' vis[sizeOf <tex>|V|</tex>] <font color=darkgreen>// инициализировать массив значениями ''false''</font> '''for''' <tex>v</tex> '''<tex>\in''' </tex> <tex>V</tex>
'''if''' <tex>\operatorname{deg} v</tex> > 0
dfs(<tex>v</tex>, vis)
break
'''for''' <tex>v</tex> '''<tex>\in''' </tex> <tex>V</tex>
'''if''' <tex>\operatorname{deg} v</tex> > 0 '''and''' '''not''' vis[<tex>v</tex>] <font color=darkgreen>// если количество компонент связности, содержащие ребра, больше одной,</font>
'''return''' ''false'' <font color=darkgreen> // то граф не является эйлеровым</font>
'''while not''' S.isEmpty()
<tex>w</tex> = S.top()
'''if''' exists <tex>(w, u)</tex> '''<tex>\in''' </tex> <tex>E</tex>
S.push(<tex>u</tex>)
remove <tex>(w, u)</tex>
|proof=
Данный алгоритм проходит по каждому ребру, причем ровно один раз. Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из <tex>S</tex>, и <tex>S</tex> не мог стать пустым. Так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может.<br>
Вершина <tex>v</tex>, с которой начат обход графа, будет последней помещена в путь <tex>P</tex>. Так как изначально стек пуст, и вершина <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>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> {{---}} искомый эйлеров путь.
}}
<font size=2>
'''function''' findEulerPath(<tex>v</tex> : Vertex):
'''for''' <tex>(v,u)</tex> '''<tex>\in''' </tex> <tex>E</tex>
remove <tex>(v, u)</tex>
findEulerPath(<tex>u</tex>)
