GIIT_AMA_18_Grafos_Tutorial 1

146 days ago by etlopez18

Teoría de Grafos

Definiendo grafos

Para generar grafos de modo rápido (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() 
       

Si marcas la casilla "live", entonces las aristas funcionan como gomas elásticas, con una longitud marcada por "length" y una velocidad de contracción determinada por "strength".

Otra manera de generar grafos es mediante el objeto graphs, que contiene muchos constructores de grafos. Escribe graphs. y pulsa el tabulador para ver las opciones.

# Grafo aleatorio de 6 vértices y 12 aristas g=graphs.RandomGNM(6,12) g.plot() 
       

Lista de adyacencia

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

g=Graph({}) # Comenzamos por un grafo vacío 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): # Función que recibe una lista y una función f de dos variables definida sobre los pares de elementos de lista # Devuelve el grafo de vértices los elementos de la lista y arista los pares de vértices que anulan f g=Graph({}) # Generamos un grafo vacío for u in lista: # Recorremos la lista g.add_vertex(u) # Añadimos sus elementos como vértices for v in lista: # Recorremos los pares de elmentos de lista if f(u,v)==0: # Si f se anula en un par, g.add_edge((u,v)) # añadimos ese par como arista return g # Devolvemos el grafo generado 
       
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 
       
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]
g=Graph(M) g.show() 
       

Y podemos recuperar la matriz de adyacencia a partir del grafo son el método adjacency_matrix.

g.adjacency_matrix() 
       
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]

Practica

1. Crea un grafo $3$-regular de 6 vértices.

2. Genera un grafo aleatorio con 20 vértices y 40 aristas.

3. Genera un grafo cuyos vértices sean los números naturales del 1 al 20 y dos vértices sean adyacentes si los números son congruentes módulo 4.

4. Crea una función que reciba una lista de números y genere el grafo cuyos vértices son los números de la lista y dos vértices serán adyacentes si la diferencia de los números es 3 o superior.

 
       

Accediendo a los elementos del grafo

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() 
       
[0, 1, 2, 3]
[0, 1, 2, 3]
for u in g.vertex_iterator(): print u 
       
0
1
2
3
0
1
2
3
for u in g: print u 
       
0
1
2
3
0
1
2
3

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

for e in g.edge_iterator(): print e 
       
(0, 1, None)
(0, 3, None)
(1, 2, None)
(2, 3, None)
(0, 1, None)
(0, 3, None)
(1, 2, None)
(2, 3, None)

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

g.has_edge(1,0) 
       
True
True
g.has_edge(0,2) 
       
False
False

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

g.neighbors(1) 
       
[0, 2]
[0, 2]
for i in g.neighbor_iterator(1): print i 
       
0
2
0
2

Por último, para eliminar vértices o aristas utilizamos delete_vertex o delete_edge, respectivamente.

g.delete_vertex(0) g 
       

Practica

1. Crea una función que reciba un grafo y una lista de vértices y devuelva la lista de los vértices adyacentes a cualquier vértice de la lista.

2. Modifica la función anterior para que los vértices en la lista devuelta no estén repetidos. Un modo de hacer esto es convertir la lista en un conjunto con la función set y después volver a convertirla en lista con list (consulta la documentación si tienes dudas de cómo se usan).

3. Crea una función que reciba dos listas y devuelva la lista obtenida al borrar en la primera lista los elementos de la segunda.

4. Vamos a crear una función que calcule la componente conexa de un vértice. La función recibira un grafo y un vértice v y seguirá el siguiente algoritmo:

    a) Inicializará una lista L con el vértice v

    b) Calculará la lista de vértices adyacentes a alguno de L pero que no esté en L

    c) Mientras la lista de vértices adyacentes del apartado anterior no sea vacía, repetirá a) y b).

 
       

Generadores de grafos

Sage nos permite generar los grafos de modo exhaustivo, por ejemplo, para comprobar conjeturas u obtener ejemplos. Para ello tenemos la función graphs que recibe el número de vértices y devuelve la lista de grafos (salvo isomorfismos) con ese número de vértices.

# Todos los grafos con tres vértices (salvo isomorfismos) L=[] for G in graphs(3): L.append(G) graphs_list.show_graphs(L) 
       

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.

# Contamos los grafos con 2, 3, 4, ... 7 vértices for i in [2..7]: print len([g for g in graphs(i)]) 
       

También se puede restringir la lista a los grafos con un determinado número de aristas, usando la opción size.

# Todos los grafos con 5 vértices y 7 aristas L=[] for g in graphs(5, size=7): L.append(g) graphs_list.show_graphs(L) 
       

Practica

1. Crea una función que reciba un grafo y devuelva su secuencia de grados.

2. Genera todos los grafos 4 regulares de 7 vértices.

3. Genera todos los grafos regulares de 7 vértices. Trata de optimizar el código para que tarde poco tiempo.