GIIT_AMA_1415_Tema_2_Grafos_Eulerianos_Hamiltonianos

1119 days ago by trinidad1415

Teoría de Grafos

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 volver a convertirlo en lista se utiliza list

list(s) 
       

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

for i in s: print i 
       

Para añadir un elemento utilizamos el método add

s.add(13) 
       

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 
       

Por ejemplo, una función que reciba un diccionario y nos diga si existe un elemento tal que su clave es igual a su valor:

def clave_valor(diccionario): for n, t in diccionario.iteritems(): if n==t: return True return False 
       

La probamos:

clave_valor({x: x**2 for x in (2, 4, 6)}) 
       
clave_valor({x: x**2 for x in (-1, 0, 1, 2, 4, 6)}) 
       

Practica.

1.Crea un conjunto S con los elementos 1,3,2,1,4,3,2,1,5,6,7,8,9,20,34,12.

2. Crea una lista con todas las parejas de números de S (con [ (i,j) for i in S for j in S if i!=j] creamos todas las parejas ordenadas de números).

3. 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$.


 
       

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() 
       

Vamos a crear una función que reciba una lista y una función de dos variables y devuelva el grafo con los vértices indicados por la lista y las aristas {u,v} tales que f(u,v)=0.

def grafo_condicion(lista,f): g=Graph({}) for u in lista: g.add_vertex(u) for v in lista: if f(u,v)==0: g.add_edge((u,v)) return g 
       
def f(x,y): return (x+y)%3 # x+y múltiplo de 3 g=grafo_condicion([1..10],f) g.show() 
       

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() 
       

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) 
       
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).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') 
       

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') 
       

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.plot(edge_labels=True) 
       

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.plot(edge_labels=True,color_by_label=True) 
       

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 (pista: usa el diccionario de los ejercicios anteriores o usar la función grafo_condicion).

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 
       

Vamos a ilustrar las instrucciones anteriores obteniendo la componente conexa de un vértice. Para ello:

1. Guardamos una lista de los vértices de la componente conexa ya explorados (ccdefinitiva), una de los vértices de la componente conexa por explorar (cc) y una lista con el resto de los vértices. Al inicio, la lista de los explorados es vacía, la de vértices a explorar sólo tiene el vértice al cual buscamos la componente conexa y la del resto contiene a todos menos a este.

2. Mientras modifiquemos alguna de las listas hacemos lo siguiente:

3. Guardamos los vértices por explorar en la lista de explorados. Hacemos una copia de la lista de vértices por explorar y borramos la lista. Para cada vértice por explorar, miramos sus vecinos y si alguno está en los vértices restantes, lo añadimos a la lista de vértices por explorar y marcamos que hemos hecho un cambio.

def componente_conexa(g,w): # Recibe un grafo g y un vértice w y devuelve la componente conexa de w cc_definitiva=set([]) # Inicializamos los conjuntos (¿podrían ser listas?) según el algoritmo anterior cc={w} resto=g.vertices() resto.remove(w) contador=1 # Hemos modificado las listas, así que ponemos contador a 1 while contador>0: # Mientras se hayan modificado los conjuntos contador=0 # Marcamos que en este punto no se ha modificado ninguna cc_definitiva=cc_definitiva.union(cc) # Añadimos los vértices de cc a cc_definitiva cc_explorando=copy(cc) # Hacemos una copia de cc y la borramos cc.clear() for u in cc_explorando: # Para cada uno de los vértices que nos faltan por explorar for v in g.neighbor_iterator(u): # Miramos los vecinos if v in resto: # Si no están entre los que habíamos encontrado en la componente conexa cc.add(v) # Los añadimos a la componente conexa resto.remove(v) # Los eliminamos del resto contador=contador+1 # Marcamos que hemos modificado los conjuntos return cc_definitiva # Devolvemos la componente conexa 
       

Ahora lo probamos con un grafo aleatorio.

g=graphs.RandomGNP(10,0.15); g.show() 
       
componente_conexa(g,9) 
       

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 
       

Practica

1. Crea una función que reciba un grafo y devuelva el número de vértices de grado cero.

 
       

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')