Изменения

== Алгоритм ===== Описание алгоритма ===Приведенный ниже псевдокод алгоритма Алгоритм находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]]. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию алгоритм из вершины с нечетной степенью.<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> S.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''' <tex>S</tex>.addpush(<tex>v</tex>) <font color=darkgreen>// <tex>S</tex> {{---}} стек</font> '''while not stack''' <tex>S</tex>.isEmptyempty(): <tex>w := </tex> <tex>S</tex>.top() found_edge = '''False''' '''for''' <tex>u : u \in V</tex> '''if E contains ''' (<tex>w, u</tex>):<tex>\in E</tex> <font color=darkgreen> // нашли ребро, по которому ещё не прошли</font> <tex>S</tex>.addpush(<tex>u</tex>)<font color=darkgreen> // добавили новую вершину в стек</font> <tex>E</tex>.remove(<tex>w, u</tex>) else: found_edge = '''True''' '''break''' '''if''' '''not''' found_edge <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> и <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>P</tex> {{---то }} искомый эйлеров путь и оператор алгоритм работает корректно.}}=== Рекурсивная реализация ===<font size=2> '''printfunction''' 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>) print(<tex>v</tex>)</font>=== Время работы ===Если реализовать поиск ребер инцидентных вершине и удаление ребер за <tex>O(1)</tex>, то путьалгоритм будет работать за <tex>O(E)</tex>.<br>Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство <tex>\mathtt{deleted}</tex> бинарного типа.

Пусть === Рекурсивная реализация за <tex>PO(E)</tex> ===Заведём 2 массива: <tex>vis</tex> и <tex>first</tex> <br><tex>vis[i] (bool)</tex> - это напечатанный после окончания работы алгоритма путь. Заметим, что вершина посещено ли ребро с индексом <tex>i</tex> <tex>w(i \in 0..(E-1))</tex> напечатается только в том случае<br> (массив нужен, если все ребра, инцидентные чтобы за <tex>wO(1)</tex>проверять, уже пройдены. Отсюда следует, что для любой вершины из доступно ребро или нет) <br><tex> P first[u] (int)</tex> все инцидентные ей ребра содержатся в - индекс первой вершины <tex> P v</tex>. В ходе алгоритма для каждой вершины в стек попадают все смежные с ней вершинысписке смежных вершин, а так как алгоритм работает до опустошения стека, все они в итоге попадут в такой что ребро <tex> P (u,v)</tex>. Поскольку эйлеров граф содержит не больше одной компоненты связности с более чем одной вершиной, то посещено <tex> P (u \in 0..(V-1))</tex> содержит все ребра графа. А значит напечатанный путь эйлеров. <br>(массив нужен, чтобы в среднем за <tex> \Box O(1)</tex> находить доступное ребро) <br>

== Рекурсивная реализация == Изначально оба массива заполнены нулями. <font size=3> findPath(v): for (v, u) from E remove (v, u) findPath(u) print v</fontbr>

== Время работы ==Если реализовать удаление ребер за Граф будем хранить в виде списков смежных вершин. Для каждой вершины <tex>u</tex> построим список <tex>g[u]</tex> из пар вида <tex>O(1i,v)</tex>, то алгоритм будет работать за <br><tex>i</tex> - индекс ребра <tex>O(Eu,v)</tex>.<br><tex>v</tex> - номер смежной вершины <br>

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