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
Para las diferentes definiciones que utilizaremos: grafos, digrafos y multigrafos y otras más, seguimos la bibliografía recomendada.
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:
Grafo
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,\mathcal{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 \(\mathcal{E}\) puede ser cero. Si \(V=\{v_1,\ldots,v_2\}\) todo elemento de \(e\in \mathcal{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í \(\mathcal{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 \(G=(V,\mathcal{E})\) 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 un grafo \(G:(V,\mathcal{E})\) \[\mathbf{gr}(G)=2|\mathcal{E}|\]
Ejercicio: Determinar el grado del grafo
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, sí explicitamos cuando es un grafo dirigido o digrafo. En este caso, \({\displaystyle \mathcal{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 \(\mathcal{E}\) los llamamos aristas. Dada una arista \({\displaystyle (a,b)}\), \({\displaystyle a}\) es su nodo inicial y \({\displaystyle b}\) su nodo final.
Se llama orden del grafo \({\displaystyle G}\) a su número de vértices, \({\displaystyle |V|}\).
El grado de un vértice o nodo \({\displaystyle v\in V}\) es igual al número de aristas que lo tienen como extremo. Un grafo regular es un grafo en el que cada vértice tiene el mismo número de vecinos, es decir, cada vértice tiene el mismo grado.
Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.
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.
Propiedades
- Adyacencia: Dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
- Incidencia: una rista es incidente a un vértice si esta lo une a otro.
- Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.
- Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.
Grafo completo
Un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.
Un grafo completo de \(n\) vértices tiene \({\displaystyle n(n-1)/2}\) aristas, y se denota \({\displaystyle K_{n}}\). Es un grafo regular con todos sus vértices de grado \({\displaystyle n-1}\).
Ejercicio: Dibujar \({\displaystyle K_{4}\,}
Grafos bipartitos
Un grafo bipartito es un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos, de manera que las aristas no pueden relacionar vértices de un mismo conjunto.
Veamos la definición formal:
Definición: Un grafo \({\displaystyle G=(N,\mathcal{E})}\) es bipartito si \(N\) se puede particionar en dos conjuntos \(U\) y \(V\), es decir, tal que \({\displaystyle U\cup V=N}\) y \({\displaystyle U\cap V=\emptyset }\), de manera que las aristas sólo pueden conectar vértices de un conjunto con vértices del otro; formalmente:
\({\displaystyle \forall u_{1},u_{2}\in U,\forall v_{1},v_{2}\in V}\) no existe ninguna arista \({\displaystyle e=(u_{1},u_{2})}\) ni \({\displaystyle e=(v_{1},v_{2})}\).
Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.
Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul y los vértices de V de verde, obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un grafo no tiene la propiedad de que se puede colorear con dos colores no es bipartito.
Un grafo bipartito con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dos subconjuntos tienen la misma cantidad de elementos o cardinalidad, decimos que el grafo bipartito G es balanceado. Si todos los vértices del mismo lado de la bipartición tienen el mismo grado, entonces G es llamado grafo birregular.
Una aplicación la vemos en análisis de redes sociales; las redes diádicas son redes bimodales que se pueden representar como grafos bipartitos. Sin embargo, también se pueden definir grafos bipartitos sobre redes unimodales. Redes diádicas son redes bimodales en que los actores de un tipo se relacionan solo con los del otro tipo. Por ejemplo, una red de donaciones de empresas privadas a organizaciones sin fines de lucro.
Ejercicio: Demuestra que un grafo $G$ es bipartido si y solo si no contiene ciclos de longitud impar.
Ejercicio: Sea el grafo \(G(V,\mathcal{E})\), donde $V=\{A, B, C, D, E, F\}$ y $\mathcal{E}=\{(A,B), (B,C), (C,D), (D,E), (E,F), (F,A)\}$. ¿Es un grafo bipartido?
Un grafo bipartito completo es un grafo bipartito en el que todos los vértices de uno de los subconjuntos de la partición están conectados a todos los vértices del segundo subconjunto, y viceversa. El grafo completo bipartito con particiones de tamaño \({\displaystyle \left|V_{1}\right|=m}\) y \({\displaystyle \left|V_{2}\right|=n,}\) es denotado como \({\displaystyle K_{m,n}\,}\)
Ejercicio: Dibujar \({\displaystyle K_{3,4}\,}
Ejercicio: ¿Cuántas aristas tiene \({\displaystyle K_{m,n}\,}\)
Grafo de los divisores de un número
Un ejercicio sencillo es dibujar un grafo que representa los divisores de un número. Por ejemplo, consideremos el número 12, sus divisores son [1,2,3,4,6,12]. Ahora establecemos las aristas dirigidas, considerando una arista de v a u si v divide a u y no hay un divisor intermedio.
De Klaus Röder – Trabajo propio, CC BY-SA 3.0, Enlace. Grafo que representa los divisores del número 12. La distancia entre 1 y 6 es 2, por los caminos 1-2-6 o 1-3-6. La distancia entre 1 y 12 es 3.
Para construir un grafo que represente los divisores de un número \( n \), seguimos este procedimiento:
- Nodos: Cada nodo representa un divisor de \( n \).
- Aristas: Se dibuja una arista dirigida desde el nodo \( a \) al nodo \( b \) si \( a \) es divisor de \( b \) y no hay un divisor intermedio \( c \) tal que \( a \) divide a \( c \) y \( c \) divide a \( b \).
En adelante, a estos grafos, los llamaremos grafos de divisibilidad de un número.
Ejercicio: Construir el grafo de divisibilidad del número 24.
Grafo de Coprimalidad
Sea $S$ un subconjunto de los números naturales $\mathbb{N}$ (usualmente el conjunto $\{1, 2, \dots, n\}$). El grafo de coprimalidad $G(S)$ se define como:
- Vértices ($V$): Los elementos del conjunto $S$.
- Aristas ($E$): Dos vértices $u, v \in S$ están conectados si y solo si su máximo común divisor es 1:$$ \mathbf{mcd}(u, v) = 1 $$
Ejercicio: Dibuja el grafo de coprimalidad de $S = \{1, 2, 3, 4, 5, 6\}$
Ejercicio: Dibuja el grafo de coprimalidad de $S = \{4,6,9,10,15,21,32\}$
Grafo de factorización
Sea $S$ un subconjunto de los números naturales $\mathbb{N}$ (usualmente el conjunto $\{1, 2, \dots, n\}$). El grafo de factorización $G(S)$ se define como:
- Vértices ($V$): Los elementos del conjunto $S$.
- Aristas ($E$): Dos vértices $u, v \in S$ están conectados si y solo si su máximo común divisor es mayor de 1:$$ \mathbf{mcd}(u, v) > 1 $$
La condición anterior es equivalente a que dos vértices son adyacentes si tienen un primo en común. Generaliza el grafo de coprimalidad (es su “complementario parcial”)
Ejercicio: Dibuja el grafo de factorización de $S = \{4,6,9,10,15,21,32\}$