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

Материал из Викиконспекты
Перейти к: навигация, поиск
(слово ширина)
(Псевдокод)
Строка 8: Строка 8:
 
'''Код проверки графа на эйлеровость:'''
 
'''Код проверки графа на эйлеровость:'''
 
  '''boolean''' checkForEulerPath():
 
  '''boolean''' checkForEulerPath():
     '''int''' numberOfOdd = 0
+
     '''int''' OddVertex <tex>= 0</tex>
     '''for''' <tex>v</tex> <tex>\in</tex> <tex>V</tex>
+
     '''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex>
         '''if''' <tex>\operatorname{deg} v</tex> '''mod''' 2 == 1
+
         '''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) '''mod''' <tex>2 == 1</tex>
             numberOfOdd = numberOfOdd + 1
+
             OddVertex++
     '''if''' numberOfOdd > 2   <font color=darkgreen>// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым</font>
+
     '''if''' OddVertex <tex> > 2 </tex><font color=darkgreen>// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым</font>
 
         '''return''' ''false''
 
         '''return''' ''false''
     '''boolean''' vis[<tex>|V|</tex><font color=darkgreen>// инициализировать массив значениями ''false''</font>
+
     '''boolean''' visited(<tex>|V|</tex>, ''false'') <font color=darkgreen>// массив инициализируется значениями ''false''</font>
     '''for''' <tex>v</tex> <tex>\in</tex> <tex>V</tex>
+
     '''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex>
         '''if''' <tex>\operatorname{deg} v</tex> > 0
+
         '''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) <tex> > 0</tex>
             dfs(<tex>v</tex>, vis)
+
             dfs(<tex>v</tex>, visited)
             break
+
             '''break'''
     '''for''' <tex>v</tex> <tex>\in</tex> <tex>V</tex>
+
     '''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex>
         '''if''' <tex>\operatorname{deg} v</tex> > 0 '''and''' '''not''' vis[<tex>v</tex>]  <font color=darkgreen>// если количество компонент связности, содержащие ребра, больше одной,</font>
+
         '''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''' ''false''            <font color=darkgreen> // то граф не является эйлеровым</font>
 
     '''return''' ''true''  <font color=darkgreen>// граф является эйлеровым</font>
 
     '''return''' ''true''  <font color=darkgreen>// граф является эйлеровым</font>
  
 
'''Код построения эйлерова пути:'''
 
'''Код построения эйлерова пути:'''
  '''function''' findEulerPath(<tex>v</tex> : Vertex):  <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font>
+
  '''function''' findEulerPath(<tex>v</tex>):  <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font>
     Stack S
+
    '''for''' <tex>u : u \in V</tex>
     S.push(<tex>v</tex>)
+
        '''if''' <tex>\operatorname{deg}</tex>(<tex>u</tex>) '''mod''' <tex>2 == 1</tex>
     '''while not''' S.isEmpty()
+
            <tex>v = u</tex>
         <tex>w</tex> = S.top()
+
            '''break'''
         '''if''' <tex>(w, u)</tex> <tex>\in</tex> <tex>E</tex>
+
     Stack <tex>S</tex>
            S.push(<tex>u</tex>)
+
     <tex>S</tex>.push(<tex>v</tex>)
            remove <tex>(w, u)</tex>
+
     '''while not''' <tex>S</tex>.empty()
         '''else'''  
+
         <tex>w = </tex> <tex>S</tex>.top()
             S.pop()
+
         '''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>)
 +
                '''break'''
 +
         '''if''' <tex> w == S</tex>.top()
 +
             <tex>S</tex>.pop() <font color=darkgreen> // не нашлось инцидентных вершине <tex>w</tex> рёбер, по которым ещё не прошли</font>
 
             print(<tex>w</tex>)
 
             print(<tex>w</tex>)
 
</font>
 
</font>

Версия 10:35, 6 декабря 2015

Алгоритм

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

Алгоритм находит Эйлеров цикл как в ориентированном, так и в неориентированном графе. Перед запуском алгоритма необходимо проверить граф на эйлеровость. Чтобы построить Эйлеров путь, нужно запустить алгоритм из вершины с нечетной степенью.
Алгоритм напоминает поиск в ширину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины [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
   Stack [math]S[/math]
   [math]S[/math].push([math]v[/math])
   while not [math]S[/math].empty()
       [math]w = [/math] [math]S[/math].top()
       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])
               break
       if [math] w == S[/math].top()
           [math]S[/math].pop()  // не нашлось инцидентных вершине [math]w[/math] рёбер, по которым ещё не прошли
           print([math]w[/math])

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

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

TODO: Довести до ума
Данный алгоритм проходит по каждому ребру, причем ровно один раз. Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из [math]S[/math], и [math]S[/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})[/math], принадлежащее [math]E[/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 варианта:

  1. На следующем шаге [math]w[/math] перемещена в [math]P[/math]. Тогда [math](w,u)[/math] представлено в [math]P[/math].
  2. Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине [math]w[/math], и проходящая по ребру [math](w, u_1)[/math]. Докажем, что данный проход [math]T[/math] [math]{u_1, u_2, ..., u_k}[/math] закончится в вершине [math]w[/math]: ребро [math](u_{k-1}, u_k)[/math] не может быть инцидентно вершинам [math]u_1, \dots , u_{k-2}[/math]. Иначе степень вершины [math]u_k[/math] будет нечетной. Предположим, что [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]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] бинарного типа.

См. также

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