Componentes conexas, puentes y puntos de articulación

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Qué significa «conexo»

Un grafo es conexo cuando hay un camino entre cada par de sus vértices. Puedes empezar en cualquier parte y, siguiendo aristas, llegar a todas partes. Cuando eso falla, el grafo se descompone en piezas llamadas componentes conexas: los mayores subgrafos conexos que contiene, sin ninguna arista entre dos piezas distintas.

La forma más clara de ver las componentes es a través de la relación «u puede alcanzar a v». Es reflexiva (cada vértice se alcanza a sí mismo por el camino vacío), simétrica (en un grafo no dirigido un camino puede recorrerse al revés) y transitiva (dos caminos pueden unirse uno tras otro). Una relación con esas tres propiedades es una relación de equivalencia, y toda relación de equivalencia divide su conjunto en clases disjuntas. Las clases de la alcanzabilidad son exactamente las componentes. Por eso cada vértice pertenece a exactamente una componente, y por eso un vértice aislado, sin ninguna arista, es una componente por sí solo.

Un solo grafo recorre todo el artículo. Tiene doce vértices y trece aristas, y está construido para que cada idea de abajo tenga un ejemplo concreto y, cuando importa, un contraejemplo concreto:

V = {A, B, C, D, E, F, G, H, I, J, K, L}
E = {AB, BC, CA, CD, DE, EC, EF, FG, GH, HI, IF, IJ, KL}        13 aristas

componente 1 = {A, B, C, D, E, F, G, H, I, J}    12 aristas
componente 2 = {K, L}                              1 arista

El vocabulario viene de la guía de vértices y aristas, y todo lo que sigue trata de grafos no dirigidos hasta la sección 11, donde la dirección cambia la historia.

2. Encontrar las componentes

Como las componentes son clases de alcanzabilidad, cualquier búsqueda en el grafo las encuentra. Lanza una búsqueda en anchura o en profundidad desde algún vértice; todo lo que alcanza es la componente de ese vértice. Luego vuelve a empezar desde cualquier vértice aún no alcanzado, y repite hasta que no quede ninguno. Cada nuevo comienzo es una componente más.

from collections import deque

def connected_components(graph):
    """Etiqueta cada vértice de un grafo no dirigido con el índice de su componente."""
    label, components = {}, []
    for start in graph:                      # los vértices aislados forman su propia componente
        if start in label:
            continue
        label[start] = len(components)
        members, queue = [start], deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in label:
                    label[v] = len(components)
                    members.append(v)
                    queue.append(v)
        components.append(sorted(members))
    return components, label

edges = ['AB', 'BC', 'CA', 'CD', 'DE', 'EC', 'EF', 'FG', 'GH', 'HI', 'IF', 'IJ', 'KL']
graph = {v: [] for v in 'ABCDEFGHIJKL'}
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

components, label = connected_components(graph)
print(len(components), components)
# 2 [['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'], ['K', 'L']]
print(label['H'] == label['A'], label['K'] == label['A'])
# True False

Cada vértice se etiqueta una vez y cada arista se examina dos veces, una desde cada extremo, así que todo el trabajo lleva un tiempo O(V + E) en total. El bucle exterior sobre todos los vértices es la línea importante. Una sola búsqueda responde a «qué puedo alcanzar desde aquí», no a «cuántas piezas hay», y olvidar el bucle es una forma habitual de contar 1 componente en un grafo que tiene varias.

Vale la pena conocer dos alternativas. Si las aristas llegan de una en una y solo las añades, una estructura union-find mantiene las componentes al día en un tiempo amortizado casi constante por arista: cada arista fusiona las clases de sus dos extremos, y dos vértices están en la misma componente exactamente cuando tienen la misma raíz. La idea se remonta al algoritmo de equivalencia de Galler y Fischer de 1964. Y en el procesamiento de imágenes, donde el «grafo» es una cuadrícula de píxeles, el mismo problema se llama etiquetado de componentes conexas. Rosenfeld y Pfaltz describieron un barrido secuencial para ello en 1966. Que cuenten los vecinos diagonales, lo que se llama 8-conectividad, o solo los cuatro vecinos rectos, lo que se llama 4-conectividad, cambia qué formas son una sola región y cuáles son dos.

Incluso hay una respuesta algebraica. La matriz laplaciana de un grafo, con los grados en la diagonal y −1 por cada arista, tiene el valor propio 0 con multiplicidad exactamente igual al número de componentes. En el ejemplo esa multiplicidad es 2. La relación entre valores propios y estructura se desarrolla en la teoría espectral de grafos.

3. Lo que dice el número de componentes

Llama n al número de vértices, m al número de aristas y k al número de componentes. Unos pocos hechos relacionan los tres, y sirven como comprobaciones de cordura para cualquier programa que cuente componentes.

Un grafo con n vértices y k componentes tiene al menos n − k aristas, con igualdad exactamente cuando es un bosque.

La demostración es un argumento de conteo. Parte de n vértices aislados, que son n componentes, y añade las aristas una a una. Cada arista o bien une dos componentes distintas, lo que reduce la cuenta en uno, o bien cae dentro de una componente y no cambia nada. Para bajar a k componentes necesitas al menos n − k aristas del primer tipo, y tienes exactamente esas cuando ninguna arista se desperdició en cerrar un ciclo. Un bosque es precisamente un grafo sin ciclos, y un árbol es un bosque conexo, por eso un árbol con n vértices tiene n − 1 aristas, como la guía de árboles en teoría de grafos demuestra de varias otras formas. El ejemplo cumple 13 ≥ 12 − 2 = 10, con tres aristas de sobra, una por cada uno de sus tres ciclos.

La otra dirección también tiene un techo. Un grafo simple con k componentes tiene como mucho C(n − k + 1, 2) aristas, cota que se alcanza poniendo n − k + 1 vértices en un grafo completo y dejando aislados los otros k − 1. Un corolario es una prueba rápida de conectividad: un grafo simple con más de C(n − 1, 2) aristas no puede tener dos componentes, así que debe ser conexo.

Otro hecho es un ejercicio clásico con una demostración de dos líneas: un grafo o su complemento siempre es conexo. Si G es disconexo, toma dos vértices cualesquiera. Si están en componentes distintas de G, son adyacentes en el complemento. Si están en la misma componente, elige cualquier vértice de otra componente; es adyacente a ambos en el complemento. En cualquier caso quedan unidos por un camino de longitud como mucho dos. Estos tres hechos se comprobaron por fuerza bruta sobre todos los grafos simples de hasta seis vértices.

4. Puentes: las aristas que no puedes perder

La conectividad no trata solo de si un grafo se mantiene unido, sino de con qué firmeza. Un puente, también llamado arista de corte, es una arista cuya eliminación aumenta el número de componentes. Borrarla divide su componente en exactamente dos piezas, nunca más, porque quitar una arista solo puede separar entre sí a sus dos extremos.

Una arista es un puente si y solo si no está en ningún ciclo.

Si una arista uv está en un ciclo, el resto del ciclo es una segunda ruta de u a v, así que quitar la arista no desconecta nada. A la inversa, si al quitar uv quedan u y v conectados, el camino restante de v de vuelta a u junto con uv forma un ciclo. Así que los puentes son exactamente las aristas sin ruta alternativa. Se siguen dos consecuencias inmediatas: en un árbol cada arista es un puente, y una arista entre dos vértices unidos por una segunda arista paralela nunca es un puente.

El ejemplo tiene tres puentes: E–F, I–J y K–L. Quitar cualquiera de ellos eleva el número de componentes de 2 a 3. Todas las demás aristas están en uno de los tres ciclos: los dos triángulos y el cuadrado.

5. Puntos de articulación: los vértices que no puedes perder

Un punto de articulación, también llamado vértice de corte, es un vértice cuya eliminación, junto con sus aristas, aumenta el número de componentes. De forma equivalente, v es un vértice de corte cuando hay otros dos vértices u y w en su componente tales que todo camino de u a w pasa por v.

A diferencia de un puente, un vértice de corte puede dividir su componente en muchas piezas a la vez. Quita el centro de una estrella con cinco hojas y quedan cinco componentes. En el ejemplo, al quitar C quedan tres componentes: {A, B}, todo lo que va de D a J, y {K, L}, que ya estaba separada.

Los puentes y los vértices de corte están relacionados, y la relación es una trampa que conviene enunciar con cuidado:

• Un extremo de un puente es un vértice de corte salvo que tenga grado 1. Quita E y el puente desaparece con él, separando el lado de F del lado de D. Por eso E, F e I son vértices de corte.
• Un puente no necesita tener un vértice de corte en ninguno de sus extremos. K–L es un puente, pero ambos extremos tienen grado 1, y quitar una hoja nunca desconecta nada.
• Un vértice de corte no necesita tocar ningún puente. C une dos triángulos, una figura que suele llamarse pajarita. Cada arista en C está en un triángulo, así que ninguna es un puente, y sin embargo quitar C separa A y B del resto.

Así que el ejemplo tiene cuatro vértices de corte, C, E, F e I, y las dos ideas son realmente distintas: los fallos de vértices y los fallos de enlaces revelan puntos débiles diferentes en la misma red.

6. Una búsqueda en profundidad encuentra ambos

El algoritmo obvio borra cada arista, o cada vértice, por turno y vuelve a contar las componentes. Eso cuesta una búsqueda completa por candidato, O(E(V + E)) para los puentes. En 1972 y 1973, Tarjan, y Hopcroft y Tarjan, demostraron que basta con una sola búsqueda en profundidad, con un coste de O(V + E) en total. El método se basa en dos números por vértice.

• disc[v] es el instante en que la búsqueda alcanza por primera vez v: 0 para el primer vértice, 1 para el siguiente, y así sucesivamente.
• low[v] es el menor tiempo de descubrimiento que se puede alcanzar desde el subárbol de v bajando por aristas de árbol y tomando después como mucho una arista de retroceso.

En una búsqueda en profundidad no dirigida, toda arista que no es de árbol es una arista de retroceso: une un vértice con uno de sus antepasados. Una arista de retroceso es una vía de escape, una forma de salir de un subárbol sin usar la arista de árbol que tiene encima. Ambas pruebas preguntan si existe tal vía. Para una arista de árbol del padre u al hijo v:

puente             u–v es un puente                si  low[v] > disc[u]    nada bajo v llega a u ni más arriba
vértice de corte   u es un vértice de corte        si  low[v] ≥ disc[u]    nada bajo v llega por encima de u
raíz               la raíz es un vértice de corte  si tiene 2 o más hijos en el árbol DFS

La raíz necesita su propia regla porque no hay nada por encima de ella: separa el grafo exactamente cuando la búsqueda tuvo que salir de ella dos veces, lo que significa que sus subárboles no tienen ninguna arista entre sí. Este es el método completo, escrito de forma iterativa para que un camino largo no desborde la pila de llamadas de Python:

def bridges_and_cut_vertices(vertices, edges):
    """Método low-link de Tarjan, iterativo. Las aristas son pares (u, v); se permiten aristas paralelas."""
    adj = {v: [] for v in vertices}
    for i, (u, v) in enumerate(edges):       # guarda los ids de las aristas, no solo los vecinos
        adj[u].append((v, i))
        adj[v].append((u, i))
    disc, low, bridges, cuts, clock = {}, {}, [], set(), 0
    for root in vertices:
        if root in disc:
            continue
        disc[root] = low[root] = clock; clock += 1
        children = 0
        stack = [(root, -1, iter(adj[root]))]  # (vértice, id de la arista por la que llegamos, vecinos)
        while stack:
            u, in_edge, it = stack[-1]
            for v, i in it:
                if i == in_edge:             # salta solo esa arista, no todas las que vuelven al padre
                    continue
                if v in disc:                # arista de retroceso: una vía de escape hacia arriba en el árbol
                    low[u] = min(low[u], disc[v])
                else:                        # arista de árbol: descender
                    disc[v] = low[v] = clock; clock += 1
                    stack.append((v, i, iter(adj[v])))
                    break
            else:                            # u ha terminado: informa a su padre p
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    low[p] = min(low[p], low[u])
                    if low[u] > disc[p]:
                        bridges.append(edges[in_edge])
                    if low[u] >= disc[p] and p != root:
                        cuts.add(p)
                    if p == root:
                        children += 1
        if children >= 2:                    # la raíz es vértice de corte solo con 2+ hijos DFS
            cuts.add(root)
    return bridges, sorted(cuts), disc, low

edges = ['AB', 'BC', 'CA', 'CD', 'DE', 'EC', 'EF', 'FG', 'GH', 'HI', 'IF', 'IJ', 'KL']
bridges, cuts, disc, low = bridges_and_cut_vertices('ABCDEFGHIJKL', edges)
print(bridges)
# ['IJ', 'EF', 'KL']
print(cuts)
# ['C', 'E', 'F', 'I']

print(bridges_and_cut_vertices('xy', ['xy', 'xy'])[0])   # una arista doble no es un puente
# []

En el ejemplo, la búsqueda desde A recorre por casualidad un camino recto, A, B, C, …, J, y las tres aristas que no son de árbol C–A, E–C y I–F se convierten en aristas de retroceso. La figura muestra los números resultantes.

Leer la tabla con las reglas da todas las respuestas. low[F] = 5 es mayor que disc[E] = 4, así que nada por debajo de F vuelve a subir hasta E, y E–F es un puente; I–J es un puente por la misma razón, con 9 > 8. low[D] = 2 es igual a disc[C] = 2: el subárbol bajo C puede volver a subir hasta el propio C, pero no más arriba, así que C es un vértice de corte aunque ningún puente lo toque. Y A, la raíz, tiene un solo hijo, así que no lo es.

7. Dos errores que superan las pruebas sencillas

El código low-link es corto, y dos de sus errores clásicos dan respuestas correctas en la mayoría de los ejemplos pequeños. Ambos se compararon con la fuerza bruta: la versión de arriba coincide con «bórralo y vuelve a contar» en 5.000 multigrafos aleatorios.

Saltar el vértice padre en lugar de la arista padre. Cuando la búsqueda examina los vecinos de v, no debe tratar la arista de árbol por la que llegó como una arista de retroceso, o cada vértice podría escapar a través de su propio padre. Muchas implementaciones saltan «el vecino igual a mi padre». Eso funciona en un grafo simple, pero con dos aristas paralelas entre x y y salta las dos, y la arista doble aparece como puente aunque borrar una copia no desconecte nada. Saltar esa única arista por su identidad, como hace el código con in_edge, es correcto para los multigrafos también.

Usar low[w] en lugar de disc[w] en una arista de retroceso. La actualización a lo largo de una arista de retroceso hacia w debe usar disc[w]. Escribir low[w] permite que la vía de escape continúe más allá de w por aristas que pertenecen a otro bloque. Para los puentes esto resulta inofensivo: en 20.000 grafos aleatorios la variante nunca falló un puente. Para los vértices de corte no lo es: la misma prueba lo detectó en 35 de los grafos, y el fallo más pequeño que encontró esa búsqueda es el par de triángulos que comparten C. Con low[w], la arista de retroceso E–C importa low[C] = 0, así que low[D] pasa a valer 0, la prueba en C falla y el vértice de corte desaparece de la salida.

8. Bloques y el árbol de bloques y vértices de corte

Los vértices de corte dividen un grafo conexo en piezas naturales. Un bloque es un subgrafo conexo maximal sin vértices de corte propios: o bien una pieza 2-conexa (que sigue siendo conexa tras borrar cualquier vértice), o bien un solo puente, o bien un vértice aislado. Cada arista pertenece a exactamente un bloque, y dos bloques comparten como mucho un vértice, que entonces es un vértice de corte. Los bloques también se llaman componentes biconexas, y el algoritmo de Hopcroft y Tarjan de 1973 los encuentra en esa misma búsqueda, manteniendo una pila de aristas y sacando un bloque cada vez que se cumple la prueba del vértice de corte.

El ejemplo tiene seis bloques: los triángulos {A, B, C} y {C, D, E}, el cuadrado {F, G, H, I} y los tres puentes {E, F}, {I, J} y {K, L}.

El árbol de bloques y vértices de corte, introducido por Harary y Prins en 1966, tiene un nodo por cada bloque y otro por cada vértice de corte, con una arista siempre que el vértice de corte está en el bloque. Para un grafo conexo siempre es un árbol. Para la componente 1 tiene 5 nodos de bloque y 4 nodos de vértice de corte: 9 nodos unidos por 8 aristas. El árbol es el esqueleto grueso del grafo: responde a «qué fallos separan qué partes» sin mirar dentro de ningún bloque.

Los puentes dan una descomposición paralela. Borra todos los puentes, y lo que queda se divide en componentes 2-conexas por aristas, piezas que sobreviven a la pérdida de cualquier arista. El ejemplo tiene cinco: {A, B, C, D, E}, {F, G, H, I} y los vértices sueltos {J}, {K} y {L}. Observa que la primera es una sola componente 2-conexa por aristas pero dos bloques. La pajarita sobrevive al fallo de cualquier arista, pero no al fallo de C.

Dos teoremas clásicos explican lo que aporta realmente «no tener vértices de corte». Whitney demostró en 1932 que un grafo con al menos tres vértices es 2-conexo exactamente cuando cada par de vértices está unido por dos caminos sin vértices interiores en común, lo que equivale a decir que cada par de vértices está en un ciclo común. Y Robbins demostró en 1939 que a las aristas de un grafo conexo se les pueden dar direcciones de modo que cada vértice alcance a todos los demás exactamente cuando el grafo no tiene puentes, el teorema central de la guía de grafos dirigidos y no dirigidos.

9. Medir cuán conexo es un grafo

Los puentes y los vértices de corte son el primer peldaño de una escalera. La conectividad por vértices κ(G) es el menor número de vértices cuya eliminación desconecta el grafo o deja un solo vértice. La conectividad por aristas λ(G) es el menor número de aristas cuya eliminación lo desconecta. Un grafo conexo con al menos tres vértices tiene un vértice de corte exactamente cuando κ = 1, y un grafo conexo con al menos dos vértices tiene un puente exactamente cuando λ = 1. La desigualdad de Whitney de 1932 relaciona ambas con el grado mínimo δ(G):

κ(G)  ≤  λ(G)  ≤  δ(G)

dos triángulos que comparten C   κ = 1   λ = 2   δ = 2      un vértice de corte, pero ningún puente
componente 1 del ejemplo         κ = 1   λ = 1   δ = 1      J cuelga de una sola arista
cualquier ciclo                  κ = 2   λ = 2   δ = 2

La desigualdad de la derecha es fácil: borrar las aristas de un vértice de grado mínimo lo aísla. La de la izquierda dice que los fallos de vértices son siempre al menos tan peligrosos como los fallos de aristas, y la pajarita muestra que la diferencia puede ser real.

El teorema de Menger de 1927 convierte estos mínimos en máximos. El menor número de aristas cuya eliminación separa dos vértices u y v es igual al mayor número de caminos de u a v que no comparten ninguna arista. La versión para vértices es el mismo enunciado con caminos internamente disjuntos, y requiere que u y v no sean adyacentes, ya que ningún conjunto de otros vértices separa a dos vecinos. El teorema de Menger es un caso particular de flujo máximo igual a corte mínimo, que es también como se calcula la conectividad en la práctica.

10. Dónde importa esto

Las componentes, los puentes y los vértices de corte son el vocabulario del análisis de fallos. Siempre que un sistema pueda modelarse como cosas y enlaces, estos conceptos nombran sus puntos débiles.

Las componentes también explican uno de los resultados más famosos sobre grafos aleatorios. Erdős y Rényi demostraron en 1960 que si añades aristas aleatorias a n vértices aislados, las componentes siguen siendo pequeñas hasta que el grado medio supera 1, y entonces, de forma bastante repentina, aparece una única componente gigante que contiene una fracción constante de todos los vértices. Esa transición de fase, tratada en la historia de la teoría de grafos, es la razón por la que las grandes redes reales casi siempre tienen una componente dominante rodeada de unas cuantas pequeñas dispersas.

Cuando el grafo cambia sin parar, la conectividad se convierte en un problema de estructuras de datos. Las inserciones por sí solas son fáciles con union-find. Las eliminaciones son mucho más difíciles, porque quitar una arista puede dividir o no una componente y averiguarlo parece requerir una búsqueda. Holm, de Lichtenberg y Thorup demostraron en 2001 que la conectividad, la 2-conectividad por aristas y la biconectividad pueden mantenerse bajo inserciones y eliminaciones en un tiempo amortizado polilogarítmico por actualización.

11. Grafos dirigidos: conectividad débil y fuerte

En un grafo dirigido, «u puede alcanzar a v» ya no es una relación simétrica, así que no es de equivalencia, y «la componente de v» exige elegir. Hay dos opciones estándar.

• Las componentes débilmente conexas ignoran la dirección: son las componentes del grafo no dirigido subyacente, y todo lo que dice este artículo se aplica a ellas sin cambios.
• Las componentes fuertemente conexas exigen alcanzabilidad en ambos sentidos. «u alcanza a v y v alcanza a u» vuelve a ser una relación de equivalencia, y sus clases son las componentes fuertes, que se encuentran en tiempo lineal con el algoritmo de Tarjan o el de Kosaraju, como explica la guía de componentes fuertemente conexas paso a paso.

Ejecutar el código de componentes no dirigido sobre una lista de adyacencia dirigida no da ninguna de las dos respuestas. Solo sigue las aristas hacia delante, así que las «componentes» que devuelve dependen de dónde empezó cada búsqueda. O simetrizas primero las listas para obtener las componentes débiles, o usas un algoritmo de componentes fuertes.

12. Errores comunes

13. Glosario

15. Referencias

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

1. Menger, K. (1927). "Zur allgemeinen Kurventheorie." Fundamenta Mathematicae 10, 96 a 115. Caminos disjuntos y conjuntos separadores.
2. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1), 150 a 168.
3. Whitney, H. (1932). "Non-separable and Planar Graphs." Transactions of the American Mathematical Society 34(2), 339 a 362. Junto con el artículo anterior, la desigualdad entre la conectividad por vértices, la conectividad por aristas y el grado mínimo, y la caracterización de los grafos 2-conexos mediante caminos disjuntos.
4. 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.
5. Erdős, P. y Rényi, A. (1960). "On the Evolution of Random Graphs." Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, 17 a 61. La componente gigante.
6. Galler, B. A. y Fischer, M. J. (1964). "An Improved Equivalence Algorithm." Communications of the ACM 7(5), 301 a 303. La idea de union-find para fusionar clases.
7. Harary, F. y Prins, G. (1966). "The Block-Cutpoint-Tree of a Graph." Publicationes Mathematicae Debrecen 13, 103 a 107.
8. Rosenfeld, A. y Pfaltz, J. L. (1966). "Sequential Operations in Digital Picture Processing." Journal of the ACM 13(4), 471 a 494. Etiquetado de componentes conexas en imágenes.
9. Tarjan, R. E. (1972). "Depth-First Search and Linear Graph Algorithms." SIAM Journal on Computing 1(2), 146 a 160.
10. Hopcroft, J. E. y Tarjan, R. E. (1973). "Algorithm 447: Efficient Algorithms for Graph Manipulation." Communications of the ACM 16(6), 372 a 378. Componentes biconexas y vértices de corte en tiempo lineal.
11. Tarjan, R. E. (1974). "A Note on Finding the Bridges of a Graph." Information Processing Letters 2(6), 160 a 161.
12. Holm, J., de Lichtenberg, K. y Thorup, M. (2001). "Poly-logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity." Journal of the ACM 48(4), 723 a 760.
13. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer.