Эйлеров цикл

Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз.

Замкнутый эйлеров путь называется эйлеровым обходом или эйлеровым циклом.

Эйлеров граф — граф, в котором существует эйлеров обход.

Критерий эйлеровости графа: «Эйлеров обход в графе существует тогда и только тогда, когда граф связный и все его вершины четной степени».

Нахождение эйлерова цикла можно выполнить эффективно, с помощью нижепредставленного алгоритма, основная идея которого содержиться в построении произвольных замкнутых циклов (если вы окажетесь в эйлеровом графе, и будете идти произвольно по его ребрам, сжигая их после своего прохода, то рано или поздно вы вернетесь в точку старта), и обьединении таких циклов в единый эйлеров цикл.

<code-python>

def euler_circuit(G):
   EP=[]  # Эйлеров цикл - массив вершин.
   
   #возвращает локальный замкнутый цикл    
   def euler(v):
       cycle={}
       while (G.degree(v)>0):  #пока не оказались в "безвыходной" вершине
           w=G.neighbors(v)[0] # берем $w$ --- первого попавшегося "соседа" $v$ 
           cycle[v]=w          # записываем ребро $(v,w)$ в $cycle$ и стираем его из графа
           G.delete_edge(v,w)
           v=w                 # повторяем все с вершиной $w$
       return cycle    

   # добавляет цикл к эйлерову пути
   def add_cycle():        
       print EP,"+",
       if len(EP)>0: # ищем вершину, к которой можно добавить цикл
           for i in range(0,len(EP)):
               if G.degree(EP[i])>0:
                   v=EP[i]
                   break
       else: # Подготавливаем пока пустой EP к присоединению цикла 
           v=G.nodes()[0] # выбираем первую попавшуюся вершину
           EP.append(v)   # и добавляем ее в EP
           i=0    
       c=euler(v)
       print c,"-->",    
       while c: # пока не перенесли все содержимое цикла   
           i=i+1; EP.insert(i,c[v]) #вставляем очередную вершину в EP        
           w=c[v] #переходим к следующей
           del c[v] #удаляя из цикла вставленную.
           v=w
       print EP

   #Проверка, необходимых и достаточных условий существования
   for v in G.nodes(): 
       if (G.degree(v) % 2)<>0: print "No Euler path!"; return
   
   while (G.number_of_edges()>0):
       add_cycle()          # добавляем цикл к эйлерову пути
           
   print EP
   return EP

</code-python>

[] + {0: 1, 1: 2, 2: 3, 3: 4, 4: 0} --> [0, 1, 2, 3, 4, 0]
[0, 1, 2, 3, 4, 0] + {1: 4, 4: 1} --> [0, 1, 4, 1, 2, 3, 4, 0]
[0, 1, 4, 1, 2, 3, 4, 0]

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.