Grafos Simples y Multigrafos Explicados

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Tres definiciones, dos concesiones

Hay dos cosas que un conjunto de pares no ordenados no puede expresar: una arista que une un vértice consigo mismo y dos aristas distintas que unen el mismo par. Permitirlas o no da tres objetos diferentes, y conviene usar bien los nombres, porque los teoremas se enuncian sobre objetos concretos.

El grafo simple es la opción por defecto en casi toda la literatura, y su definición es la de la guía de vértices y aristas:

G = (V, E)      con   E ⊆ [V]²      cada arista es un subconjunto de 2 elementos de V

Como E es un conjunto de subconjuntos de 2 elementos, {v, v} no es admisible (tiene un solo elemento) y el mismo par no puede aparecer dos veces (un conjunto contiene cada elemento una sola vez). Ambas restricciones son consecuencias de la notación, no decisiones que alguien tomara.

Para levantarlas hace falta otro formalismo. El libro Graph Theory de Bondy y Murty da a las aristas una identidad propia y añade una función que indica qué par une cada una:

G = (V, E, ψ)      con   ψ: E → pares no ordenados de vértices (no necesariamente distintos)

Ahora e1 y e2 pueden ser elementos distintos de E con ψ(e1) = ψ(e2) = {u, v}, lo que forma un par de aristas paralelas, y ψ(e) = {v, v} es un lazo. Diestel llega al mismo punto con dos aplicaciones que envían cada arista a sus extremos, y West con una relación que asocia cada arista con sus extremos. El formalismo cambia; el contenido no.

Dos advertencias sobre el propio vocabulario, porque causan confusión real al leer artículos:

• «Multigrafo» no se usa de forma coherente. Algunos autores permiten lazos en un multigrafo, otros lo reservan para «pseudografo», y unos pocos llaman «multigrafo» a cualquier grafo. Comprueba la definición de la fuente antes de citar uno de sus teoremas.
• «Grafo» suele significar «grafo simple». La mayoría de los textos lo dicen una vez en el capítulo uno y no lo repiten nunca. Un resultado enunciado para «grafos» a menudo lleva una hipótesis implícita de simplicidad, y la sección 5 muestra lo mal que fallan algunos sin ella.

2. La teoría de grafos nació de un multigrafo

No es un caso marginal añadido después. El problema con el que empezó la disciplina es un multigrafo, y deja de ser el mismo problema si lo simplificas.

El artículo de Euler de 1736 sobre los puentes de Königsberg modela cuatro masas de tierra unidas por siete puentes. Dos puentes conectan la orilla norte con la isla y otros dos conectan la orilla sur con la isla. Son aristas paralelas, y ningún grafo simple puede contenerlas.

El criterio de Euler trata de la paridad de los grados, y son los puentes paralelos los que llevan los grados a donde están:

Multigrafo de Königsberg   7 aristas    grados 3, 5, 3, 3    cuatro impares  → no hay camino euleriano
Grafo simple subyacente    5 aristas    grados 2, 3, 2, 3    dos impares     → existe un camino

Elimina los duplicados y la respuesta se invierte. La multiplicidad no es un adorno del modelo: es el modelo, y el detalle histórico de la historia de la teoría de grafos es inseparable del formalismo. Quien cargue los siete puentes en una estructura de datos que elimine aristas duplicadas en silencio concluirá que Euler se equivocó.

3. Qué le hace un lazo al grado

El grado cuenta extremos de aristas que llegan a un vértice, no aristas. Un lazo tiene dos extremos y ambos caen en el mismo vértice, así que:

Un lazo en v aporta 2 a deg(v). Las aristas paralelas aportan 1 cada una, exactamente igual que aristas separadas.

Esa convención viene forzada, no elegida. El lema del apretón de manos cuenta de dos maneras los pares (vértice, extremo de arista en él), y toda arista, incluido un lazo, tiene exactamente dos extremos, así que ∑ deg(v) = 2m se cumple sin cambios en los pseudografos. Da a un lazo grado 1 y el teorema más antiguo de la disciplina se rompe de inmediato.

Algunas consecuencias que conviene tener presentes:

• Un vértice con un lazo y ninguna otra arista tiene grado 2, no 0, y no está aislado.
• El número de vértices de grado impar sigue siendo par, ya que la demostración solo usa ∑ deg(v) = 2m.
• En un grafo simple se cumple deg(v) = |N(v)|, el tamaño de la vecindad. En un multigrafo esa identidad falla: tres aristas paralelas hacia un mismo vecino dan grado 3 y un solo vecino. El código que calcula el grado como el tamaño de un conjunto de vecinos sin duplicados calcula el número equivocado.

4. Qué cambia la multiplicidad, y qué no puede cambiar

La pregunta útil no es «¿mi grafo es simple?», sino «¿la propiedad que calculo depende de la multiplicidad?». Las respuestas se dividen con claridad, y la división no es obvia.

Tres de esas filas merecen que se explique su razonamiento.

La coloración ignora las aristas paralelas, pero muere con los lazos. Una coloración propia exige que los extremos de cada arista reciban colores distintos. Una segunda copia de {u, v} repite una restricción que ya existe, así que el conjunto de coloraciones propias, y por tanto el número cromático y el polinomio cromático, son exactamente los del grafo simple subyacente. Un lazo exige c(v) ≠ c(v), que nada cumple, así que un pseudografo con un lazo no tiene ninguna coloración propia y su polinomio cromático es idénticamente cero. Por eso la coloración de grafos se enuncia casi siempre para grafos sin lazos.

El número de árboles de expansión sí depende de la multiplicidad. Dos vértices unidos por una sola arista tienen un árbol de expansión; unidos por dos aristas paralelas tienen dos, porque elegir una u otra arista da un árbol distinto. El teorema matriz-árbol de Kirchhoff, de 1847, los cuenta a partir de la matriz laplaciana, y se enuncia para multigrafos precisamente porque las multiplicidades entran en la matriz como conteos fuera de la diagonal. Las redes eléctricas, donde Kirchhoff se encontró con el problema, tienen con frecuencia componentes en paralelo.

Los cortes y los flujos dependen de la multiplicidad. El número mínimo de aristas cuya eliminación separa u de v es 1 cuando las une una sola arista y 2 cuando las unen dos. Como el flujo máximo es igual al corte mínimo, lo mismo vale para el flujo: k aristas paralelas de capacidad unitaria transportan k unidades. Esa es exactamente la razón por la que un multigrafo con capacidades unitarias es el modelo no ponderado natural de una red de flujo.

5. Todas las cotas de grafos simples dejan de cumplirse

Una gran parte de los resultados estándar lleva una hipótesis implícita de simplicidad, y sin ella no se degradan poco a poco. Fallan del todo.

Las dos filas que sobreviven merecen tanta atención como las que fallan. El lema del apretón de manos y la fórmula poliédrica de Euler se demuestran contando incidencias, y a los argumentos de conteo no les importa si dos aristas unen por casualidad el mismo par. Las cotas que fallan son las que se demuestran eligiendo pares distintos de vértices, que es precisamente el paso que un multigrafo invalida.

La versión práctica de esta sección: cuando consultes una cota, comprueba si su demostración cuenta incidencias o cuenta pares. La primera clase se traslada a los multigrafos; la segunda, no.

6. Almacenamiento: donde la matriz de adyacencia se queda corta

Las tres representaciones estándar se degradan de forma muy distinta, y las diferencias deciden cuál usar.

La matriz de adyacencia deja de ser una matriz 0/1. La extensión natural guarda el número de aristas que unen cada par, así que la entrada (u, v) pasa a ser un conteo, y un lazo pone por convención 2 en la diagonal para que las sumas de filas sigan dando los grados. Funciona, pero tiene una limitación fatal para datos reales: un conteo no puede llevar información por arista. Si tus tres vuelos paralelos tienen cada uno un precio distinto, una matriz de conteos no tiene dónde guardarlos.

simple        A[u][v] ∈ {0, 1}
multigrafo    A[u][v] = número de aristas que unen u y v
pseudografo   A[v][v] = 2 × (número de lazos en v)      para que las sumas de filas sean los grados

La lista de adyacencia conserva los duplicados. La lista de u simplemente contiene a v tantas veces como aristas los unan. El código de recorrido no cambia, y BFS o DFS considerarán el mismo vecino varias veces, lo cual es inofensivo cuando la comprobación de visitados es sobre vértices.

La lista de aristas se convierte en el formato natural. Es la representación que realmente encaja con las matemáticas: cada arista es un registro con identidad propia, así que las aristas paralelas son simplemente registros distintos y los atributos por arista tienen dónde vivir. Es la definición mediante función de incidencia de la sección 1 expresada como estructura de datos.

De aquí se deduce un principio de diseño, y es lo más útil que puedes llevarte de esta sección:

En un multigrafo, las aristas necesitan identidades. Un par de extremos ya no identifica una arista, así que todo lo que se refiera a una arista, sea un emparejamiento, un árbol de expansión, un flujo o un borrado, debe referirse a un ID de arista y no a (u, v).

Casi todos los errores con multigrafos vienen de esa única frase. Guardar un árbol de expansión como un conjunto de pares de vértices, o un conjunto de aristas visitadas con clave (u, v), confunde en silencio las aristas paralelas y produce respuestas erróneas que ningún comprobador de tipos detectará.

7. A qué algoritmos les importa

La mayoría de los algoritmos de tipo recorrido son indiferentes a la multiplicidad, porque marcan vértices. Los que marcan o seleccionan aristas necesitan atención.

La fila de Karger es la que sorprende, y merece explicarse entera porque invierte el instinto habitual. El algoritmo aleatorizado de corte mínimo de Karger contrae repetidamente una arista elegida uniformemente al azar, fusionando sus dos extremos en un único vértice. La contracción convierte dos aristas que apuntaban a los dos vértices fusionados en dos aristas paralelas que apuntan al nuevo, y el análisis probabilístico del algoritmo depende de conservar todas las copias, porque la probabilidad de contraer una arista es proporcional a cuántas copias hay. Simplifica el grafo intermedio y el algoritmo deja de ser correcto. Lo mismo ocurre con el paso de contracción del algoritmo de árbol de expansión de Borůvka.

8. Cuándo un multigrafo no es opcional

Los multigrafos no son una rareza que haya que normalizar. Son el modelo honesto siempre que dos entidades puedan relacionarse más de una vez y las relaciones individuales importen:

• Redes de transporte. Dos ciudades unidas por tres vuelos distintos, o una carretera y una línea de tren entre el mismo par. Cada una tiene su propia duración, precio y capacidad.
• Circuitos eléctricos. Componentes en paralelo entre los mismos dos nodos, que es exactamente el contexto en el que Kirchhoff desarrolló el teorema matriz-árbol en 1847.
• Grafos de transacciones y pagos. Dos cuentas pueden hacer muchas transacciones entre sí; fusionarlas en una arista pierde importes, marcas de tiempo y el propio conteo, que suele ser la señal que se busca.
• Grafos de reacciones químicas y moleculares. Los enlaces dobles y triples son aristas paralelas en el modelo clásico de grafo de una molécula.
• Grafos de conocimiento y RDF. Dos entidades relacionadas por varios predicados distintos. Por eso estos datos suelen guardarse como ternas, que es una lista de aristas con una etiqueta por arista.
• Todo lo construido por contracción. El algoritmo de Karger, el de Borůvka y los pasos de condensación de muchos algoritmos de aproximación crean aristas paralelas mientras se ejecutan, sea cual sea la entrada.
• Problemas de rutas eulerianas. La limpieza de calles y las rutas postales necesitan recorrer cada calle física, y dos calles entre los mismos cruces son dos obligaciones.

9. Simplificar, y lo que cuesta

Convertir un multigrafo en un grafo simple suele ser la decisión correcta, y solo es seguro si sabes cuáles de las propiedades de la sección 4 estás a punto de cambiar. Hay tres formas estándar, y responden preguntas distintas:

Fíjate en que la segunda y la tercera regla son incompatibles: sumar es correcto para capacidades e incorrecto para distancias, y tomar el mínimo es correcto para distancias e incorrecto para capacidades. Cuál se aplica depende de cómo se combinan los pesos a lo largo de un camino, que es el tema de la guía complementaria sobre grafos ponderados y no ponderados. Elegir la fusión equivocada responde en silencio a otra pregunta, y después el grafo parecerá perfectamente razonable.

Una cuarta opción suele ser mejor que todas ellas: conserva el multigrafo y deja que el algoritmo lo gestione. BFS, DFS, Dijkstra, Kruskal y Prim funcionan correctamente sobre multigrafos tal como están, así que simplificar a menudo no aporta nada y cuesta información.

10. Multigrafos dirigidos

Todo lo anterior se traslada a los grafos dirigidos, con una distinción adicional que conviene nombrar. En un digrafo, los arcos (u, v) y (v, u) ya son objetos distintos, lo cual no es multiplicidad sino dirección: ese par es un dígono, y un digrafo ordinario ya puede contener uno sin ampliar su definición. Muchos digrafos no contienen ninguno: un DAG nunca lo hace. La multiplicidad en el caso dirigido significa dos o más arcos con la misma cola y la misma cabeza, lo que de nuevo requiere una definición al estilo de la función de incidencia, como en el libro Digraphs de Bang-Jensen y Gutin.

Las consecuencias prácticas se trasladan directamente: el grado de entrada y el de salida cuentan arcos y no vecinos distintos, un lazo dirigido suma 1 a ambos, y las condiciones eulerianas en un multigrafo dirigido siguen comparando el grado de entrada con el de salida en cada vértice.

11. Errores comunes

• Cargar un multigrafo en una estructura que elimina duplicados. Un Set de pares, una matriz de adyacencia de booleanos o una restricción de unicidad en base de datos sobre (u, v) descartan en silencio las aristas paralelas. El grafo parece correcto y todos los conteos están mal.
• Identificar las aristas por sus extremos. En un multigrafo, (u, v) nombra un conjunto de aristas, no una. Los emparejamientos, los árboles de expansión, los flujos y los conjuntos de aristas visitadas deben usar IDs de arista como clave.
• Calcular el grado como el número de vecinos. Correcto en un grafo simple, incorrecto en cuanto se duplica una arista o aparece un lazo.
• Dar a un lazo grado 1. Aporta 2, y el lema del apretón de manos depende de ello.
• Aplicar m ≤ n(n-1)/2. Esa cota, y todo lo que se deriva de ella, incluido el razonamiento sobre disperso frente a denso, necesita simplicidad.
• Simplificar antes de un cálculo euleriano, de corte o de flujo. Los tres dependen de la multiplicidad, como demuestra Königsberg con el ejemplo fundacional de la disciplina.
• Eliminar duplicados dentro de un algoritmo de contracción. Los algoritmos de Karger y Borůvka crean aristas paralelas a propósito y necesitan conservarlas.
• Suponer que una biblioteca hace lo que esperas. Las bibliotecas de grafos difieren en si añadir una arista existente crea un duplicado, se ignora o lanza un error. Compruébalo una vez, en un test.

12. Glosario

14. Referencias

Las definiciones, teoremas y atribuciones anteriores proceden de estas fuentes, ordenadas cronológicamente.

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (publicado en 1741), 128 a 140. Los puentes de Königsberg, modelados como multigrafo.
2. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik 148(12), 497 a 508. El teorema matriz-árbol, desarrollado sobre redes eléctricas con componentes en paralelo.
3. Harary, F. (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley. Distingue grafos, multigrafos y pseudografos.
4. Karger, D. R. (1993). "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-cut Algorithm." Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 21 a 30. El algoritmo de contracción que crea aristas paralelas mientras se ejecuta.
5. Karger, D. R. y Stein, C. (1996). "A New Approach to the Minimum Cut Problem." Journal of the ACM 43(4), 601 a 640.
6. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. Nueva York: Springer.
7. West, D. B. (2001). Introduction to Graph Theory, 2.ª edición. Upper Saddle River: Prentice Hall. Define un grafo mediante un conjunto de vértices, un conjunto de aristas y una relación de extremos, lo que admite lazos y aristas paralelas.
8. Bondy, J. A. y Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres: Springer. Origen de la definición mediante función de incidencia de la sección 1.
9. Bang-Jensen, J. y Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2.ª edición. Londres: Springer. Multigrafos dirigidos.
10. Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición. Cambridge, Massachusetts: MIT Press.
11. Wilson, R. J. (2010). Introduction to Graph Theory, 5.ª edición. Harlow: Prentice Hall. Desarrolla los multigrafos junto a los grafos simples desde el primer capítulo.
12. Chartrand, G., Lesniak, L. y Zhang, P. (2015). Graphs & Digraphs, 6.ª edición. Boca Raton: CRC Press.
13. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer. Origen de la definición de grafo simple y de la formulación de multigrafo con dos aplicaciones de extremos.