Эйлеров цикл - История изменений

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:46:19Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

WikiSysop: 1 версия

2008-08-04T09:55:55Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2005-12-06T04:41:26Z

реплицировано из внутренней CustisWiki

Новая страница

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

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

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

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

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

<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}}

StasFomin: - переход на

2005-12-05T12:22:44Z

<graphviz> - переход на <graph>

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

@@ Строка 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;
--> 1[fontcolor="blue",label="1",style=solid];
--> 4[fontcolor="blue",label="2",style=solid];
--> 1[fontcolor="blue",label="3",style=solid];
--> 2[fontcolor="blue",label="4",style=solid];
--> 3[fontcolor="blue",label="5",style=solid];
--> 4[fontcolor="blue",label="6",style=solid];
--> 0[fontcolor="blue",label="7",style=solid];
-−
-</graph>
-−
-−
-[[Category:Алгоритмы]]
-{{replicate-from-custiswiki-to-lib}}

← Предыдущая	Версия 12:22, 5 декабря 2005
(нет различий)