.. -*- coding: utf-8 -*- Modelización con grafos ======================= Definición de grafo ------------------- Un **grafo** consta de un conjunto de **vértices** (también llamados **nodos**) y otro de **aristas**. Una arista une dos vértices, representando de este modo una relación entre esos dos vértices. Si la relación es simétrica, hablaremos de **grafos no dirigidos** (o **grafos** a secas), y no será necesario 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. Sin embargo, si la relación es direccional, hablaremos de **grafos dirigidos** . Gráficamente, se suele representar con un punto del plano por cada vértice, y un arco de v1 a v2 si ambos vértices están unidos por una arista (en vez un arco usaremos una flecha en grafos dirigidos). :: sage: #Ejemplo de grafo: el grafo completo sage: g1 = graphs.CompleteGraph(4) sage: show(g1.plot()) .. image:: grafos_media/cell_8_sage0.png :align: center .. end of output :: sage: #El grafo ciclico (dirigido) sage: dg1 = digraphs.Circuit(15) sage: show(plot(dg1)) .. image:: grafos_media/cell_7_sage0.png :align: center .. end of output :: sage: #El grafo que forman las aristas del cubo sage: #si usamos un plot sin argumentos, el dibujo confunde dos vertices sage: g2 = graphs.CubeGraph(3) sage: show(plot(g2)) .. image:: grafos_media/cell_1_sage0.png :align: center .. end of output :: sage: #Una solucion: usar otro "layout" sage: show(plot(g2, layout='spring')) .. image:: grafos_media/cell_12_sage0.png :align: center .. end of output :: sage: #Lee la documentación de Graph.plot para encontrar otras formas sage: #de dibujar grafos (una interrogacion al final de un metodo o sage: #funcion muestra la ayuda) sage: g2.plot? ... .. end of output :: sage: #Tambien podemos introducir un grafo usando un diccionario sage: #que a cada vertice le asigna la lista de sus vecinos sage: #(los vertices a los que esta unido). sage: g3 = Graph({0:[1,3],1:[3],2:[1,3],3:[0]}) sage: show(plot(g3)) .. image:: grafos_media/cell_14_sage0.png :align: center .. end of output :: sage: dg2 = DiGraph({0:[1,3],1:[3,0],2:[1,3],3:[0]}) sage: show(plot(dg2)) .. image:: grafos_media/cell_13_sage0.png :align: center .. end of output Los grafos pueden representar información discreta de lo más diverso, como veremos en los ejemplos, pero no es raro que al expresar una pregunta de interés por medio de grafos nos encontremos con que la pregunta es típica en teoría de grafos, y que existe una solución o un algoritmo *canónicos* para este problema. Al haber introducido sólamente información discreta, las preguntas que podemos hacer al nivel de la teoría de grafos son también de naturaleza discreta. Por ejemplo: - Si voy saltando de un vértice a otro que esté unido por una arista, ¿es posible alcanzar cualquier vértice partiendo de otro vértice arbitrario? Un grafo con esta propiedad se denomina **conexo** . - ¿Existe un **camino cerrado** de aristas consecutivas (el extremo de una es el principio de la siguiente)? Un tal camino se denomina **ciclo** . Un grafo dirigido sin ciclos se denomina **acíclico** , o tambien DAG (directed acyclic graph). Un grafo no dirigido sin ciclos se denomina **árbol** (si es conexo). - ¿Es posible disponer los vértices y las aristas en el plano de modo que las aristas no se intersequen? Si lo es, el grafo se denomina **plano** . :: sage: print g1.is_connected() sage: print g2.is_connected() sage: print g3.is_connected() True True True .. end of output :: sage: #La suma de dos grafos es su unión disjunta sage: g4 = g1 + g2 sage: show(plot(g4)) sage: print g4.is_connected() False .. image:: grafos_media/cell_16_sage0.png :align: center .. end of output :: sage: print g1.is_tree() sage: print g2.is_tree() sage: print g3.is_tree() sage: print g4.is_tree() False False False False .. end of output :: sage: dg3 = DiGraph({0:[1,3],1:[3],2:[1,3]}) sage: show(plot(dg3)) sage: print dg3.is_directed_acyclic() True .. image:: grafos_media/cell_21_sage0.png :align: center .. end of output :: sage: print g1.is_planar() sage: print g2.is_planar() sage: print g3.is_planar() sage: print g4.is_planar() True True True True .. end of output :: sage: #Situa el cursor al final de la ultima linea y pulsa [Tab] sage: #para que Sage sugiera las posibles formas de completar el comando sage: #Los "metodos" de un grafo que comienzan por "is_" comprueban sage: #si el grafo tiene determinadas propiedades. sage: g1.is_eulerian .. end of output Información extra ^^^^^^^^^^^^^^^^^ Si nos resulta conveniente, podemos añadir información extra a cada vértice, o a cada arista. Por ejemplo, es típico añadir números reales que midan la *intensidad* o la *capacidad* del enlace entre dos vértices. En estos casos, nos encontramos con que podemos hacer otro tipo de preguntas, que ya no son necesariamente discretas. :: sage: #Para introducir un grafo con etiquetas, llamamos a DiGraph sage: #con un diccionario que a cada nodo le asigna otro diccionario sage: #que tiene a sus vecinos como claves y las etiquetas como valores sage: g5 = Graph({'Madrid':{'Barcelona':621}, ... 'Sevilla':{'Madrid': 538,'Barcelona': 1046}}) sage: g5.plot(edge_labels=True, vertex_size=300, figsize=8) .. image:: grafos_media/cell_31_sage0.png :align: center .. end of output Ejemplos -------- Árbol genealógico de un caballo de carreras (un tal Lion Share). En este tipos de grafos, podríamos intentar por ejemplo medir el grado de endogamia (lo haremos en los ejercicios). .. image:: grafos_media/http://www.graphviz.org/Gallery/directed/lion_share.png :align: center Recogida de basuras ^^^^^^^^^^^^^^^^^^^ El grafo de debajo muestra el entramado de calles de un barrio. El camión de basuras debe pasar (al menos) una vez por cada calle para hacer la recogida, y quiere encontrar el recorrido más corto, saliendo y llegando al vértice de arriba a la izquierda: .. image:: grafos_media/ejemplo1.png :align: center La primera idea es buscar un camino en el grafo que pase por cada calle exactamente una vez. En este grafo, resulta ser imposible, porque cada vez que entramos en un vértice y luego salimos, consumimos dos aristas, y hay 4 vértices a los que llegan 3 aristas (decimos que tienen **grado** 3). Euler mostró que, de hecho, un grafo admite un camino que pasa exactamente una vez por cada arista si y sólo si los grados de todos los vértices son pares. Es por ello que esos caminos se denominan eulerianos, y a los grafos que admiten tales caminos se les dice grafos eulerianos. Por lo tanto, es necesario pasar dos veces por algunas aristas, pero ¿por cuáles?. Si duplicamos suficientes aristas, obtenemos un grafo tal que todos los grados son pares y, por el teorema de Euler, admite un camino euleriano. Por ejemplo, recorriendo una distancia extra de 18\+13\+22, conseguimos un posible recorrido para la recogida de basuras: .. image:: grafos_media/ejemplo2.png :align: center ¿Es éste el mejor recorrido? Autómata finito ^^^^^^^^^^^^^^^ En este ejemplo mostramos una "maquina de estados" para definir números en notación científica (simplificado). Si recorres el grafo comenzando en "base_line" y vas siguiendo las flechas, escribiendo al pasar por cada vertice o cada arista su etiqueta, obtienes codigo que representa un número en notación científica. :: sage: function_def = DiGraph({'comienzo':{'antes_de_la_coma':'+|-'}, ... 'antes_de_la_coma': ... {'despues_de_la_coma':' ,', ... 'antes_de_la_coma':'digito'}, ... 'despues_de_la_coma': ... {'despues_de_la_coma':'digito', ... 'exponente':'10^'}, ... 'exponente': ... {'exponente':'digito', ... 'fin':''} ... }) sage: #en esta hoja hemos incluido un fichero graphviz.sage que sage: #permite dibujar grafos dirigidos de otra forma (solo si el sage: #paquete graphviz esta instalado) sage: attach(DATA + 'graphviz.sage') sage: graphviz(function_def, 'dot') ... .. end of output