.. -*- coding: utf-8 -*- Grafos ====== En esta lección vamos a estudiar las posibilidades que ofrece SAGE para trabajar con **grafos** . Un grafo consiste de un conjunto de **vértices** y otro conjunto de **aristas** que unen algunos de los vértices. En un grafo no dirigido las aristas no tienen dirección, mientras que en los grafos dirigidos debemos distinguir entre la arista que une el vértice v1 con el v2 de la arista que une el vértice v2 con el v1. Introducir Grafos en SAGE ::::::::::::::::::::::::: .. index:: graphs, CompleteGraph, Graph.plot, digraphs Algunos grafos especiales ~~~~~~~~~~~~~~~~~~~~~~~~~ Existen constructores para muchos de los grafos no dirigidos más famosos, dentro del módulo ``graphs`` . Por ejemplo: - Grafo completo: el que tiene todas las aristas que unen cada par de vértices - Grafo cíclico: una circuito simple - Grafo del n\-cubo - ... :: sage: g1 = graphs.CompleteGraph(5) sage: show(g1.plot()) .. image:: b4s2_media/cell_24_sage0.png :align: center :: sage: g2 = graphs.CycleGraph(4) sage: show(plot(g2)) .. image:: b4s2_media/cell_81_sage0.png :align: center :: sage: g3 = graphs.CubeGraph(3) sage: show(plot(g3)) .. image:: b4s2_media/cell_43_sage0.png :align: center El dibujo anterior confunde dos de los vértices. Leemos la documentación de Graph.plot para encontrar la forma de mejorar el dibujo :: sage: g3.plot? ... :: sage: #Una solucion: usar otro "layout" sage: show(plot(g3, layout='spring')) .. image:: b4s2_media/cell_22_sage0.png :align: center Como de costumbre, usando el tabulador accedemos a una lista completa con todos los grafos disponibles. :: sage: graphs. Traceback (most recent call last): ... SyntaxError: invalid syntax También tenemos alguns familias de grafos famosos en la librería ``digraphs`` . :: sage: show(plot(digraphs.Circuit(5))) .. image:: b4s2_media/cell_84_sage0.png :align: center ..index:: Graph, matriz de adyacencia, DiGraph Introducir un grafo mediante la matriz de adyacencia ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ También podemos introducir un grafo usando la *matriz de adyacencia* : una matriz *KxK* (donde *K* es el número de vértices), que tiene un 1 en la posición *i,j* si y sólo si hay una arista entre los vértices *i* y *j* . Para grafos no dirigidos, la matriz debe ser simétrica. *Nota* : En la documentación de ``Graph`` puedes encontrar otras formas de introducir un grafo (por ejemplo, mediante un diccionario asigna a cada vertice la lista de sus vecinos). :: sage: M = matrix([[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]]) sage: show(M) sage: g4 = Graph(M) sage: show(g4, layout='circular') .. MATH:: \left(\begin{array}{rrrr} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right) .. image:: b4s2_media/cell_28_sage0.png :align: center Podemos construir del mismo modo un grafo dirigido, con una matriz no necesariamente simétrica, usando ``DiGraph`` . :: sage: M = matrix(ZZ,[[0,0,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]]) sage: show(M) sage: g4 = DiGraph(M) sage: show(g4, layout='circular') .. MATH:: \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right) .. image:: b4s2_media/cell_86_sage0.png :align: center El método ``adjacency_matrix`` devuelve la matriz de adyacencia de un grafo, independientemente de cómo lo introdujimos. :: sage: g1.adjacency_matrix() [0 1 1 1 1] [1 0 1 1 1] [1 1 0 1 1] [1 1 1 0 1] [1 1 1 1 0] Operaciones con grafos :::::::::::::::::::::: También podemos construir nuevos grafos a partir de otros. - La suma de grafos devuelve la unión de los dos grafos. - El producto de un grafo por un entero repite un grafo. :: sage: g5 = g1 + g2 sage: show(g5,layout='circular') .. image:: b4s2_media/cell_29_sage0.png :align: center :: sage: g6 = g4*3 sage: show(g6,layout='circular') .. image:: b4s2_media/cell_36_sage0.png :align: center .. index:: add_vertex, add_edge, delete_vertex, delete_edge Modificar grafos :::::::::::::::: Podemos añadir y quitar vértices y aristas a grafos existentes usando ``add_vertex`` , ``add_edge`` , ``delete_vertex`` , ``delete_edge`` . :: sage: g7 = 2*g2 sage: show(g7,layout='spring') sage: g7.add_edge(0,4) sage: g7.add_edge(1,5) sage: g7.add_edge(2,6) sage: g7.add_edge(3,7) sage: show(g7,layout='spring') .. image:: b4s2_media/cell_37_sage0.png :align: center .. image:: b4s2_media/cell_37_sage1.png :align: center Podemos partir de un grafo vacío y añadir los vértices y aristas necesarios: :: sage: g8 = Graph() sage: g8.add_vertex(0) sage: g8.add_vertex(1) sage: g8.add_edge(0,1) sage: plot(g8) .. image:: b4s2_media/cell_64_sage0.png :align: center Ejercicio ~~~~~~~~~ Modifica el grafo g6 añadiendo un vértice y uniendo todos los otros vértices al nuevo vértice. .. index:: is_connected, is_planar, is_eulerian, is_tree Propiedades de los grafos ::::::::::::::::::::::::: Podemos verificar un buen número de propiedades de un grafo usando los métodos adecuados. Por ejemplo: - ``is_connected`` : comprueba si el grafo es **conexo** - ``is_planar`` : comprueba si el grafo es **plano** . Un grafo es plano si se pueden dibujar los vértices y las aristas en un plano sin que las aristas se intersequen. - ``is_eulerian`` : comprueba si el grafo tiene un **circuito euleriano** . Un circuito en un grafo es una sucesión de aristas adyacentes que comienza y termina en el mismo vértice. Un circuito euleriano es un circuito que pasa exactamente una vez por cada arista. - ``is_tree`` : comprueba si el grafo es un **árbol** . Un árbol es un grafo conexo que no tiene *ningún circuito cerrado* . :: sage: print g1.is_connected() sage: print g1.is_planar() sage: print g1.is_eulerian() sage: print g1.is_tree() sage: show(g1.plot()) True False True False .. image:: b4s2_media/cell_32_sage0.png :align: center Criterio de Euler ~~~~~~~~~~~~~~~~~ Según el criterio de Euler, un grafo tiene un circuito euleriano si y sólo todos los vértices tienen grado par. Ejercicio --------- Comprueba el criterio de Euler para decidir si un grafo es euleriano. :: sage: g5.degree() [4, 4, 4, 4, 4, 2, 2, 2, 2] .. index:: is_isomorphic Isomorfismo de grafos ::::::::::::::::::::: Dos grafos son isomorfos si y sólo si existe una biyección del conjunto de vértices del primero en el conjunto de vértices del segundo tal que dos vértices están unidos en el primer grafo si y sólo si los vértices correspondientes están unidos en el segundo. En dos grafos isomorfos, los vértices pueden tener nombres distintos y estar colocados en distintas posiciones, pero todas las relaciones de incidencia y todas las propiedades de grafos como conexión, planaridad etćetera son idénticas. :: sage: print g7.is_isomorphic(g3) sage: print g7 == g3 sage: print g3.vertices() sage: print g7.vertices() True False ['000', '001', '010', '011', '100', '101', '110', '111'] [0, 1, 2, 3, 4, 5, 6, 7] **Pregunta**: ¿cuál de los grafos que definimos antes es isomorfo al siguiente grafo? :: sage: M = matrix(ZZ,[[0,1,1,0],[1,0,0,1],[1,0,0,1],[0,1,1,0]]) sage: show(M) sage: g9=Graph(M) sage: show(g9,layout='circular') .. MATH:: \left(\begin{array}{rrrr} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{array}\right) .. image:: b4s2_media/cell_78_sage0.png :align: center La función ``graphs`` genera un grafo de cada clase de isomorfismo de grafos con un cierto número de vértices. :: sage: for g in graphs(4): ... if g.is_connected(): ... print g.adjacency_matrix() ... print [0 1 1 1] [1 0 0 0] [1 0 0 0] [1 0 0 0] [0 1 1 0] [1 0 0 0] [1 0 0 1] [0 0 1 0] [0 1 1 0] [1 0 1 0] [1 1 0 1] [0 0 1 0] [0 1 1 0] [1 0 0 1] [1 0 0 1] [0 1 1 0] [0 1 1 0] [1 0 1 1] [1 1 0 1] [0 1 1 0] [0 1 1 1] [1 0 1 1] [1 1 0 1] [1 1 1 0] :: sage: L = list(graphs(4)) El siguiente método es una forma de dibujar un montón de grafos en poco espacio. :: sage: graphs_list.show_graphs(L) .. image:: b4s2_media/cell_49_sage0.png :align: center Podemos generar todos los grafos con un cierto número de vértices y contar el número de ellos que verifican una cierta propiedad. :: sage: L = [g for g in graphs(4) if g.is_connected()] sage: print len(L) sage: graphs_list.show_graphs(L) 6 .. image:: b4s2_media/cell_53_sage0.png :align: center