GIIT_AMA_1415_Tema_2_Grafos_Arboles_Mapas_Coloraciones

1043 days ago by trinidad1415

Árboles, mapas y coloraciones

Algunas funciones útiles para analizar grafos

Sage dispone de multitud de herramientas para estudiar los grafos. en esta sección veremos algunas de ellas.

# Generamos un grafo para pruebas a partir de su secuencia de grados g=graphs.DegreeSequence([6,4,4,4,4,4,2,4,2,4]) show(g,figsize=3) 
       

Grafos eulerianos y hamiltonianos

Vamos a ver los comandos para ver si un grafo es euleriano o hamiltoniano en Sage y para generar caminos eulerianos o circuitos.

# Comprobamos si el grafo es euleriano o hamiltoniano g.is_eulerian(),g.is_hamiltonian() 
       
# Generamos el circuito euleriano eu=g.eulerian_circuit() eu 
       
# Guardamos las aristas como un grafo dirigido, etiquetándolas en orden circuito=DiGraph([(eu[k][0],eu[k][1],k+1) for k in range(len(eu))]) # Mostramos el circuito show(circuito,edge_labels=True,layout="circular") 
       
# Lo mismo con el ciclo hamiltoniano show(g.hamiltonian_cycle()) 
       

Dijkstra

Sage tiene implementado el algoritmo de Dijkstra para calcular el camino más corto entre dos vértices.

B = {0:{1:2,2:5,3:4},1:{2:2,4:7},2:{3:1,4:4,5:3},3:{5:4},4:{5:1,6:5},5:{6:7}} g_etiquetado = Graph(B,weighted=True) g_etiquetado.show(edge_labels=True) 
       
g_etiquetado.shortest_path(0,6,by_weight=True) 
       

Planos

Veamos cómo obtener si un grafo es plano.

# Generamos un grafo aleatorio para pruebas con 10 vértices y 50% de probabilidad para cada arista g=graphs.RandomGNP(10,0.4) show(g,figsize=3) 
       

Usamos is_planar() para obtener si es plano o no. (Genera grafos aleatorios hasta que obtengas uno plano.)

g.is_planar() 
       

Si es plano, podemos pedirle que represente un mapa.

g.show(layout='planar') 
       

Coloraciones

Vamos a ver cómo obtener una coloración de un grafo y dibujar el grafo con dicha coloración.

Para obtener la coloración, usamos coloring(). Este método agrupa los vértices que tendrían el mismo color (devuelve una lista de listas de vértices).

Para colorearlos, definimos un diccionario que asigna un color a cada grupo.

vertices_color=g.coloring() colores={ (random(),random(),random()):vertices for vertices in vertices_color} g.show(vertex_colors=colores) 
       

Generadores de grafos

Sage nos permite generar los grafos de modo exhaustivo, por ejemplo, para comprobar conjeturas u obtener ejemplos. Hay que tener en cuenta que el número de grafos posibles crece a gran velocidad, así que sólo podremos probar con un número pequeño de vértices y aristas.

# Todos los grafos con tres vértices (salvo isomorfismos) for G in graphs(3): G.show(figsize=2) 
       
# Contamos los grafos con 2, 3, 4, ... 7 vértices for i in [2..7]: print len([g for g in graphs(i)]) 
       
# Todos los grafos con 5 vértices y 4 aristas for g in graphs(5, size=4): show(g,figsize=2) 
       
# Grafos planos de 7 vértices y 15 aristas salvo isomorfismos for g in graphs(7, lambda g: g.is_planar(), size=15): g.show(figsize=2) 
       
 
       

Grafo de una función recursiva

Si tenemos una función recursiva, podemos considerar el grafo cuyos vértices son cada uno de los conjuntos de parámetros para los que se ha llamado la función y tenemos una arista que va desde un vértice v a otro w si la función con parámetro v llama a w.

El siguiente "decorador" crea el grafo de llamadas de  una función recursiva.

def grafo_llamadas(f): class G(object): def __init__(self, f): self.f=f self.stack = [] self.g = DiGraph() def __call__(self, *args, **kwds): if self.stack: sargs = ','.join(str(a) for a in args) last = ','.join(str(a) for a in self.stack[-1]) if self.g.has_edge(last, sargs): l = self.g.edge_label(last, sargs) self.g.set_edge_label(last, sargs, l + 1) else: self.g.add_edge(last, sargs, 1) else: self.g = DiGraph() self.stack.append(args) v = self.f(*args) self.stack.pop() return v def grafo(self): return self.g return G(f) 
       

Para usar el decorador, debemos escribir @grafo_llamadas en la celda en la que definamos la función.

@grafo_llamadas def fibo(n): if n<=2: return 1 else: return fibo(n-1) + fibo(n-2) 
       

El decorador nos generará el grafo de llamadas cada vez que ejecutemos la función. Las etiquetas de las aristas indican cuantas veces se ha pasado por esa arista en la llamada.

fibo(6) g = fibo.grafo() g.show(edge_labels=True) 
       
fibo(7) g = fibo.grafo() g.show(edge_labels=True) 
       

El decorador @cached_function hace que una función recursiva vaya guardando los valores que calcula.

@grafo_llamadas @cached_function def fibo_cached(n): if n<=2: return 1 else: return fibo_cached(n-1) + fibo_cached(n-2) 
       
fibo_cached(6) g = fibo_cached.grafo() g.show(edge_labels=True) 
       

Veamos un segundo ejemplo con las particiones de un número (una partición de un número natural n es una sucesión de números k1, ..., kr tal que n=k1+k2+...+kr).

@grafo_llamadas def particiones(n, k): if k == n: return [[1]*n] if k == 1: return [[n]] if not(0 < k < n): return [] ls1 = [p+[1] for p in particiones(n-1, k-1)] ls2 = [[parte+1 for parte in p] for p in particiones(n-k, k)] return ls1 + ls2 
       
particiones(8,3) g = particiones.grafo() g.show(edge_labels=True, figsize=(8,8), vertex_size=500) 
       
particiones(10,4) g = particiones.grafo() g.show(edge_labels=True, figsize=(8,8), vertex_size=500)