Comenzamos con la teoría de grafos. Para adentrarnos en este tema hablamos de dos ejemplos que nos ilustran perfectamente nuestro contenido:
- El problema de los puentes de Königsberg
- El problema matemático que nació en un campo de trabajo de la Segunda Guerra Mundial
Hoy hemos trabajado las diferentes definiciones que utilizaremos: grafos, digrafos y multigrafos y otras más, siguiendo la bibliografía recomendada. Además hemos visto algunas de sus propiedades.
Bibliografía recomendada
- Capítulo 2 de Números y Grafos, Juan de Burgos, ingebook
- Temas 7 y 9 de Matemática Discreta, Félix García, Edt. Thomson
También os recomiendo el visionado de este vídeo:
Comenzemos con la definición:
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, \(G=(V,E)\), que permiten representar relaciones binarias entre elementos de un conjunto.
Nosotros trabajaremos con grafos donde \(0<|V|\) y finito; sin embargo, el cardinal de \(E\) puede ser cero. Si \(V=\{v_1,\ldots,v_2\}\) todo elemento de \(e\in E\) es un par de elementos de \(V\); es decir \(e=\{v_i,v_j\}\) para \(v_i,v_j\in V\). Al elemento \(\{v_i,v_j\}\in \wp(V)\) se le denomina par no ordenado; así \(E\subseteq \{x\in {\wp}(V):|x|=2\}\) es un conjunto de pares.
Generalmente tratamos como grafo al conjunto anterior, pero si queremos ser precisos deberíamos decir grafo no dirigido.
Se llama orden del grafo \({\displaystyle G}\) a su número de vértices, \({\displaystyle |V|}\).
El grado de un vértice en un grafo es el número de aristas incidentes a él. En un grafo dirigido, se puede distinguir entre grado de salida («outdegree», número de arcos que salen del vértice) y grado de entrada («indegree», número de arcos que llegan al vértice); un vértice fuente es un vértice con grado de entrada cero, mientras que un sumidero es un vértice con grado de salida cero.
Llamamos grado de un grafo a la suma de los grados de todos sus vértices.
Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.
Proposición: Dado una grafo \(G:(V,E)\) \[\mathbf{gr}(G)=2|E|\]
Dos o más aristas son paralelas si relacionan el mismo par de vértices.
Como hemos dicho es habitual nombrar como grafo a un grafo no dirigido, sin embargo, si explicitamos cuando es un grafo dirigido o digrafo. En este caso \({\displaystyle E\subseteq \{(a,b)\in V\times V:a\neq b\}\,}\) es un conjunto de pares ordenados de elementos de \({\displaystyle V}\). A los elementos de \(E\) los llamamos aristas. Dada una arista \({\displaystyle (a,b)}\), \({\displaystyle a}\) es su nodo inicial y \({\displaystyle b}\) su nodo final.
Si se quiere remarcar la inexistencia de múltiples aristas entre cada par de vértices (y en el caso no dirigido, excluir bucles) el grafo puede llamarse simple. Por otra parte, si se quiere asegurar la posibilidad de permitir múltiples aristas, el grafo puede llamarse multigrafo.
Diremos que un grafo simple no orientado es:
- Un grafo completo cuando cada vértice se une con el resto de los vértices
- Un grafo bipartito si el conjunto de vértices se divide en dos conjuntos disjuntos de tal manera que las aristas únicamente unen vértices de un subconjunto con vértices del otro subconjunto. Diremos que es un grafo bipartito completo si cada vértice del primer subconjunto está unido mediante una arista con cada vértice del segundo
- Un ciclo si consiste únicamente en un camino cíclico.
Más definiciones la encontraréis en la bibliografía recomendada.
graphs: grafos con maxima
El paquete graphs proporciona estructuras de datos de grafos y dígrafos para Maxima. Los grafos y dígrafos son simples (no tienen aristas múltiples ni bucles), aunque los dígrafos pueden tener una arista dirigida de u a v y una arista dirigida de v a u.
Para trabajar con graphs es necesario cargar el paquete graphs. A continuación, utilizamos el comando
- create_graph (v_list, e_list): Creates a new graph on the set of vertices v_list and with edges e_list.
y lo mostramos con
- draw_graph (graph, option1, …, optionk): Draws the graph using the draw package.
Veamos un ejemplo:
(%i1) | load(«graphs»); |
(%i3) | g:create_graph([1,2,3,4], [[1,2], [2,3], [1,3],[1,4],[2,4]])$ draw_graph(g)$ |
También podemos crear digrafos:
(%i5) | g:create_graph([1,2,3,4], [[1,2], [2,4], [1,3],[1,4],[4,1]],directed= true)$ draw_graph(g, show_id=true, show_vertices=[1,2,3,4], show_vertex_size=3, show_vertex_color=green, edge_color=blue, edge_width=1, text_color=red)$ |
Las principales funciones para trabajar con grafos están en:
Ejercicio: Construir el grafo
Ejercicio: Construir el digrafo