Grafos Dirigidos y No Dirigidos Explicados

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Las dos definiciones, lado a lado

La diferencia entre un grafo dirigido y uno no dirigido es una sola palabra de la definición: si el par que une dos vértices está ordenado. Todo lo demás en este artículo, incluido qué algoritmos siguen funcionando, es consecuencia de esa palabra.

Un grafo no dirigido es el objeto estándar tratado en la guía de vértices y aristas. Siguiendo el libro Graph Theory de Diestel:

G = (V, E)      con   E ⊆ [V]²      una arista es un par no ordenado {u, v}

Un grafo dirigido, o digrafo, sustituye el par no ordenado por uno ordenado:

D = (V, A)      con   A ⊆ V × V      un arco es un par ordenado (u, v)

Como (u, v) y (v, u) son pares ordenados distintos, ambos pueden estar presentes a la vez, y se dice que un digrafo que contiene ambos tiene un dígono entre u y v. En el mundo no dirigido no hay nada que distinguir: {u, v} y {v, u} son el mismo conjunto, así que la arista existe una vez o no existe.

Diestel ofrece una formulación más general que conviene conocer, porque es la que resiste el contacto con datos reales. Un grafo dirigido es un par (V, E) de conjuntos disjuntos junto con dos aplicaciones

init: E → V        asigna a cada arista su vértice inicial
ter:  E → V        asigna a cada arista su vértice final

Aquí un arco es un objeto por derecho propio y no un par, de modo que la definición admite arcos paralelos y lazos sin ningún caso especial. Es la contrapartida dirigida de la definición mediante función de incidencia que necesitan los multigrafos, y es la razón por la que un horario con tres vuelos diarios distintos de A a B sigue siendo un digrafo perfectamente válido.

La relación formal con la lógica es exacta y merece enunciarse una vez: un grafo no dirigido sin lazos es precisamente una relación simétrica irreflexiva sobre V, mientras que un digrafo es una relación binaria arbitraria sobre V. La dirección es lo que obtienes cuando dejas de exigir que la relación sea simétrica.

Estos dos grafos son el ejemplo recurrente de todo el artículo. El digrafo es

V = {A, B, C, D, E}
A = { (A,B), (B,C), (C,A), (C,D), (D,E), (E,D) }        6 arcos

y el grafo no dirigido de la izquierda es su grafo subyacente, con 5 aristas, ya que los arcos opuestos entre D y E se convierten en la única arista {D, E}.

2. Aristas, arcos, colas y cabezas

El vocabulario cambia junto con la definición, y los cambios no son decorativos. El libro Digraphs de Bang-Jensen y Gutin, la referencia estándar del lado dirigido, reserva con cuidado palabras distintas para que un enunciado nunca sea ambiguo sobre el objeto al que se refiere.

Dos términos merecen su propia línea porque se confunden constantemente. Un grafo orientado es un digrafo sin dígonos: tomaste un grafo no dirigido y elegiste una dirección para cada arista. Todo grafo orientado es un digrafo, pero un digrafo que contiene tanto (u,v) como (v,u) no es un grafo orientado. Esta distinción es todo el tema de la sección 5.

3. El grado se divide en dos

En un grafo no dirigido, el grado de un vértice cuenta los extremos de aristas que llegan a él, y el lema del apretón de manos dice que esos conteos suman el doble del número de aristas. En un digrafo cada arco tiene una cola y una cabeza en lugar de dos extremos simétricos, así que el conteo único se divide en dos:

• Grado de salida d+(v): el número de arcos cuya cola es v.
• Grado de entrada d-(v): el número de arcos cuya cabeza es v.

y la identidad única también se divide en dos:

no dirigido    ∑v∈V deg(v)   =  2m           cada arista tiene dos extremos

dirigido       ∑v∈V d+(v)  =  ∑v∈V d-(v)  =  |A|
                                             cada arco tiene una cola y una cabeza

El factor 2 que falta confunde a mucha gente. No es un teorema diferente: es el mismo argumento de doble conteo aplicado a un conjunto cuyos elementos ahora contribuyen a dos sumas separadas en lugar de contribuir dos veces a una sola.

Compruébalo en el ejemplo recurrente. Los grados de salida son A 1, B 1, C 2, D 1, E 1, que suman 6. Los grados de entrada son A 1, B 1, C 1, D 2, E 1, que también suman 6, el número de arcos. En el grafo no dirigido subyacente los grados son 2, 2, 3, 2, 1, que suman 10, el doble de sus 5 aristas.

De aquí salen de inmediato dos tipos de vértice con nombre propio que no tienen equivalente alguno en el caso no dirigido:

• Una fuente tiene grado de entrada 0: nada apunta hacia ella.
• Un sumidero tiene grado de salida 0: no apunta a nada.

Las fuentes y los sumideros son los puntos de entrada y salida de las redes de flujo y las posiciones inicial y final de un orden topológico. En un grafo no dirigido estos conceptos simplemente no se pueden expresar.

4. Qué cambia en la matriz y en la lista

La dirección se nota en el almacenamiento tan claramente como en la definición, y las diferencias son las que exponen Cormen, Leiserson, Rivest y Stein en Introduction to Algorithms.

La matriz de adyacencia. En un grafo no dirigido la matriz siempre es simétrica, A = AT, porque {u, v} y {v, u} son la misma arista. En un digrafo, en general, no lo es, y esa asimetría contiene información real:

• Las sumas de filas son grados de salida, las sumas de columnas son grados de entrada. En el caso no dirigido ambas dan el grado, por eso la distinción nunca aparece.
• La traspuesta AT es exactamente el digrafo inverso, con cada arco invertido. Invertir un grafo no dirigido no hace nada, que es otra forma de decir que A = AT.
• La entrada (Ak)uv cuenta los recorridos de longitud k de u a v en ambos mundos, pero en el caso dirigido esos recorridos deben respetar las flechas, así que el conteo en general es distinto de (Ak)vu.

La lista de adyacencia. Un grafo no dirigido almacena cada arista dos veces, una en la lista de cada extremo, así que las listas contienen 2m entradas. Un digrafo almacena cada arco una vez, en la lista de la cola, lo que da m entradas. Esto tiene una consecuencia práctica que sorprende la primera vez: para recorrer un digrafo hacia atrás necesitas una segunda estructura, la lista de adyacencia inversa, porque la lista de un vértice te dice adónde puedes ir, no de dónde viniste. El algoritmo de Kosaraju para componentes fuertemente conexas se basa directamente en esta observación y recorre el grafo inverso en su segunda pasada.

De aquí salen dos cotas. Un grafo simple no dirigido con n vértices tiene como mucho n(n-1)/2 aristas. Un digrafo sin lazos tiene como mucho n(n-1) arcos, exactamente el doble, porque cada par ordenado es ahora un hueco propio.

5. Orientaciones y el grafo subyacente

Los dos mundos están conectados por un par de construcciones que van en direcciones opuestas, y nombrarlas bien elimina mucha confusión.

• Dado un digrafo D, su grafo subyacente es lo que obtienes al olvidar las flechas: sustituye cada arco (u, v) por la arista {u, v} y descarta los duplicados. El grafo subyacente del ejemplo recurrente tiene 5 aristas, una menos que los 6 arcos del digrafo, porque el dígono entre D y E se funde.
• Dado un grafo no dirigido G, una orientación suya es un digrafo que se obtiene eligiendo exactamente una dirección para cada arista. El resultado es un grafo orientado: sin dígonos, ya que cada arista produce un solo arco.

No son operaciones inversas. Tomar el grafo subyacente pierde información que ninguna orientación puede recuperar, y un grafo con m aristas tiene 2m orientaciones distintas, ya que cada arista es una elección binaria independiente. El grafo subyacente del ejemplo recurrente tiene 5 aristas y por tanto 32 orientaciones, y el digrafo original ni siquiera es una de ellas, porque tiene un dígono.

Eso plantea la pregunta que responde la siguiente sección. De esas 2m orientaciones, ¿alguna es buena, en el sentido de que todavía se puede llegar a todas partes?

6. Teorema de Robbins: qué calles pueden ser de sentido único

En 1939 Herbert Robbins publicó un breve artículo en el American Mathematical Monthly con el memorable título «A theorem on graphs, with an application to a problem of traffic control». El problema es exactamente el de un urbanista: si todas las calles pasan a ser de sentido único, ¿pueden los conductores seguir llegando a cualquier parte de la ciudad?

Teorema de Robbins. Un grafo no dirigido conexo tiene una orientación fuertemente conexa si y solo si no tiene puentes.

Un puente, también llamado arista de corte, es una arista cuya eliminación desconecta el grafo. Un grafo conexo sin puentes es exactamente un grafo 2-arista-conexo, uno en el que cada arista está en un ciclo. (La conexidad importa aquí: un grafo no conexo puede no tener puentes sin ser 2-arista-conexo.)

Una dirección de la demostración es la fácil y vale la pena verla, porque explica todo el resultado. Supón que e = {u, v} es un puente, de modo que eliminarlo divide el grafo en una componente que contiene u y otra que contiene v. Cualquier orientación debe mandar e en un sentido o en el otro. Si se convierte en (u, v) , nada del lado de vpuede volver jamás al lado de u, porque e era la única conexión y ahora apunta en el sentido equivocado. Si se convierte en (v, u) , el mismo argumento funciona al revés. En ambos casos la orientación no es fuertemente conexa. El recíproco, que todo grafo conexo sin puentes sí admite una orientación fuertemente conexa, es la mitad sustancial, y la demostración estándar ejecuta una búsqueda en profundidad y orienta las aristas del árbol alejándose de la raíz y las aristas de retroceso hacia ella.

El ejemplo recurrente hace concreto el teorema. Su grafo subyacente contiene el triángulo A, B, C, que no tiene puentes, pero las aristas {C, D} y {D, E} son ambas puentes. Así que, por el teorema de Robbins, ninguna orientación de ese grafo es fuertemente conexa, y precisamente por eso el digrafo de la figura no es fuertemente conexo por mucho que redibujes las flechas.

Nash-Williams generalizó el resultado en 1960: todo grafo no dirigido 2k-arista-conexo tiene una orientación k-arco-conexa, de la que el teorema de Robbins es el caso k = 1. La lectura práctica no cambia. Los sistemas de sentido único son seguros justo donde la red viaria tiene redundancia, y una única carretera que conecta un barrio con el resto de la ciudad nunca puede hacerse de sentido único sin aislarlo.

7. La conexidad se convierte en tres preguntas distintas

En un grafo no dirigido, la conexidad es un simple sí o no: ¿hay un camino entre cada par de vértices? La dirección lo convierte en una jerarquía. La clasificación se debe a Structural Models de Harary, Norman y Cartwright, y es la parte de la teoría de grafos dirigidos que más a menudo se salta y más a menudo se necesita.

Cada condición implica la de debajo, así que fuerte implica unilateral, que implica débil. El ejemplo recurrente queda justo en el centro de la jerarquía, que es el caso habitual en la práctica: puedes salir del triángulo A, B, C hacia D y E, pero nunca volver.

El refinamiento útil es dejar de preguntar por el digrafo entero y preguntar por sus partes. Una componente fuertemente conexa, o CFC, es un conjunto maximal de vértices en el que cada vértice alcanza a todos los demás. Todo digrafo se particiona de forma única en CFC, y contraer cada una a un solo vértice produce la condensación, que siempre es acíclica. Este último hecho no es casualidad: si la condensación tuviera un ciclo, cada componente del ciclo alcanzaría a todas las demás, así que desde el principio habrían sido una sola CFC.

Encontrar las CFC lleva tiempo lineal. El artículo de Tarjan de 1972, «Depth-first search and linear graph algorithms», lo hace en un único recorrido en profundidad usando valores low-link, y el método de Kosaraju-Sharir lo hace en dos pasadas, la segunda sobre el digrafo inverso. Ambos se ejecutan en O(n + m), y ninguno tiene equivalente no dirigido, porque en un grafo no dirigido las componentes conexas salen de cualquier recorrido.

8. Ciclos, DAG y orden topológico

La palabra «ciclo» pasa a significar algo más estricto en cuanto hay flechas, y esa diferencia causa errores reales.

En un grafo simple no dirigido, un ciclo es un recorrido cerrado sin vértices repetidos y necesita al menos tres vértices, ya que ir por una arista y volver directamente no se considera un ciclo. Un grafo no dirigido sin ciclos es un bosque, y uno conexo es un árbol.

En un digrafo, un ciclo dirigido debe seguir las flechas en todo el recorrido, y un dígono cuenta: los dos arcos (D, E) y (E, D) forman un ciclo dirigido de longitud 2. Un digrafo sin ciclos dirigidos es un DAG, un grafo dirigido acíclico, y los DAG tienen una propiedad que nada en el mundo no dirigido posee:

Un digrafo tiene un orden topológico, una disposición lineal de sus vértices en la que todo arco apunta hacia delante, si y solo si es acíclico.

El artículo de Kahn de 1962 en Communications of the ACM dio el algoritmo estándar: toma repetidamente un vértice de grado de entrada 0, emítelo y elimínalo junto con sus arcos salientes. Si el digrafo se vacía, la salida es un orden topológico; si se atasca con vértices restantes, cada superviviente está en un ciclo. Los detalles están en la guía del orden topológico.

De todo esto se derivan dos trampas:

• Que el grafo subyacente tenga un ciclo no dice nada. El grafo subyacente del ejemplo recurrente contiene el triángulo A, B, C, y su digrafo sí contiene ahí un ciclo dirigido. Pero orienta ese mismo triángulo como A → B, A → C, B → C y tendrás un DAG cuyo grafo subyacente sigue teniendo un ciclo. La detección de ciclos no dirigida no puede responder una pregunta dirigida.
• La detección de ciclos es un algoritmo distinto. En un grafo no dirigido, una DFS encuentra un ciclo cuando llega a cualquier vértice ya visitado que no sea el padre del que vino. En un digrafo esa prueba es incorrecta: debes encontrar una arista de retroceso hacia un vértice que siga en la pila de recursión actual, ya que un arco hacia un vértice ya terminado es inofensivo.

9. Qué algoritmos se trasladan y cuáles se rompen

La pregunta práctica es qué partes de la caja de herramientas no dirigida sobreviven al cambio. El patrón es más claro de lo que parece: todo lo que solo sigue aristas hacia delante se traslada, y todo lo que depende de la simetría, no.

La fila del árbol de expansión mínima es la que atrapa incluso a gente experimentada. Los algoritmos de Kruskal y Prim son voraces sobre una estructura de costes simétrica, y ninguno sobrevive a la orientación. La pregunta dirigida correcta es la arborescencia de expansión mínima: elegir un conjunto de arcos de peso total mínimo tal que todo vértice sea alcanzable desde una raíz fija. Chu y Liu en 1965 y Edmonds en 1967 lo resolvieron de forma independiente, y el algoritmo no se parece en nada a un recorrido de aristas ordenadas: selecciona el arco entrante más barato de cada vértice, luego contrae cualquier ciclo que se forme y repite.

10. Cómo elegir: ¿tu relación es simétrica?

La pregunta de modelado tiene una sola forma: si la relación se cumple de u a v, ¿debe cumplirse también de v a u? Si la respuesta es sí, usa un grafo no dirigido. Si es no, o si no estás seguro, usa un digrafo, porque un digrafo siempre puede expresar una relación simétrica, pero no al revés.

Un caso merece atención especial porque parece simétrico y no lo es. Una arista no dirigida solo puede llevar un peso. Si el coste de ir de u a v difiere del coste de volver, la relación es mutua pero el modelo aun así debe ser dirigido. Pedalear cuesta arriba y cuesta abajo, subir y bajar datos por un enlace asimétrico y cambiar divisas en un sentido o en el otro son conexiones mutuas con dos costes distintos, y cada una obliga a usar un digrafo con dos arcos de pesos diferentes.

11. Conversión entre ambos

Tres conversiones aparecen constantemente, y cada una pierde o inventa algo que conviene tener presente.

• De digrafo a no dirigido (simetrización). Sustituye cada arco por una arista. Esto inventa alcanzabilidad: tras simetrizar el ejemplo recurrente, D alcanza a A, lo cual era falso en el original. Úsala solo cuando de verdad quieras preguntar algo sobre la estructura subyacente, como si el digrafo es débilmente conexo. Una variante más estricta conserva solo los pares mutuos y da el grafo «recíproco», que no inventa nada pero descarta muchísimo.
• De no dirigido a digrafo (orientación). Elige una dirección por arista. Esto descarta la alcanzabilidad mutua salvo que el grafo no tenga puentes, que es exactamente el teorema de Robbins de la sección 6.
• No dirigido como digrafo (duplicación de arcos). Sustituye cada arista {u, v} por los dos arcos (u, v) y (v, u). Es lo que hace internamente casi toda biblioteca de grafos, y es fiel para recorridos y caminos más cortos. Pero convierte cada arista en un ciclo dirigido de longitud 2, así que cualquier prueba de DAG responde ahora que no, cada componente conexa se vuelve una única componente fuertemente conexa, y un detector de ciclos informa de un ciclo por cada arista. La representación está bien; ejecutar sobre ella algoritmos estructurales dirigidos, no.

12. Errores comunes

• Construir la lista de adyacencia en un solo sentido para un grafo no dirigido. El error de grafos más común que existe. Leer una lista de aristas y añadir solo adj[u].push(v) produce en silencio un digrafo, y tu BFS no encuentra un camino a lo largo de una arista que puede ver.
• Construirla en ambos sentidos para un grafo dirigido. El mismo error al revés, y más difícil de detectar: el código se ejecuta, los caminos parecen plausibles, y toda respuesta que dependía de la dirección es incorrecta.
• Usar detección de ciclos no dirigida en un digrafo. Informar de un ciclo cada vez que la DFS encuentra un vértice visitado que no es el padre marca muchos DAG como cíclicos. Los digrafos necesitan la prueba de la arista de retroceso a la pila de recursión.
• Suponer que la alcanzabilidad es simétrica. «¿Hay un camino de u a v?» y «¿hay un camino de v a u?» son dos consultas diferentes en un digrafo, y responder una no responde la otra.
• Olvidar que necesitas el grafo inverso. «¿Qué vértices pueden alcanzar a v?» no se puede responder con la lista de adyacencia directa sin un recorrido completo. Construye una vez la lista inversa si haces esa pregunta a menudo.
• Recurrir a un MST en un digrafo. Kruskal y Prim no tienen versión dirigida. Lo que quieres es una arborescencia mínima.
• Simetrizar para reutilizar una biblioteca. Es cómodo, y cambia la respuesta. Cada conversión de la sección 11 tiene un coste, así que hazla de forma deliberada.

13. Glosario

15. Referencias

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

1. Robbins, H. E. (1939). "A theorem on graphs, with an application to a problem of traffic control." American Mathematical Monthly 46(5), 281 a 283. El teorema de orientación sin puentes de la sección 6.
2. Ford, L. R. y Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics 8, 399 a 404. El flujo, planteado sobre un digrafo desde el principio.
3. Nash-Williams, C. St. J. A. (1960). "On orientations, connectivity and odd-vertex-pairings in finite graphs." Canadian Journal of Mathematics 12, 555 a 567. La generalización de Robbins a la k-arco-conexidad.
4. Kahn, A. B. (1962). "Topological sorting of large networks." Communications of the ACM 5(11), 558 a 562.
5. Chu, Y. J. y Liu, T. H. (1965). "On the shortest arborescence of a directed graph." Scientia Sinica 14, 1396 a 1400.
6. Harary, F., Norman, R. Z. y Cartwright, D. (1965). Structural Models: An Introduction to the Theory of Directed Graphs. Nueva York: Wiley. Origen de la clasificación en conexidad fuerte, unilateral y débil.
7. Edmonds, J. (1967). "Optimum branchings." Journal of Research of the National Bureau of Standards 71B(4), 233 a 240.
8. Tarjan, R. E. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing 1(2), 146 a 160. Componentes fuertemente conexas en tiempo lineal.
9. Sharir, M. (1981). "A strong-connectivity algorithm and its applications in data flow analysis." Computers & Mathematics with Applications 7(1), 67 a 72. El método de dos pasadas que suele asociarse al nombre de Kosaraju.
10. Brin, S. y Page, L. (1998). "The anatomy of a large-scale hypertextual Web search engine." Computer Networks and ISDN Systems 30(1 a 7), 107 a 117. PageRank sobre el digrafo de la web.
11. West, D. B. (2001). Introduction to Graph Theory, 2.ª edición. Upper Saddle River: Prentice Hall.
12. Bondy, J. A. y Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres: Springer.
13. Bang-Jensen, J. y Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2.ª edición. Londres: Springer. La referencia estándar de la terminología de grafos dirigidos.
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición. Cambridge, Massachusetts: MIT Press. Origen de los costes de representación de la sección 4.
15. Chartrand, G., Lesniak, L. y Zhang, P. (2015). Graphs & Digraphs, 6.ª edición. Boca Raton: CRC Press. Un libro de texto que desarrolla ambos objetos en paralelo.
16. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer. Origen de las dos definiciones citadas en la sección 1.