Персональные инструменты
 

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (1 версия)
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
Строка 1: Строка 1:
'''Эйлеровым путем''' в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз.
+
#REDIRECT [[discopal:{{PAGENAME}}]]
 
+
Замкнутый эйлеров путь называется '''эйлеровым обходом''' или '''эйлеровым циклом'''.
+
 
+
'''Эйлеров граф''' — граф, в котором существует эйлеров обход.
+
 
+
Критерий эйлеровости графа:
+
«Эйлеров обход в графе существует тогда и только тогда, когда граф связный и все его вершины четной степени».
+
 
+
Нахождение эйлерова цикла можно выполнить эффективно, с помощью нижепредставленного алгоритма, основная идея которого содержиться в построении произвольных замкнутых циклов (если вы окажетесь в эйлеровом графе, и будете идти произвольно по его ребрам, сжигая их после своего прохода, то рано или поздно вы вернетесь в точку старта), и обьединении таких циклов в единый эйлеров цикл.
+
 
+
<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]
+
 
+
<graph>
+
digraph G{ rankdir=LR;
+
0 -> 1[fontcolor="blue",label="1",style=solid];
+
1 -> 4[fontcolor="blue",label="2",style=solid];
+
4 -> 1[fontcolor="blue",label="3",style=solid];
+
1 -> 2[fontcolor="blue",label="4",style=solid];
+
2 -> 3[fontcolor="blue",label="5",style=solid];
+
3 -> 4[fontcolor="blue",label="6",style=solid];
+
4 -> 0[fontcolor="blue",label="7",style=solid];
+
}  
+
</graph>
+
 
+
 
+
[[Category:Алгоритмы]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:46, 13 июня 2011

  1. REDIRECT discopal:Эйлеров цикл