Изменения

== Алгоритм ===== Описание алгоритма ===Приведенный ниже псевдокод алгоритма Алгоритм находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]]. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию алгоритм из вершины с нечетной степенью.<br>Алгоритм напоминает поиск в ширину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины <tex>v</tex> строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в [[Стек | стеке]] <tex>S</tex>. Когда наступает такой момент, что для текущей вершины <tex>w</tex> все инцидентные ей ребра уже пройдены, записываем вершины из <tex>S</tex> в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам.

=== Псевдокод ===<font size=32>'''Код проверки графа на эйлеровость:''' '''boolean''' checkForEulerPath(): '''int''' OddVertex <tex>= 0</tex> '''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex> '''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) '''mod''' <tex>2 == 1</tex> OddVertex++ '''if''' OddVertex <tex> > 2 </tex><font color=darkgreen>// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым</font> '''return''' ''false'' '''boolean''' visited(<tex>|V|</tex>, ''false'') <font color=darkgreen>// массив инициализируется значениями ''false''</font> '''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex> '''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) <tex> > 0</tex> dfs(<tex>v</tex>, visited) '''break''' '''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex> '''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) <tex> > 0</tex> '''and''' '''not''' visited[<tex>v</tex>] <font color=darkgreen>// если количество компонент связности, содержащие ребра, больше одной,</font> '''return''' ''false'' <font color=darkgreen> // то граф не является эйлеровым</font> '''return''' ''true'' findPath<font color=darkgreen>// граф является эйлеровым</font> '''Код построения эйлерова пути:''' '''function''' findEulerPath(<tex>v</tex>): <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font> stack.clear'''for''' <tex>u : u \in V</tex> '''if''' <tex>\operatorname{deg}</tex>(<tex>u</tex>)'''mod''' <tex>2 == 1</tex> <tex>v = u</tex> '''break''' stack<tex>S</tex>.addpush(<tex>v</tex>) <font color=darkgreen>// <tex>S</tex> {{---}} стек</font> '''while not stack''' <tex>S</tex>.isEmptyempty(): <tex>w := stack</tex> <tex>S</tex>.top() '''for''' <tex>u : u \in V</tex> '''if E contains ''' (<tex>w, u</tex>):<tex>\in E</tex> <font color=darkgreen> // нашли ребро, по которому ещё не прошли</font> stack <tex>S</tex>.addpush(<tex>u</tex>)<font color=darkgreen> // добавили новую вершину в стек</font> <tex>E</tex>.remove(<tex>w, u</tex>) else: '''break''' stack'''if''' <tex> w == S</tex>.top() <tex>S</tex>.pop()<font color=darkgreen> // не нашлось инцидентных вершине <tex>w</tex> рёбер, по которым ещё не прошли</font> print (<tex>w</tex>)

=== Доказательство корректности ===Заметим, что рано или поздно {{Лемма|statement=Данный алгоритм закончит свое выполнениепроходит по каждому ребру, так как количество вершинпричем ровно один раз.|proof=Допустим, которое добавится что в стекмомент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно не превышает количества реберпройденное ребро, инцидентное посещенной вершине. А на каждой итерации цикла, в стек либо добавляется Но тогда эта вершинане могла быть удалена из стека <tex>S</tex>, либо и он не мог стать пустым. Значит алгоритм пройдёт по всем рёбрам хотя бы один раз.Но так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может. Ясно<br>}}Вершина <tex>v</tex>, что с которой начат обход графа, будет последней помещена в стеке всегда лежит какой-то путь <tex>P</tex>. Так как изначально стек пуст, и оператор ''print'' напечатает какой-вершина <tex>v</tex> входит в стек первой, то путьпосле прохода по инцидентным ребрам, алгоритм возвращается к данной вершине, выводит ее и опустошает стек, затем выполнение программы завершается. <br>{{ЛеммаПусть |statement=Напечатанный путь <tex>P</tex> {{--- это напечатанный после окончания работы алгоритма путь}} корректный маршрут в графе, в котором каждые две соседние вершины <tex>u_i</tex> и <tex>u_{i+1}</tex> будут образовывать ребро <tex>(u_i, u_{i+1}) \in E</tex>. Заметим|proof=Будем говорить, что вершина ребро <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>w</tex> переместят в <tex> P </tex> все инцидентные ей ребра содержатся , и ребро <tex>(w,u)</tex> будет представлено в <tex> P </tex>. В ходе алгоритма для каждой *Иначе будет пройдена некоторая последовательность ребер <tex>{u_1, u_2, ..., u_k}</tex>, начинающаяся в вершине <tex>w</tex> и проходящая по ребру <tex>(w, u_1)</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> содержит все ребра графа. А значит напечатанный }}{{Теорема|id=proof1|statement=Данный алгоритм находит корректный эйлеров путь эйлеров. |proof=Из предыдущих лемм следует, что <tex> \Box P</tex>{{---}} искомый эйлеров путь и алгоритм работает корректно.}}=== Рекурсивная реализация === <font size=32> findPath '''function''' findEulerPath(<tex>v</tex> : Vertex): '''for ''' <tex>(v, u) from </tex> <tex>\in</tex> <tex>E</tex> remove <tex>(v, u)</tex> findPath findEulerPath(<tex>u</tex>) print (<tex>v</tex>)

== Время работы См. также ==Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.* [[Гамильтоновы графы]]* [[Покрытие рёбер графа путями]]* [[Произвольно вычерчиваемые из заданной вершины графы]]

== См. также Источники информации ==* [[http://ru.wikipedia.org/wiki/Эйлеров_цикл Википедия {{---}} Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]