Sesion de Pr´acticas 3 - um.es

Algebra y Matematica Discreta Sesion de Practicas 3

Algebra y Matematica DiscretaSesion de Practicas 3

(c) 2013 Leandro Marın, Francisco J. Vera, Gema M. Dıaz

30 Sep 2013 - 6 Oct 2013


Grafos

Grafos en Sage

Definicion

Un grafo es simplemente un conjunto de vertices y unconjunto de aristas que unen pares de vertices.

Para introducir un grafo en sage lo que tenemos que decir escuantos vertices tenemos y cuales son las conexiones entreellos.

El programa nos da varias opciones.


Grafos

Grafos en Sage

Comandos para vertices y aristas

Los comandos add_vertex y delete_vertex nos ponen yquitan vertices en un grafo.

Los comandos add_edge y delete_edge nos ponen y quitanaristas en un grafo.

Una forma de definir un grafo, es ir anadiendo sucesivamentecada uno de los vertices y aristas que necesitamos.


Grafos

Grafos en Sage

Escribamos el siguiente codigo

G = Graph ()

G.add_vertex(0)

G.add_vertex(1)

G.add_vertex(2)

G.add_vertex(3)

G.add_edge(0,1)

G.add_edge(1,2)

G.add_edge(2,3)

G.add_edge(3,0)

plot(G)


Grafos

Grafos en Sage

Obtenemos lo siguiente:

0

1

2

3


Grafos

Grafos en Sage

Anadir una Arista

Vamos a anadir una arista entre los vertices 1 y 3

Para eso no tenemos mas que pone G.add_edge(1,3)

Y para eliminar la arista entre los vertices 0 y 1 ponemosG.delete_edge(0,1)

Si volvemos a dibujar el grafo con G.plot()


Grafos

Grafos en Sage


0

1 2

3


Grafos

Grafos en Sage

Disposicion de los Vertices

sage elige la ordenacion de los vertices que considera ajustadaal grafo que dibujamos.

Podemos indicar diferentes formas de poner los vertices asage poniendo un parametro llamado layout

Podemos usar por ejemplo las disposicionesG.plot(layout=’circular’) oG.plot(layout=’spring’)


Grafos

Grafos en Sage

G.plot(layout=’circular’)


0

1

2

3


Grafos

Grafos en Sage

Matriz de Adyacencia (I)

Dado un grafo G , la matriz de adyacencia de G es una matrizcuadrada que tiene tantas filas y columnas como verticestenga nuestro grafo, y dados dos vertices i y j , tendra el valor1 en la posicion (i , j) de la matriz si hay una arista que unedichos vertices, y 0 si no existe dicha arista.

Podemos calcular la matriz de adyacencia de un grafo con elcomando

G.adjacency_matrix ()

En nuestro caso obtenemos

0 0 0 10 0 1 10 1 0 11 1 1 0


Grafos

Grafos en Sage

Matriz de Adyacencia (II)

Tambien podemos definir un grafo a partir de su matriz deadyacencia.

Para ello simplemente ponemos

M = matrix (ZZ ,3,[0,1,1,1,0,1,1,1,0])

G = Graph(M)

Nos introducira la matriz en G . Podemos mostrarlo enpantalla.


Grafos

Grafos en Sage


0

1 2


Grafos

Tipos de Grafos

Grafos Dirigidos

Un grafo dirigido es un grafo en el cual las aristas tienen unsentido de recorrido.

Eso significa que podemos tener una arista entre el vertice i yel vertice j mientras que no lo tenemos en el sentido contrario,entre j e i .

Para construir grafos dirigidos utilizamos DiGraph en lugar deGraph.


Grafos

Tipos de Grafos


G = DiGraph ()

G.add_vertex(0)

G.add_vertex(1)

G.add_vertex(2)

G.add_vertex(3)

G.add_edge(0,1)

G.add_edge(1,2)

G.add_edge(2,3)

G.add_edge(3,0)

plot(G)


Grafos

Tipos de Grafos


0

1

2

3


Grafos

Tipos de Grafos

Matriz de Adyacencia (III)

Si el grafo es dirigido la matriz de adyacencia puede no sersimetrica, puesto que podemos tener una conexion entre i y j ,pero no entre j e i . Eso hace que la posicion (i , j) de lamatriz valga 1 mientras que la posicion (j , i) vale 0.

En este caso podemos tambien calcular la matriz deadyacencia de un grafo con el comando

G.adjacency_matrix ()

Que con el grafo anterior nos da

0 1 0 00 0 1 00 0 0 11 0 0 0


Grafos

Tipos de Grafos

Pseudografos

Un pseudografo es aquel en el que permitimos uniones de unvertice consigo mismo.Un ejemplo podrıan ser los elementos {0, 1, 2, 3, 4, 5} junto con lasrelaciones de divisibilidad entre ellos:

M = matrix(ZZ ,6,[0]*36)

for i in range(6):

for j in range(6):

if ZZ(i).divides(ZZ(j)):

M[i,j] = 1

G = DiGraph(M)

Podemos representar el grafo de forma circular.


Grafos

Tipos de Grafos


0

1

2

3

4

5


Grafos

Tipos de Grafos

Vertices con Nombres

Podemos definir un grafo dando nombres a los vertices e indicandocuales son los vertices que los conectan.

G = Graph({"a":{"b","h"},"b":{"a","c","h"},

"c":{"b","d","f","i"},"d":{"c","e","f"},

"e":{"d","f"},"f":{"c","d","e","g"},

"g":{"f","h","i"},"h":{"a","b","i"}})

Podemos representarlo con G.plot()


Grafos

Tipos de Grafos


a

b

c

d

e f

g

h

i


Grafos

Caminos y Conexion

Definicion de Camino

Dado un grafo G y dos vertices u y v . Un camino entre u y v

es una lista de vertices [w0,w1, · · · ,wk ] tales que w0 = u,wk = v y para todo i = 0, ..., k − 1 el par {wi ,wi+1} es unaarista del grafo.

La longitud del camino es el numero de aristas que lo forman.


Grafos

Caminos y Conexion

Caminos y Matriz de Adyacencia

La matriz de adyacencia de un grafo nos indica el numero decaminos de longitud 1 que existen entre cada par de vertices.

Eso tambien es cierto para las potencias de la matriz deadyacencia. Es decir, si G es un grafo definido con matriz M,la matriz Mk tiene en su entrada (i , j) el numero de caminosde longitud k que existen entre el vertice i y el vertice j .

El numero de caminos de longitud menor que k que unen i

con j se calcula con la suma de las matrices:

M0 +M1 +M2 + · · ·+Mk−1


Grafos

Caminos y Conexion

Ejemplo

Por ejemplo, el grafo:

0

1

2

3

4

5

Tiene como matriz de adyacencia:

M =

0 1 0 0 1 01 0 1 0 1 10 1 0 1 0 10 0 1 0 0 11 1 0 0 0 00 1 1 1 0 0


Grafos

Caminos y Conexion

Ejemplo

0

1

2

3

4

5

Si elevamos la matriz al cuadrado,podemos ver los caminos de longitud 2entre todos los pares de vertices.

M2 =

2 1 1 0 1 11 4 1 2 1 11 1 3 1 1 20 2 1 2 0 11 1 1 0 2 11 1 2 1 1 3

Si nos fijamos por ejemplo en la entradaM2

1,3 = 2 nos indica que hay doscaminos de longitud 2 entre los vertices1 y 3.


Grafos

Caminos y Conexion

Ejemplo

0

1

2

3

4

5

Si elevamos la matriz al cubo, podemosver los caminos de longitud 2 entretodos los pares de vertices.

M3 =

2 5 2 2 3 25 4 7 2 5 72 7 4 5 2 52 2 5 2 2 53 5 2 2 2 22 7 5 5 2 4

Si nos fijamos por ejemplo en la entradaM3

0,3 = 2 nos indica que hay doscaminos de longitud 2 entre los vertices0 y 3.


Grafos

Caminos y Conexion

Conexion

Un grafo se dice conexo si todo par de vertices esta conectadopor un camino.

Se puede saber si un grafo es conexo con el comandoG.is_connected()

Si un grafo no es conexo, se puede dividir en trozos. Cadauno de ellos recibe el nombre de componente conexa.


Grafos

Caminos y Conexion

Conexion y Matriz de Adyacencia

Si en un grafo hay un camino entre dos vertices, podemosasegurar que tiene que haber al menos un camino que norepita vertices.

Por lo tanto, en un grafo de k vertices, dos verticescualesquiera tiene conexion si y solo si existe un camino delongitud menor que k .

Si M es la matriz de adyacencia de un grafo G con k vertices,se puede saber si G es conexo si para todo i y j , la matriz

M0 +M1 +M2 + · · ·+Mk−1

tiene una entrada no nula.


Grafos

Caminos y Conexion

Ejemplo

0

1

2

3

4

5

M0+M

1+...+M5 =

29 49 34 24 29 34

49 77 73 44 49 73

34 73 63 49 34 63

24 44 49 33 24 49

29 49 34 24 29 34

34 73 63 49 34 63

lo que nos indica que este grafo esclaramente conexo. Podemos hacer esecalculo con:

sum([M ** j for j in range(6)])


Grafos

Caminos y Conexion

Caminos en sage

Dados dos vertices i y j de un grafo finito, podemos calculartodos los caminos entre i y j que no repitan vertices.

El comando:

G.all_paths(0,3)

nos dara los caminos entre el vertice 0 y el vertice 3.

En el grafo anterior nos dara:

[[0, 1, 2, 3], [0, 1, 2, 5, 3], [0, 1, 5, 2, 3],

[0, 1, 5, 3], [0, 4, 1, 2, 3], [0, 4, 1, 2, 5, 3],

[0, 4, 1, 5, 2, 3], [0, 4, 1, 5, 3]]

Debemos notar que el numero de caminos no coincide con laspotencias de la matriz porque aquı los caminos nos los da sinrepeticion de vertices (si no podrıamos tener infinitos).


Grafos

Arboles

Definicion

Un arbol es un tipo de grafo conexo que cumple que entre dosvertices distintos hay un unico camino.

Un grafo formado por varios arboles disconexos se llama unbosque.

Se puede saber si un grafo es un arbol poniendo G.is_tree()


Grafos

Arboles


G = Graph ()

G.add_vertex(0)

G.add_vertex(1)

G.add_vertex(2)

G.add_vertex(3)

G.add_vertex(4)

G.add_edge(0,1)

G.add_edge(0,2)

G.add_edge(2,3)

G.add_edge(2,4)

plot(G)


Grafos

Arboles


0

1

2

3

4


Grafos

Arboles

Para los arboles tenemos un layout especial. Podemos ponerG.plot(layout=’tree’)

0

12

34


Grafos

Arboles

Arboles con Raız

Si el arbol esta construido a partir de uno de sus vertices, esevertice se llama raız.

La distancia de un vertice a la raız es el numero de aristas quetenemos que recorrer para llegar a ella. Ası hablaremos de losvertices que estan en el nivel 1,2,...

Para indicar que nos represente el grafo con una raız concreta,lo indicamos con el comando:

G.plot(layout=’tree’,tree_root=0)


Grafos

Arboles

Ası G.plot(layout=’tree’,tree_root=0) nos da

0

12

34


Grafos

Arboles

Y si ponemos como raız al vertice 2, tenemosG.plot(layout=’tree’,tree_root=2) nos da

0

1

2

34


Grafos

Arboles

Grafos con Pesos

En los grafos, podemos establecer el coste de las aristasindicandolo con un valor numerico sobre ellas. Es lo que sedenomina un grafo con pesos.

G = Graph({"a":{"b":4,"h":8},"b":{"c":1,"h":2},

"c":{"d":6,"f":1,"i":2},"d":{"e":4,"f":10},

"e":{"f":5},"f":{"g":1},"g":{"h":2,"i":6},

"h":{"i":14}})

Podemos representarlo con G.plot(edge_labels=True)


Grafos

Arboles


1

1

6

5

2

1

10 24 14

2

8

4

6

a

b

cd

e

f

g

h

i


Grafos

Arboles

Arboles Generadores

Dado un grafo conexo, nos puede interesar encontrar un arbolcontenido dentro del grafo que nos mantenga la conexion,pero que al ser arbol, tenga el mınimo numero de aristas.

Un arbol de este tipo se llama arbol generador del grafo.

Si el grafo tiene pesos en sus aristas, nos puede interesarencontrar el arbol generador de peso mınimo.

sage nos lo puede calcular directamente con el algoritmoKruskal.


Grafos

Arboles

Kruskal

Introcuzcamos el grafo con pesos y calculemos el arbol generadorminimal

from sage.graphs.spanning_tree import kruskal

G = Graph({"a":{"b":4,"h":8},"b":{"c":1,"h":2},

"c":{"d":6,"f":1,"i":2},"d":{"e":4,"f":10},

"e":{"f":5},"f":{"g":1},"g":{"h":2,"i":6},

"h":{"i":14}})

G.weighted(True)

E = kruskal(G, check=True)


Grafos

Arboles

Kruskal II

Para que se imprima la lista de aristas que tenemos que construir ysus costes (lo que nos devuelve la funcion kruskal), tenemos quedecir print E y obtenemos:

[(’b’, ’c’, 1),

(’c’, ’f’, 1),

(’f’, ’g’, 1),

(’b’, ’h’, 2),

(’c’, ’i’, 2),

(’a’, ’b’, 4),

(’d’, ’e’, 4),

(’e’, ’f’, 5)]

Si por ejemplo queremos calcular el peso total del arbol resultantepodemos hacerlo con:

sum([u[2] for u in E])

Documents

Sesion de Pr´acticas 3 - um.es