|
|
| Строка 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}}
| + | |
