Изменения

== Алгоритм ===== Описание алгоритма ===Приведенный ниже псевдокод алгоритма Алгоритм находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]]. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию алгоритм из вершины с нечетной степенью.<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>. Так как изначально стек либо добавляется пуст, и вершина<tex>v</tex> входит в стек первой, либо удаляетсято после прохода по инцидентным ребрам, алгоритм возвращается к данной вершине, выводит ее и опустошает стек, затем выполнение программы завершается. Ясно<br>{{Лемма|statement=Напечатанный путь <tex>P</tex> {{---}} корректный маршрут в графе, что в стеке всегда лежит какой-то путь котором каждые две соседние вершины <tex>u_i</tex> и оператор ''print'' напечатает какой-то путь<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> P 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/Эйлеров_цикл Википедия {{---}} Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]