Изменения

== Алгоритм ===== Описание алгоритма ===

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

=== Псевдокод ===

'''int''' numberOfOdd OddVertex <tex>= 0</tex> '''for''' <tex>v : v '''</tex> <tex>\in''' </tex> <tex>V</tex> '''if''' vertexDegree<tex>\operatorname{deg}</tex>(<tex>v</tex>) '''mod''' <tex>2 == 1</tex> numberOfOdd = numberOfOdd OddVertex++ 1 '''if''' numberOfOdd OddVertex <tex> > 2 </tex><font color=darkgreen>// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым</font>

'''boolean''' vis[sizeOf visited(<tex>|V|</tex>] , ''false'') <font color=darkgreen>// инициализировать массив инициализируется значениями ''false''</font> '''for''' <tex>v : v '''</tex> <tex>\in''' </tex> <tex>V</tex> '''if''' vertexDegree<tex>\operatorname{deg}</tex>(<tex>v</tex>) <tex> > 0</tex> dfs(<tex>v</tex>, visvisited) '''break''' '''for''' <tex>v ''': v</tex> <tex>\in''' </tex> <tex>V</tex> '''if''' vertexDegree<tex>\operatorname{deg}</tex>(<tex>v</tex>) <tex> > 0 </tex> '''and''' '''not''' visvisited[<tex>v</tex>] <font color=darkgreen>// если количество компонент связности, содержащие ребра, больше одной,</font> '''return''' ''false'' <font color=darkgreen> // то граф не является эйлеровым</font> '''return''' ''true'' // граф является эйлеровым <font color=darkgreen>// Вспомогательные функции:граф является эйлеровым</font> '''function''' dfs(v : Vertex, vis[] : '''boolean'''): vis[v] = ''true'' '''for''' (v, u) '''in''' <tex>E</tex> '''if not''' vis[u] dfs(u, vis) '''int''' vertexDegree(v : Vertex): '''int''' count = 0 '''for''' (v, u) '''in''' <tex>E</tex> count = count + 1 '''return''' count

'''Код построения эйлерова циклапути:''' '''function''' findEulerPath(<tex>v : Vertex</tex>): <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font> Stack stack'''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>.push(<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() found_edge = '''False''' '''iffor''' exists (w, <tex>u : u) \in V</tex> '''inif''' (<tex>w, u</tex>) <tex>\in E</tex> <font color=darkgreen> // нашли ребро, по которому ещё не прошли</font> stack <tex>S</tex>.push(<tex>u</tex>)<font color=darkgreen> // добавили новую вершину в стек</font> <tex>E</tex>.remove(<tex>w, u</tex>) found_edge = '''True''' '''break''' '''elseif''' ''' not''' found_edge stack<tex>S</tex>.pop()<font color=darkgreen> // не нашлось инцидентных вершине <tex>w</tex> рёбер, по которым ещё не прошли</font> print(<tex>w</tex>)

=== Доказательство корректности ===Пусть <tex>P</tex> {{---}} напечатанный путьЛемма|statement=Данный алгоритм проходит по каждому ребру, причем ровно один раз. Заметим|proof=Допустим, что первой в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно не пройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из стека <tex>S</tex> помещается вершина <tex>v</tex>, и она будет последней перемещена из он не мог стать пустым. Значит алгоритм пройдёт по всем рёбрам хотя бы один раз.Но так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может.<texbr>S}}Вершина </tex> в <tex>Pv</tex>. Следовательно, она с которой начат обход графа, будет последней вершиной помещена в путь <tex>P</tex>. Далее, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены, активной будет стартовая вершина <tex>v</tex> (Так как степени всех вершин четны). Значитизначально стек пуст, эта и вершина будет первой перемещена из <tex>Sv</tex> входит в <tex>P</tex>. Итакстек первой, то после прохода по окончании работы алгоритма в начале и в конце последовательности вершининцидентным ребрам, содержащейся в <tex>P</tex>алгоритм возвращается к данной вершине, находится вершина <tex>v</tex>. Иначе говорявыводит ее и опустошает стек, если эта последовательность представляет маршрут, то этот маршрут замкнутзатем выполнение программы завершается.<br>Покажем, что {{Лемма|statement=Напечатанный путь <tex>P</tex> это {{---}} корректный маршрут содержащий все ребра.<br>Допустимв графе, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из котором каждые две соседние вершины <tex>Su_i</tex>, и <tex>Su_{i+1}</tex> не мог стать пустым.будут образовывать ребро <tex>(u_i, u_{i+1}) \in E<br/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>wu</tex>, а следующей в <tex>S</tex> лежит <tex>uw</tex>. Возможны 2 варианта:#*На следующем шаге для вершины <tex>w</tex> не найдётся инцидентного ребра, тогда <tex>uw</tex> перемещена переместят в <tex>SP</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>uw</tex>. Следовательно, а значит она следующей попадет данная вершина первой поместится в <tex>P</tex> вслед за <tex>u</tex>, и ребро <tex>(w,u)</tex> будет представлено в <tex>P</tex>.}}{{Теорема|id=proof1|statement=Данный алгоритм находит корректный эйлеров путь.|proof=Из предыдущих лемм следует, что <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>) print(<tex>v</tex>)</font>=== Время работы ===Если реализовать поиск ребер инцидентных вершине и удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.<br>Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство <tex>\mathtt{deleted}</tex> бинарного типа. === Рекурсивная реализация за <tex>O(E)</tex> ===Заведём 2 массива: <tex>vis</tex> и <tex>first</tex> <br><tex>vis[i] (bool)</tex> - посещено ли ребро с индексом <tex>i</tex> <tex>(i \in 0..(E-1))</tex><br> (массив нужен, чтобы за <tex>O(1)</tex> проверять, доступно ребро или нет) <br><tex>first[u] (int)</tex> - индекс первой вершины <tex>v</tex> в списке смежных вершин, такой что ребро <tex>(u,v)</tex> не посещено <tex>(u \in 0..(V-1))</tex><br>(массив нужен, чтобы в среднем за <tex>O(1)</tex> находить доступное ребро) <br>

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

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

'''function''' findEulerPatheuler(v<tex>u</tex>): '''forwhile''' (first[<tex>u</tex>] < g[<tex>u</tex>].size()): <font color=darkgreen> //если first[<tex>u</tex>] = g[<tex>u</tex>].size, рёбра во все смежные вершины уже посещены</font> <tex>i</tex>,<tex>v, </tex> = g[<tex>u</tex>][first[<tex>u</tex>]] first[<tex>u) </tex>] += 1 '''inif''' (!vis[<tex>Ei</tex> remove(v, u]):<br> findEulerPath(u) print(v)vis[<tex>i</fonttex> ] == Время работы ==Если реализовать удаление ребер за true<br> euler(<tex>O(1)v</tex> )<br> print(для этого для каждого ребра достаточно добавить свойство deleted типа boolean), то алгоритм будет работать за <tex>O(E)v</tex>.)</font> <br>

* [[Эйлеров цикл, Эйлеров путь, Эйлеровы Гамильтоновы графы, Эйлеровость орграфов]]* [[Покрытие ребер рёбер графа путями]]* [[Произвольно вычерчиваемые из заданной вершины графы]]