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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Отредактировано доказательство)
Строка 20: Строка 20:
 
     '''for''' v '''in''' <tex>V</tex>
 
     '''for''' v '''in''' <tex>V</tex>
 
         '''if''' vertexDegree(v) > 0 '''and''' '''not''' vis[v]  <font color=darkgreen>// если количество компонент связности, содержащие ребра, больше одной,</font>
 
         '''if''' vertexDegree(v) > 0 '''and''' '''not''' vis[v]  <font color=darkgreen>// если количество компонент связности, содержащие ребра, больше одной,</font>
             '''return''' ''false''                       <font color=darkgreen> // то граф не является эйлеровым</font>
+
             '''return''' ''false''                       <font color=darkgreen> // то граф не является эйлеровым</font>
 
     '''return''' ''true'' // граф является эйлеровым
 
     '''return''' ''true'' // граф является эйлеровым
 
   
 
   
Строка 36: Строка 36:
 
     '''return''' count
 
     '''return''' count
  
'''Код построения эйлерова цикла:'''
+
'''Код построения эйлерова пути:'''
  '''function''' findEulerPath(v : Vertex):
+
  '''function''' findEulerPath(v : Vertex): <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font>
     Stack stack
+
     Stack <tex>S</tex>
     stack.push(v)
+
     <tex>S</tex>.push(v)
     '''while not''' stack.isEmpty()
+
     '''while not''' <tex>S</tex>.isEmpty()
         w = stack.top()
+
         w = <tex>S</tex>.top()
 
         '''if''' exists (w, u) '''in''' <tex>E</tex>
 
         '''if''' exists (w, u) '''in''' <tex>E</tex>
             stack.push(u)
+
             <tex>S</tex>.push(u)
 
             remove(w, u)
 
             remove(w, u)
 
         '''else'''  
 
         '''else'''  
             stack.pop()
+
             <tex>S</tex>.pop()
 
             print(w)
 
             print(w)
 
</font>
 
</font>
  
 
== Доказательство ==
 
== Доказательство ==
Пусть <tex>P</tex> {{---}} напечатанный путь. Заметим, что первой в <tex>S</tex> помещается вершина <tex>v</tex>, и она будет последней перемещена из <tex>S</tex> в <tex>P</tex>. Следовательно, она будет последней вершиной в <tex>P</tex>. Далее, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены, активной будет стартовая вершина <tex>v</tex> (Так как степени всех вершин четны). Значит, эта вершина будет первой перемещена из <tex>S</tex> в <tex>P</tex>. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в <tex>P</tex>, находится вершина <tex>v</tex>. Иначе говоря, если эта последовательность представляет маршрут, то этот маршрут замкнут.<br>
+
1. Данный алгоритм проходит по каждому ребру, причем ровно один раз. Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из <tex>S</tex>, и <tex>S</tex> не мог стать пустым.<br>  
Покажем, что <tex>P</tex> это маршрут содержащий все ребра.<br>
+
Так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может. <br>
Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из <tex>S</tex>, и <tex>S</tex> не мог стать пустым.<br>
+
2. Напечатанный путь <tex>P</tex> {{---}} маршрут, содержащий все ребра графа, при этом не содержит ребра, не лежащие на пути графа. Будем говорить, что ребро <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>w</tex>, а следующей в <tex>S</tex> лежит <tex>u</tex>. Возможны 2 варианта:
Будем говорить, что ребро <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>w</tex>, а следующей в <tex>S</tex> лежит <tex>u</tex>. Возможны 2 варианта:
 
 
#На следующем шаге <tex>u</tex> перемещена в <tex>S</tex>. Тогда <tex>(w,u)</tex> представлено в <tex>P</tex>.
 
#На следующем шаге <tex>u</tex> перемещена в <tex>S</tex>. Тогда <tex>(w,u)</tex> представлено в <tex>P</tex>.
 
#Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине <tex>u</tex>. Ввиду четности степеней эта последовательность может закончиться только в вершине <tex>u</tex>, а значит она следующей попадет в <tex>P</tex> и <tex>(w,u)</tex> будет представлено в <tex>P</tex>.
 
#Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине <tex>u</tex>. Ввиду четности степеней эта последовательность может закончиться только в вершине <tex>u</tex>, а значит она следующей попадет в <tex>P</tex> и <tex>(w,u)</tex> будет представлено в <tex>P</tex>.
 
+
Из пунктов 1 и 2 следует, что <tex>P</tex> - искомый эйлеров путь.
Отсюда понятно, что последовательность вершин в <tex>P</tex> является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз.<br>
 
 
 
 
<tex> \Box </tex>
 
<tex> \Box </tex>
  
Строка 73: Строка 70:
 
== Время работы ==
 
== Время работы ==
 
Если реализовать поиск ребер инцидентных вершине и удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.<br>
 
Если реализовать поиск ребер инцидентных вершине и удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.<br>
Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин. Тогда удаление ребер будет выглядеть следующим образом:
+
Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство deleted бинарного типа.
<font size=2>
 
'''function''' remove(v : Vertex, index : '''int'''):
 
    graph[v][index] = graph[v].back()
 
    graph[v].pop()
 
</font>
 
  
 
== См. также ==
 
== См. также ==

Версия 17:53, 11 января 2015

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

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

Псевдокод

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

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

// Вспомогательные функции:
function dfs(v : Vertex, vis[] : boolean):
   vis[v] = true
   for (v, u) in [math]E[/math]
       if not vis[u]
           dfs(u, vis)

int vertexDegree(v : Vertex):
   int count = 0
   for (v, u) in [math]E[/math]
       count = count + 1
   return count

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

function findEulerPath(v : Vertex):   // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени 
   Stack [math]S[/math]
   [math]S[/math].push(v)
   while not [math]S[/math].isEmpty()
       w = [math]S[/math].top()
       if exists (w, u) in [math]E[/math]
           [math]S[/math].push(u)
           remove(w, u)
       else 
           [math]S[/math].pop()
           print(w)

Доказательство

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

  1. На следующем шаге [math]u[/math] перемещена в [math]S[/math]. Тогда [math](w,u)[/math] представлено в [math]P[/math].
  2. Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине [math]u[/math]. Ввиду четности степеней эта последовательность может закончиться только в вершине [math]u[/math], а значит она следующей попадет в [math]P[/math] и [math](w,u)[/math] будет представлено в [math]P[/math].

Из пунктов 1 и 2 следует, что [math]P[/math] - искомый эйлеров путь. [math] \Box [/math]

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

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

Время работы

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

См. также

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