GIIT_AMA_1718_Clase_13112017

495 days ago by GIIT_AMA_1718

Coloración recursiva de un grafo bipartito

def bipartito(g): if len(g.edges())==0: # Si no hay aristas return {v:0 for v in g.vertices()} # Coloreamos todos los vértices con un color # Tenemos aristas, así que tomamos la primera u,v,_=g.edges()[0] g1=copy(g) g1.delete_edge(u,v) # Borramos la arista u,v de (una copia de) g gamma=bipartito(g1) # Coloreamos g menos la arista (u,v) por recursividad if gamma==-1: # Si no ha podido, devolvemos el error return -1 if gamma[u]!=gamma[v]: # Si el color de u y v es distinto return gamma # devolvemos esta coloración # Tenemos que gamma[u]==gamma[v]. Aplicamos el procedimiento recursivo de clase K=g1.connected_component_containing_vertex(v) # Nos quedamos con la componente conexa de v if u in K: # Si contiene a u, entonces el grafo no puede ser bipartito print 'El grafo no es bipartito' return -1 # u no está en la componente conexa de K. Así que intercambiamos los colores de esa componente y devolvemos la coloración for w in K: gamma[w]=1-gamma[w] return gamma 
       
g=graphs.RandomGNM(15,13) g.plot() 
       
gamma=bipartito(g) g.plot(vertex_colors={(1,1,1):[u for u in g.vertices() if gamma[u]==1],(0,0,0):[u for u in g.vertices() if gamma[u]==0]})