GIIT_AMA_1314_Grafos

1420 days ago by trinidad

Teoría de Grafos

Representación de grafos

Comenzaremos viendo los distintos métodos para representar grafos en Sage (lista de adyacencia, lista de incidencia, matriz de adyacencia y matriz de incidencia) y también las opciones para su representación gráfica.

Lista de adyacencia

A partir de la lista de sus aristas, podemos definir un grafo en Sage utilizando add_edge.

g=Graph({}) l=[(1,2),(3,1),(1,4),(2,5),(2,4),(3,5)] for a in l: g.add_edge(a) g.show(figsize=5) 
       

Lista de incidencia

Podemos definir el grafo mediante su lista de incidencia. Para ello deberemos pasar como parámetro a Graph un "diccionario", es decir, una lista entre llaves de modo que cada elemento es un vértice, dos puntos y la lista de vertices a los que está unido.

g = Graph({0:[1,2,3], 2:[4]}); g.show(figsize=5) 
       

Matriz de adyacencia

Recordemos que la matriz de adyacencia es una matriz que en la posición $(i,j)$ guarda un $1$ si los vértices $i$ y $j$ son adyacentes y un $0$ en caso contrario. Si pasamos una matriz de este tipo al constructor Graph, genera un grafo con esa matriz de adyacencia. 

M=matrix([[0, 1, 0, 1],[1, 0, 1, 0],[0, 1, 0, 1],[1, 0, 1, 0]]);M 
       
g=Graph(M);g.show(figsize=5) 
       

Matriz de incidencia

En la matriz de incidencia, cada fila corresponde a una arista, indicando con un $-1$ y un $1$ son vertices incidentes a dicha arista. Sin embargo en Sage se utiliza cada columna como arista, así que debemos trasponer las matrices.

M = Matrix([[-1,0,0,0,1,0],[ 1,-1,0,0,0,0],[ 0,1,-1,0,0,0], [0,0,1,-1,0,0], [0,0,0,1,-1,0]]); M 
       
g=Graph(M.transpose());show(g) 
       

Editor de grafos

Para generar grafos de modo rápico (por ejemplo, para elaborar ejemplos para probar algoritmos) lo más práctico es utilizar el editor de grafos. Se ejecuta mediante el comando graph_editor. Si pasamos un grafo como parámetro al editor de grafos, será este el grafo que editemos. Se pueden añadir vértices, mover vértices y añadir aristas. En "variable name" debemos escribir el nombre de variable en el que guardará el grafo. Una vez terminada la edición, pulsamos save.

graph_editor(); 
       

Representando grafos

Los siguientes ejemplos muestran cómo cambiar el color de los vértices y su tamaño o el de las aristas. Para ello se crea un diccionario (una lista entre llaves) de modo que cada entrada de la lista sea una pareja separada por :, el elemento de la izquierda será el color y el de la derecha la lista de elementos a dibujar con ese color.

P = graphs.PetersenGraph() d = {'#FF0000':[0,5], '#FF9900':[1,6], '#FFFF00':[2,7], '#00FF00':[3,8], '#0000FF':[4,9]} P.plot(vertex_colors=d,vertex_size=500).show(figsize=4) 
       
P = graphs.PetersenGraph() E=P.edges(); e={'#FFFF00':[E[k] for k in [0..2]],'#FF00FF':[E[k] for k in [3,5..14]],'#00FFFF':[E[k] for k in [4,6..14]]} P.plot(edge_colors=e,thickness=3).show(figsize=4) 
       
stnc = 'abcdeda' g = Graph({}, loops=True, multiedges=True) for a,b in [(stnc[i], stnc[i+1]) for i in xrange(len(stnc)-1)]: g.add_edge(a, b, 'peso '+b) g.plot(color_by_label=True,edge_labels=True, edge_style='solid',thickness=3).show(figsize=(4,7)) 
       

Grafo dirigido y/o etiquetado

Todo lo anterior es válido para grafos dirigidos, sin más que cambiar Graph por DiGraph.

stnc = 'abcdeda' g = DiGraph({}, loops=True, multiedges=True) for a,b in [(stnc[i], stnc[i+1]) for i in xrange(len(stnc)-1)]: g.add_edge(a, b, b) g.plot(color_by_label=True, edge_style='solid').show(figsize=4) 
       

Para introducir un grafo etiquetado a partir de la matriz de adyacencia, debemos utilizar el parámetro format='weighted_adjacency_matrix'.

M=matrix([[0, 2, 0, 1],[2, 0, 1, 0],[0, 1, 0, 1],[1, 0, 1, 0]]);M g=Graph(M,format='weighted_adjacency_matrix');g.graphplot(edge_labels=True).show(figsize=4) 
       

También es válido con grafos dirigidos.

M=matrix([[0, 0, 0, 4],[2, 0, 0, 4],[0, 3, 0, 1],[0, 3, 0, 0]]);M g=DiGraph(M,format='weighted_adjacency_matrix');g.graphplot(edge_labels=True).show(figsize=4) 
       

Practica.

1. Crea un grafo en el que los vértices sean los números del 1 al 10 y dos vértices serán adyacentes si uno es múltiplo del otro.

2. Crea un digrafo en el que los vértices sean los números del 1 al 10 y tenemos una arista del vértice u al vértice v si u divide a v.

3. En el grafo del ejercicio 1, añade las aristas necesarias hasta que sea completo. Representa el grafo cambiando el color de las aristas añadidas.

 
       

Operaciones con grafos

Grafos "predefinidos"

Sage tiene predefinidos muchos grafos, constructores de grafos y generadores aleatorios de grafos. Escribe graphs. y pulsa <tab> para ver todas las opciones.

Por ejemplo, graphs.CompleteGraph(n) genera el grafo completo de n vértices.

g=graphs.CompleteGraph(5);g.plot().show(figsize=5) 
       

También podemos generar el grafo de un cubo en dimensión 4:

g=graphs.CubeGraph(4);g.plot().show(figsize=5) 
       

Elementos de un grafo

Podemos obtener la lista de vértices mediante el método vertices. Para recorrer los vértices podemos utlizar vertex_iterator o símplemente "recorriendo el grafo".

g.vertices() 
       
for u in g.vertex_iterator(): print u 
       
for u in g: print u 
       

Análogamente, para generar las aristas, tenemos el método edges y para recorrerlas, edge_iterator.

for e in g.edge_iterator(): print e 
       

Para saber si una arista está en el grafo, usamos has_edge.

g.has_edge('1000','0000') 
       
g.has_edge('1000','0100') 
       

Para obtener los vértices adyacentes e iterarlos, utilizamos neighbors y neighbor_iterator, respectivamente.

g.neighbors('1000') 
       
for i in g.neighbor_iterator('1000'): print i 
       

De todos modos, siempre podemos resolver cualquier problema de grafos utilizando listas y la matriz de adyacencia. Además suele ser más sencillo que los métodos anteriores. Para obtener la matriz de adyacencia de un grafo, usamos adjacency_matrix.

M=g.adjacency_matrix();M 
       

Tipos de datos para grafos

Vamos a estudiar dos tipos de datos de Python que son muy útiles a la hora de programar grafos. La documentación completa se puede consultar en:

http://docs.python.org/2/tutorial/datastructures.html

Conjuntos

Un conjunto es similar a una lista pero no permite repeticiones de elementos. Por tanto se suele utilizar precisamente para eliminar repeticiones de listas. Se puede definir mediante llaves o con el constructor Set aplicado a una lista.

s={1,2,3,4,3,2,1};s 
       
Set([1,3,4,2,1,3,4,2,3,3,2,1]) 
       

Para recorrer los elementos, se utiliza la misma sintaxis que con listas.

for i in s: print i 
       

Diccionarios

Un diccionario es un conjunto de pares de elementos separados por :. El elemento de la izquierda se llama clave y el de la derecha valor.

tel = {'jack': 4098, 'sape': 4139} 
       

Para acceder al valor de una clave, se evalúa el diccionario en la clave.

tel['jack'] 
       

Para añadir un nuevo elemento, símplemente se le asigna un valor a la nueva clave.

tel['guido'] = 4127;tel 
       

Y para eliminar una pareja, usamos del.

del tel['sape'] 
       

También podemos construir el diccionario aplicando el constructor dict a una lista de pares, a una lista de asignaciones (sólo válido cuando las claves son texto) o usando el constructor con llaves:

dict([('sape', 4139), ('guido', 4127), ('jack', 4098)]) 
       
dict(sape=4139, guido=4127, jack=4098) 
       
{x: x**2 for x in (2, 4, 6)} 
       

Por último, podemos recorrer los elementos, las claves o los valores usando los métodos iteritems, iterkeys e itervalues, respectivamente.

for n, t in tel.iteritems(): print n, t 
       
for n in tel.iterkeys(): print n, tel[n] 
       
for t in tel.itervalues(): print t 
       

Practica.

1. Crea un diccionario con los pares $n:[k n]$, para $n$ entre $1$ y $20$ y $k$ entre $2$ y $20$  de modo que $n k\leq 20$.

2. Crea un grafo a partir del diccionario anterior. Obtén la matriz de adyacencia de este grafo.

 
       

Dos ejemplos

Vamos a ver dos ejemplos de algoritmos con grafos, sacados de:

http://www.steinertriples.fr/ncohen/tut/Graphs/

Primer ejemplo

What is the maximum size of a set of integers between 1 and 100 such that for any pair (a,b), the difference a-b is not a square ?

n=100 cuadrados=[i*i for i in range(sqrt(n)+1)] # Creamos una lista con los cuadrados perfectos edges=[(i,j) for (i,j) in [(i,j) for i in range(1,n) for j in range(1,n)] if (i!=j and abs(i-j) in cuadrados)] # Generamos los pares i,j g=Graph() # Creamos un grafo vacío g.add_edges(edges) # Añadimos las aristas g.independent_set() # Calculamos un conjunto independiente maximal 
       

Segundo ejemplo

The greedy coloring algorithm can be explained in a few words :

  • Define a set of colors
  • Take each vertex iteratively, and assign to it the smallest color not already taken by one of its neighbors
g = graphs.RandomGNP(20,4/20) # Generamos un grafo aleatorio C = Set(xrange(20)) # Generamos el conjunto de colores color = {} # Creamos un diccionario vacío for u in g: # Para cada vértice en el grafo interdits = Set([color[v] for v in g.neighbors(u) if color.has_key(v)]) # Creamos el conjunto de colores de los vecinos color[u] = min(C-interdits) # Tomamos el mínimo color que no esté usado por un vecino. 
       

El procedimiento anterio calcula el color para cada vértice. Para colorearlos tenemos que hacer algunas modificaciones. En particular, necesitamos un diccionario que para cada color tenga todos los vértices para colorear. Lo hacemos con el siguiente procedimiento.

colores=[(random(),random(),random()) for k in color.itervalues()] gc={colores[k]:[c for c in color.iterkeys() if color[c]==k] for k in color.itervalues()} g.plot(vertex_colors=gc, layout='circular') 
       

Ejercicios.

En los siguientes ejercicios se tratará de codificar funciones sencillas de teoría de grafos, para repasar los conceptos y algoritmos. Sage tiene predefinidas montones de funciones que hacen todas esas operaciones, pero el objetivo es que vosotros aprendáis cómo se trabaja con grafos, por lo que en la resolución deberéis usar únicamente lo que se ha explicado en las prácticas. Las funciones tienen que estar convenientemente explicadas, con un comentario al comienzo de la función como líneas de comentario en cada operación que se considere compleja (en particular en los bucles y llamadas recursivas).

De los siguientes ejercicios elije en el $A$ el apartado que corresponda a tu última cifra del DNI (a la última cifra de la suma de DNI si sois dos), en el $B$ a la penúltima y así sucesivamente.

A. Genera un grafo con las siguientes propiedades (en caso de no existir, razona porqué no es posible un grafo así):

0,9. 3-regular con un conjunto independiente formado por 4 vértices

1,8. 3-regular con un clique formado por 4 vértices

2,7. 4-regular y euleriano

3,6. Euleriano y hamiltoniano

4,5. Euleriano pero no hamiltoniano

5,4. Conexo, 4-regular pero no hamiltoniano

6,3. No Euleriano pero sí hamiltoniano

7,2. No conexo, 2-regular y con el complemento 3-regular

8,1. Conexo, hamiltoniano pero no euleriano

9,0. No euleriano y con secuencia de grados 4 2 2 2 2 2 2.

B. Crea una función que reciba un grafo y devuelva:

0,5. El número de aristas

1,6. La secuencia de grados

2,7. Si contiene o no un clique de 3 vértices

3,8. Si el grafo es regular

4,9. Si el grafo es un árbol

C. Crea varios grafos de prueba, codifica la función descrita en el apartado y pruébala.

0,4,8. Crea una función que reciba dos caminos simples (listas de vértices), con el primero y el último en común y devuelva un ciclo.

1,5,9. Crea una función que reciba una secuencia (lista decreciente de números positivos) y devuelva un grafo con dicha secuencia de grados (en caso de que no exista, devolverá un grafo vacío).

2,6. Crea una función que reciba un grafo y un vértice y devuelva la componente conexa de dicho vértice.

3,7. Crea una función que reciba un grafo y una lista de vértices y calcule en número de componentes conexas del grafo resultante de eliminar dichos vértices. Para calcular el número de componentes conexas utilizará el método connected_components_number.