GIIT_AMA_1718_T2_Tutorial_2

666 days ago by GIIT_AMA_1718

Teoría de Grafos (Tutorial 2)

Representación de grafos

En este tutorial vamos a ver distintas opciones para representar los grafos con Sage. Esto nos permitirá visualizarlos mejor y también familiarizarnos con el modo de trabajar con grafos.

Comencemos con un grafo clásico, el grafo de Petersen (puedes consultar sus propiedades en Wikipedia). Para representar el grafo, podemos usar el comando plot.

P = graphs.PetersenGraph() P.plot() 
       

La representación anterior no permite destacar ninguna propiedad del grafo. Vamos a ir viendo cómo modificar el estilo y la disposición de los vértices del grafo (para obtener todas las opciones, se puede consultar la documentación). En primer lugar, modificaremos el color de los vértices. Para ello se crea un diccionario, un tipo de datos que consiste en un conjunto de parejas, separadas por :. El primer elemento de la pareja se denomina clave y el segundo valor. En el caso de los colores de los vértices de un grafo, la clave será el color y el valor la lista de vértices que se colorean con dicho color. Además, cambiaremos el tamaño de los vértices con vertex_size.

d = {'#FF0000':[0,5], '#FF9900':[1,6], '#FFFF00':[2,7], '#00FF00':[3,8], '#0000FF':[4,9]} P.plot(vertex_colors=d,vertex_size=500) 
       

En el caso de querer cambiar el color de las aristas, funciona del mismo modo. Para ilustrarlo, vamos a tratar de hacer algo más complejo; cambiaremos a color rojo el ciclo exterior. Es decir, todas las aristas cuyos vértices estén en el conjunto {0,1,2,3,4}.

color_aristas={'#FF0000':[ e for e in P.edges() if (e[0] in {0,1,2,3,4}) and (e[1] in {0,1,2,3,4})], '#000000':[ e for e in P.edges() if not(e[0] in {0,1,2,3,4}) or not(e[1] in {0,1,2,3,4})]} color_aristas 
       
P.plot(edge_colors=color_aristas,vertex_colors=d,vertex_size=500) 
       

Además, podemos poner nombres a las aristas. Para ello, recorremos las aristas y usamos set_edge_label. Para mostrar las etiquetas, usamos la opción edge_labels=true en la función plot. Vamos a marcar las aristas del ciclo exterior como 1,2,3,4,5 y como 0 las del interior.

for e in P.edge_iterator(): # Recorremos las aristas u,v,_=e # Guardamos los valores de los v√©rtices if (u in {0,1,2,3,4}) and (v in {0,1,2,3,4}): if not(min([u,v])==0 and max([u,v])==4): P.set_edge_label(u,v,min([u,v])+1) else: P.set_edge_label(u,v,5) else: P.set_edge_label(e[0],e[1],0) P.plot(edge_colors=color_aristas,vertex_colors=d,vertex_size=500,edge_labels=true) 
       

Además, podemos indicarle que use las etiquetas para colorear el grafo:

P.plot(color_by_label=True,edge_labels=True,vertex_colors=d,vertex_size=500) 
       

Grafo dirigido y/o etiquetado

Todo lo anterior es válido para grafos dirigidos, sin más que cambiar Graph por DiGraph. Por ejemplo, convertimos el grafo de Petersen en un digrafo y aplicamos lo anterior.

P=DiGraph(P) P.plot(vertex_colors=d) 
       

Vamos ahora a cambiar el color de las aristas. En lugar de cambiar todas las aristas exteriores, cambiaremos sólo aquellas que forman un ciclo. Además, no vamos a mostrar los nombres de los vértices (vertex_labels=false).

# Generamos la lista de aristas la=zip([0..4],[1..4]+[0]) la 
       
# Usamos el color rojo para las aristas del ciclo y un gris claro para el resto color_aristas={'#FF0000':[ e for e in P.edges() if (e[0],e[1]) in la], '#AAAAAA':[ e for e in P.edges() if not((e[0],e[1]) in la)]} P.plot(edge_colors=color_aristas,vertex_colors=d,vertex_size=500,vertex_labels=false) 
       

Practica.

1. Representa el grafo de Petersen de modo que los vértices exteriores (del 0 al 4) estén en negro y los interiores en blanco. No representes los nombres de los vértices.

2. Representa en una misma gráfica el grafo de Petersen y su complemento. Para ello representa el grafo completo, creando una copia del grafo de Petersen (puedes usar copy o crear otro nuevo con graphs) y añade las aristas que no estén (por ejemplo, recorriendo todas las parejas u,v de vértices del grafo y añadiendo las aristas que no estén). Puedes usar una nueva etiqueta para las aristas que añadas y así simplificas dibujarlas. Dibuja en un color las aristas que no estén en el grafo de Petersen y en otro las que estén.

3. Representa el grafo de Pegersen como un digrafo, mostrando en un color todas las aristas menos las que van de los vértices exteriores (0,1,2,3,4) a los interiores (5,6,7,8,9), que se representarán en otro color.