Алгоритм построения Эйлерова цикла — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Псевдокод == <font size=3> findPath(v): for (v, u) from E remove (v, u) findPath(u) print v </font> == Доказательств…»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 43 промежуточные версии 16 участников)
Строка 1: Строка 1:
== Псевдокод ==
+
== Алгоритм ==
<font size=3>
+
=== Описание алгоритма ===
   findPath(v):
+
Алгоритм находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном]], так и в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]]. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить алгоритм из вершины с нечетной степенью.<br>
     for (v, u) from E
+
Алгоритм напоминает поиск в глубину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины <tex>v</tex> строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в [[Стек | стеке]] <tex>S</tex>. Когда наступает такой момент, что для текущей вершины <tex>w</tex> все инцидентные ей ребра уже пройдены, записываем вершины из <tex>S</tex> в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам.
      remove (v, u)
+
 
      findPath(u)
+
=== Псевдокод ===
    print v
+
<font size=2>
 +
'''Код проверки графа на эйлеровость:'''
 +
'''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''   <font color=darkgreen>// граф является эйлеровым</font>
 +
 
 +
'''Код построения эйлерова пути:'''
 +
'''function''' findEulerPath(<tex>v</tex>): <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font>
 +
     '''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>.push(<tex>v</tex>)  <font color=darkgreen>// <tex>S</tex> {{---}} стек</font>
 +
    '''while not''' <tex>S</tex>.empty()
 +
        <tex>w = </tex> <tex>S</tex>.top()
 +
        found_edge = '''False'''
 +
        '''for''' <tex>u : u \in V</tex>
 +
            '''if''' (<tex>w, u</tex>) <tex>\in E</tex> <font color=darkgreen> // нашли ребро, по которому ещё не прошли</font>
 +
                <tex>S</tex>.push(<tex>u</tex>) <font color=darkgreen> // добавили новую вершину в стек</font>
 +
                <tex>E</tex>.remove(<tex>w, u</tex>)
 +
                found_edge = '''True'''
 +
                '''break'''
 +
        '''if''' '''not''' found_edge
 +
            <tex>S</tex>.pop() <font color=darkgreen> // не нашлось инцидентных вершине <tex>w</tex> рёбер, по которым ещё не прошли</font>
 +
            print(<tex>w</tex>)
 
</font>
 
</font>
  
== Доказательство ==
+
=== Доказательство корректности ===
 +
{{Лемма
 +
|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>
 +
'''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> бинарного типа.
  
Если мы запустим процедуру ''findPath'' из какой-нибудь вершины <tex> v_1 </tex>, то самой первой она и будет напечатана, так как у всех остальных вершин изначально четная степень, если мы в какую-нибудь из них войдем по одному ребру, то сможем выйти по другому. Если записать все вершины, в порядке входа в них, то получится циклический путь <tex> v_1 v_2 v_3 \ldots v_k</tex>. При выходе из функции вершины будут напечатаны в обратном порядке, относительно того, как они шли в циклическом пути <tex> v_k v_{k - 1} \ldots v_i</tex>. Возврат из рекурсии будет осуществляться до того момента, как мы либо совсем выйдем из рекурсии (что значит, что наш алгоритм напечатал циклический путь), либо из вершины <tex>v_i </tex> будут существовать еще ребра. Во втором случае, алгоритм опустится в рекурсию (и у вершины <tex> v_i </tex> степень станет нечетной, следовательно, как и в первом случае, из нее мы выйдем в первую очередь) и найдет какой-то эйлеров цикл, который содержит вершину <tex> v_i </tex> и состоит из некоторых ребер, которые мы еще не удаляли. После этого у нас будет напечатан <tex> v_k v_{k-1} \ldots v_i \ldots v_i </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>
  
Почему напечатанный цикл будет эйлеровым? Во-первых, так как все компоненты связности, кроме, может быть, одной состоят из одной вершины, то если ''findPath'' запустится от вершины с ненулевой степенью, он просмотрит все вершины и все ребра из этой компоненты связности.  
+
Изначально оба массива заполнены нулями. <br>
Во-вторых, по каждому ребру алгоритм пройдет не более одного раза, потому что после просмотра этого ребра, оно сразу же удаляется из множества. <tex> \Box </tex>
 
  
== Время работы ==
+
Граф будем хранить в виде списков смежных вершин. Для каждой вершины <tex>u</tex> построим список <tex>g[u]</tex> из пар вида <tex>(i,v)</tex> <br>
Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>, так как каждое ребро будет просмотрено не более одного раза и запусков функции будет не больше, чем количество ребер.
+
<tex>i</tex> - индекс ребра <tex>(u,v)</tex> <br>
 +
<tex>v</tex> - номер смежной вершины <br>
  
 +
После ввода графа нужно запустить <tex>euler(0)</tex> или от любой другой вершины. <br>
 +
<font size=2>
 +
'''function''' euler(<tex>u</tex>):
 +
    '''while''' (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
 +
      '''if''' (!vis[<tex>i</tex>]):<br>        vis[<tex>i</tex>] = true<br>        euler(<tex>v</tex>)<br>        print(<tex>v</tex>)
 +
</font> <br>
 
== См. также ==
 
== См. также ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
+
* [[Гамильтоновы графы]]
 +
* [[Покрытие рёбер графа путями]]
 +
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 +
 
 +
== Источники информации ==
 +
* [http://ru.wikipedia.org/wiki/Эйлеров_цикл Википедия {{---}} Эйлеров цикл]
 
* [http://e-maxx.ru/algo/euler_path  Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]
 
* [http://e-maxx.ru/algo/euler_path  Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]
 +
* [http://ивтб.рф/exams/саод/36.htm  Статья про нахождение Эйлерова пути с реализацией на Pascal на сайте ивтб.рф]
 +
* [https://www.youtube.com/watch?v=ryw059C6oK8  Видео-лекция А.С.Станкевича про нахождение Эйлерова цикла с реализацией на C++ на сайте youtube.com]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
 +
[[Категория: Эйлеровы графы]]

Текущая версия на 19:20, 4 сентября 2022

Алгоритм

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

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

Псевдокод

Код проверки графа на эйлеровость:

boolean checkForEulerPath():
   int OddVertex [math]= 0[/math]
   for [math]v : v[/math] [math]\in[/math] [math]V[/math]
       if [math]\operatorname{deg}[/math]([math]v[/math]) mod [math]2 == 1[/math]
           OddVertex++
   if OddVertex [math] \gt  2 [/math]// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым
       return false
   boolean visited([math]|V|[/math], false) // массив инициализируется значениями false
   for [math]v : v[/math] [math]\in[/math] [math]V[/math]
       if [math]\operatorname{deg}[/math]([math]v[/math]) [math] \gt  0[/math]
           dfs([math]v[/math], visited)
           break
   for [math]v : v[/math] [math]\in[/math] [math]V[/math]
       if [math]\operatorname{deg}[/math]([math]v[/math]) [math] \gt  0[/math] and not visited[[math]v[/math]]   // если количество компонент связности, содержащие ребра, больше одной,
           return false              // то граф не является эйлеровым
   return true   // граф является эйлеровым

Код построения эйлерова пути:

function findEulerPath([math]v[/math]):   // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени 
   for [math]u : u \in V[/math]
       if [math]\operatorname{deg}[/math]([math]u[/math]) mod [math]2 == 1[/math]
           [math]v = u[/math]
           break
   [math]S[/math].push([math]v[/math])  // [math]S[/math] — стек
   while not [math]S[/math].empty()
       [math]w = [/math] [math]S[/math].top()
       found_edge = False
       for [math]u : u \in V[/math]
           if ([math]w, u[/math]) [math]\in E[/math]  // нашли ребро, по которому ещё не прошли
               [math]S[/math].push([math]u[/math])  // добавили новую вершину в стек
               [math]E[/math].remove([math]w, u[/math])
               found_edge = True
               break
       if not found_edge
           [math]S[/math].pop()  // не нашлось инцидентных вершине [math]w[/math] рёбер, по которым ещё не прошли
           print([math]w[/math])

Доказательство корректности

Лемма:
Данный алгоритм проходит по каждому ребру, причем ровно один раз.
Доказательство:
[math]\triangleright[/math]

Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно не пройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из стека [math]S[/math], и он не мог стать пустым. Значит алгоритм пройдёт по всем рёбрам хотя бы один раз.

Но так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может.
[math]\triangleleft[/math]

Вершина [math]v[/math], с которой начат обход графа, будет последней помещена в путь [math]P[/math]. Так как изначально стек пуст, и вершина [math]v[/math] входит в стек первой, то после прохода по инцидентным ребрам, алгоритм возвращается к данной вершине, выводит ее и опустошает стек, затем выполнение программы завершается.

Лемма:
Напечатанный путь [math]P[/math] — корректный маршрут в графе, в котором каждые две соседние вершины [math]u_i[/math] и [math]u_{i+1}[/math] будут образовывать ребро [math](u_i, u_{i+1}) \in E[/math].
Доказательство:
[math]\triangleright[/math]

Будем говорить, что ребро [math](w,u)[/math] представлено в [math]S[/math] или [math]P[/math], если в какой-то момент работы алгоритма вершины [math]w[/math] и [math]u[/math] находятся рядом. Каждое ребро графа представлено в [math]S[/math]. Рассмотрим случай, когда из [math]S[/math] в [math]P[/math] перемещена вершина [math]u[/math], а следующей в [math]S[/math] лежит [math]w[/math]. Возможны 2 варианта:

  • На следующем шаге для вершины [math]w[/math] не найдётся инцидентного ребра, тогда [math]w[/math] переместят в [math]P[/math], и ребро [math](w,u)[/math] будет представлено в [math]P[/math].
  • Иначе будет пройдена некоторая последовательность ребер [math]{u_1, u_2, ..., u_k}[/math], начинающаяся в вершине [math]w[/math] и проходящая по ребру [math](w, u_1)[/math]. Докажем, что данный проход [math]{u_1, u_2, ..., u_k}[/math] закончится в вершине [math]w[/math]:
  1. Ребро [math](u_{k-1}, u_k)[/math] не может быть инцидентно вершинам [math]u_1, \dots , u_{k-2}[/math], иначе степень вершины [math]u_k[/math] окажется нечетной.
  2. Предположим, что [math](u_{k-1}, u_k)[/math] инцидентно вершине, пройденной при обходе графа из вершины [math]u[/math]. Но это неверно, так как тогда бы данные вершины пройдены ранее.
Из этого следует, что мы закончим обход в вершине [math]w[/math]. Следовательно, данная вершина первой поместится в [math]P[/math] вслед за [math]u[/math], и ребро [math](w, u)[/math] будет представлено в [math]P[/math].
[math]\triangleleft[/math]
Теорема:
Данный алгоритм находит корректный эйлеров путь.
Доказательство:
[math]\triangleright[/math]
Из предыдущих лемм следует, что [math]P[/math] — искомый эйлеров путь и алгоритм работает корректно.
[math]\triangleleft[/math]

Рекурсивная реализация

function findEulerPath([math]v[/math] : Vertex):
   for [math](v,u)[/math] [math]\in[/math] [math]E[/math]
       remove [math](v, u)[/math]
       findEulerPath([math]u[/math])
   print([math]v[/math])

Время работы

Если реализовать поиск ребер инцидентных вершине и удаление ребер за [math]O(1)[/math], то алгоритм будет работать за [math]O(E)[/math].
Чтобы реализовать поиск за [math]O(1)[/math], для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство [math]\mathtt{deleted}[/math] бинарного типа.

Рекурсивная реализация за [math]O(E)[/math]

Заведём 2 массива: [math]vis[/math] и [math]first[/math]
[math]vis[i] (bool)[/math] - посещено ли ребро с индексом [math]i[/math] [math](i \in 0..(E-1))[/math]
(массив нужен, чтобы за [math]O(1)[/math] проверять, доступно ребро или нет)
[math]first[u] (int)[/math] - индекс первой вершины [math]v[/math] в списке смежных вершин, такой что ребро [math](u,v)[/math] не посещено [math](u \in 0..(V-1))[/math]
(массив нужен, чтобы в среднем за [math]O(1)[/math] находить доступное ребро)

Изначально оба массива заполнены нулями.

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

После ввода графа нужно запустить [math]euler(0)[/math] или от любой другой вершины.

function euler([math]u[/math]):
   while (first[[math]u[/math]] < g[[math]u[/math]].size()):  //если first[[math]u[/math]] = g[[math]u[/math]].size, рёбра во все смежные вершины уже посещены
      [math]i[/math],[math]v[/math] = g[[math]u[/math]][first[[math]u[/math]]]
      first[[math]u[/math]] += 1
      if (!vis[[math]i[/math]]):
vis[[math]i[/math]] = true
euler([math]v[/math])
print([math]v[/math])


См. также

Источники информации