from copy import copy
def eh_conexo(grafo):
v_0=list(grafo)[0] # comece pelo primeiro vertice do grafo.
cor_vertice = {v: 'vermelho' for v in grafo}
cor_vertice[v_0]='azul'
V=[v_0]
while len(V)!=0:
u=V.pop()
for v in grafo[u]:
if cor_vertice[v]=='vermelho':
cor_vertice[v]='azul'
V.append(v)
cor_vertice[u]='preto'
return list(cor_vertice.values()).count('preto')==len(grafo)
def lista_vertice_grau_impar(grafo):
lista_vertice_grau_impar= [] #inicia lista vazia
for k in grafo:
if len(grafo[k]) % 2 != 0:
lista_vertice_grau_impar.append(k)
return lista_vertice_grau_impar
def par_de_ligados(grafo):
par_de_ligados = []
for u in grafo:
for v in grafo[u]:
par_de_ligados.append((u,v))
return par_de_ligados
#Algorithm de Fleury's
def fleury(grafo):
if len(lista_vertice_grau_impar(grafo))>2 or len(lista_vertice_grau_impar(grafo))==1:
return 'nao eh eureliano'
else:
g=copy(grafo)
caminho=[]
if len(lista_vertice_grau_impar(g))==2:
v=lista_vertice_grau_impar(g)[0]
else:
v = list(g)[0]
while len(par_de_ligados(g)) > 0:
vertice_atual = v
for v in g[vertice_atual]:
g[vertice_atual].remove(v)
g[v].remove(vertice_atual)
ponte = not eh_conexo(g)
if ponte:
g[vertice_atual].append(v)
g[v].append(vertice_atual)
else:
break
if ponte:
g[vertice_atual].remove(v)
g[v].remove(vertice_atual)
g.pop(vertice_atual)
caminho.append((vertice_atual, v))
return caminho
G = {1:[2, 5], 2: [1, 3, 5], 3: [2, 4], 4: [3, 5, 6], 5: [1, 2, 4], 6: [4]}
G1 = {1: [2, 3, 4, 4], 2: [1, 3, 3, 4], 3: [1, 2, 2, 4], 4: [1, 1, 2, 3]}
print fleury(G1)