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())
sage: #El grafo ciclico (dirigido)
sage: dg1 = digraphs.Circuit(15)
sage: show(plot(dg1))
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))
sage: #Una solucion: usar otro "layout"
sage: show(plot(g2, layout='spring'))
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?
<html>...</html>
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))
sage: dg2 = DiGraph({0:[1,3],1:[3,0],2:[1,3],3:[0]})
sage: show(plot(dg2))
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:
sage: print g1.is_connected()
sage: print g2.is_connected()
sage: print g3.is_connected()
True
True
True
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
sage: print g1.is_tree()
sage: print g2.is_tree()
sage: print g3.is_tree()
sage: print g4.is_tree()
False
False
False
False
sage: dg3 = DiGraph({0:[1,3],1:[3],2:[1,3]})
sage: show(plot(dg3))
sage: print dg3.is_directed_acyclic()
True
sage: print g1.is_planar()
sage: print g2.is_planar()
sage: print g3.is_planar()
sage: print g4.is_planar()
True
True
True
True
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
<bound method Graph.is_eulerian of Complete graph: Graph on 4 vertices>
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)
Á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).
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:
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:
¿Es éste el mejor recorrido?
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')
<html>...</html>