|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Эйлеров циклМатериал из CustisWikiЭто снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений. Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз. Замкнутый эйлеров путь называется эйлеровым обходом или эйлеровым циклом. Эйлеров граф — граф, в котором существует эйлеров обход. Критерий эйлеровости графа: «Эйлеров обход в графе существует тогда и только тогда, когда граф связный и все его вершины четной степени». Нахождение эйлерова цикла можно выполнить эффективно, с помощью нижепредставленного алгоритма, основная идея которого содержиться в построении произвольных замкнутых циклов (если вы окажетесь в эйлеровом графе, и будете идти произвольно по его ребрам, сжигая их после своего прохода, то рано или поздно вы вернетесь в точку старта), и обьединении таких циклов в единый эйлеров цикл. 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 [] + {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]
Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». |
![]() |
![]() |
![]() |