Componentes fuertemente conexas

Guillermo Palma

Universidad Simón Bolı́var

Departamento de Computación y Tecnologı́a de la Información

Plan

1. Preliminares

2. Componentes fuertemente conexas

Guillermo Palma Componentes fuertemente conexas 1 / 26

 Preliminares

Digrafo inverso

Definición de digrafo inverso

Un digrafo inverso, que denotamos como G −1 , es un digrafo que se
obtiene de cambiar la dirección de los arcos de un digrafo G .

Guillermo Palma Componentes fuertemente conexas 2 / 26

Ejemplo de un digrafo inverso

4
1 2 3

(a) Digrafo acı́clico G

1 2 3
4

(b) Digrafo acı́clico G −1 de G

Figura 1: Ejemplo de un digrafo acı́clico y su digrafo inverso

Guillermo Palma Componentes fuertemente conexas 3 / 26

Algoritmo para obtener el digrafo inverso

Función grafo-inverso(G (V , E ))
1 inicio
2 G −1 ; /* Digrafo como lista de adyacencias */
3 G −1 .adyacentes[|V |] ; /* Se crea un arreglo de listas */
4 para i ← 0 a |V | − 1 hacer
5 G −1 .adyacentes[i] ← new Lista ; /* Se crean listas */
6 para cada u ∈ V hacer
7 para cada v ∈ G .adyacentes[u] hacer
8 G −1 .adyacentes[v ].agregar (u) ; /* Nuevo arco */

9 devolver G −1

Guillermo Palma Componentes fuertemente conexas 4 / 26

Análisis del tiempo del algoritmo grafo-inverso

ˆ Creación de listas de adyacencias (lı́neas 4-5) es Θ(|V |).

ˆ Las lı́neas 6-8 se ejecutan para todos los arcos, entonces es Θ(|E |).
ˆ Por lo tanto, el tiempo del peor caso es Θ(|V | + |E |).

Guillermo Palma Componentes fuertemente conexas 5 / 26

Componente fuertemente conexas

Definición componente fuertemente conexas

Una componente fuertemente conexa (CFC) de un digrafo es el
subconjunto máximo de vértices C ⊆ V , tal que para todo par de
vértices u, v ∈ C se cumple que “el vértice u es alcanzable desde v y el
vértice v es alcanzable desde u”.

Guillermo Palma Componentes fuertemente conexas 6 / 26

Ejemplo de componentes fuertemente conexas

a b c d

e f g h
Figura 2: Grafo no dirigido con cuatro componentes fuertemente conexas
{a, b, e}, {c, d}, {f , g } y {h}. Fuente: [1]

Guillermo Palma Componentes fuertemente conexas 7 / 26

Grafo componente

Definición grafo componente

Sea G un grafo con las componentes conexas C1 , C2 , . . . , Cn . Se define
el grafo componente G SCC = (V SCC , E SCC ), tal que cada vértice
vi ∈ V SCC corresponde a una componente conexa Ci de G y existe un
lado (vi , vj ) ∈ E SCC si en G existe un lado (a, b) tal que a ∈ Ci y
b ∈ Cj y Ci 6= Cj .

Guillermo Palma Componentes fuertemente conexas 8 / 26

Ejemplo de un grafo componente

a b c d

e f g h
(a) Grafo dirigido con 4 componentes fuertemente conexas.

cd

abe

fg h
(b) Grafo componente G SCC de G .

Figura 3: Ejemplo de un grafo componente G SCC derivado de G . Fuente: [1].

Guillermo Palma Componentes fuertemente conexas 9 / 26

Tiempo de descubrimiento y finalización de conj. de vértices

Definición de las funciones d y f para conjuntos de vértices

Sea un grafo G = (V , E ) al que se le aplica el algoritmo de búsqueda
en profundidad y sea U ⊆ V . Se definen:

d(U) = mı́n{u.d}
u∈U

y
f (U) = máx{u.f }
u∈U

Guillermo Palma Componentes fuertemente conexas 10 / 26

Corolario y teorema de DFS

Corolario anidamiento de intervalos de descendientes

Un vértice v es descendiente de un vértice u en un bosque generado por
la búsqueda en profundidad (DFS) en un grafo G , si solo si
u.d < v .d < v .f < u.f .

Teorema del camino blanco

En un bosque generado por la búsqueda en profundidad (DFS) en un
grafo G , un vértice v es descendiente de un vértice u si solo si existe en
el tiempo u.d en el que u es descubierto, un camino de vértices blancos
desde u hasta v .

Guillermo Palma Componentes fuertemente conexas 11 / 26

Componentes fuertemente
conexas
Algoritmo de las componentes fuertemente conexas

Función componentes-fuertemente-conexas(G (V , E ))
1 inicio
2 Ejecutar DFS(G ) y obtener el orden topológico de todos los
vértices ;
3 G −1 ← grafo-inverso(G ) ;
4 Ejecutar DFS(G −1 ) modificado, tal que considere en ciclo
principal DFS a los vértices en el orden topológico obtenido en la
lı́nea 2 ;
5 CFC ← Los vértices que componen cada árbol i del bosque de
DFS (depth-first trees) de la lı́nea 4 van a formar parte de la
componente fuertemente conexa Ci , se crea un conjunto con
todas las componentes fuertemente conexas Ci , esto es
{C1 , . . . Cn }. ;
6 devolver CFC ; /* Se tiene que CFC = {C1 , . . . Cn } */

Guillermo Palma Componentes fuertemente conexas 12 / 26

Análisis del algoritmo de las componentes fuertemente conexas

ˆ DFS y ordenamiento topológico en la lı́nea 2 es Θ(|V | + |E |).

ˆ Obtener grafo inverso en la lı́nea 3 es Θ(|V | + |E |).
ˆ DFS(G −1 ) modificado en la lı́nea 4 es O(|V | + |E |).
ˆ Recorrer el bosque de DFS en la lı́nea 5 es O(|V | + |E |).
ˆ Por lo tanto, el tiempo del peor caso es de Θ(|V | + |E |).

Guillermo Palma Componentes fuertemente conexas 13 / 26

Ejemplo de componentes-fuertemente-conexas

a b c d

e f g h
(a) Digrafo G con 4 componentes fuertemente conexas.
a b c d
13/14 11/16 1/10 8/9

12/15 3/4 2/7 5/6

e f g h
(b) Resultado de DFS(G ), con orden topológico
hb, e, a, c, d, g , h, f i.

Figura 4: Se ejecuta DFS(G ). Fuente: [1].

Guillermo Palma Componentes fuertemente conexas 14 / 26

Ejemplo de componentes-fuertemente-conexas, cont.

a b c d
13/14 11/16 1/10 8/9

12/15 3/4 2/7 5/6

e f g h
(a) Resultado de DFS(G ), con orden topológico
hb, e, a, c, d, g , h, f i.
a b c d

e f g h
(b) Grafo inverso G −1 de G .

Figura 5: Se ejecuta grafo-inverso(G ). Fuente: [1].

Guillermo Palma Componentes fuertemente conexas 15 / 26
Ejemplo de componentes-fuertemente-conexas, cont.

a b c d
13/14 11/16 1/10 8/9

12/15 3/4 2/7 5/6

e f g h
(a) Resultado de DFS(G ), con orden topológico
hb, e, a, c, d, g , h, f i.
a b c d

e f g h
(b) Resultado de DFS(G −1 ).

Figura 6: Se ejecuta DFS(G −1 ) con orden topológico 6(a). Fuente: [1]

Guillermo Palma Componentes fuertemente conexas 16 / 26

Ejemplo de componentes-fuertemente-conexas, cont.

a b c d

e f g h
(a) Resultado de DFS(G −1 ).

cd

abe

fg h
(b) Grafo componente con los vértices de las CFC obtenidas de
DFS(G −1 ) y los lados de G .
Figura 7: Componentes fuertemente conexas
CFC = {{a, b, e}, {c, d}, {f , g }, {h}} de 7(a). Fuente: [1]
Guillermo Palma Componentes fuertemente conexas 17 / 26
Caminos entre componentes fuertemente conexas

Lema 1
Sean C y C 0 dos componentes fuertemente conexas de un digrafo G ,
sean u, v ∈ C y u 0 , v 0 ∈ C 0 y suponga que en G existe el camino
u u 0 . Entonces G no puede tener un camino v 0 v.

Guillermo Palma Componentes fuertemente conexas 18 / 26

Caminos entre componentes fuertemente conexas, cont.

Prueba Lema 1
Por contradicción.

ˆ Supongamos que existe un camino v 0 v en G .

ˆ Entonces, existe un camino v 0 v u, porque u, v ∈ C .
ˆ En consecuencia, existe un camino u u0 v 0.
ˆ Entonces, u y v 0 están en la misma componente fuertemente conexa.
ˆ Esto es una contradicción porque u y v 0 están en componentes
fuertemente conexas diferentes.
ˆ Por lo tanto, no existe un camino v 0 v en G .

Guillermo Palma Componentes fuertemente conexas 19 / 26

Lados entre componentes fuertemente conexas

Lema 2
Sean C y C 0 dos componentes fuertemente conexas de un digrafo
G = (V , E ). Suponga que existe un lado (u, v ) ∈ E , donde u ∈ C y
v ∈ C 0 . Entonces f (C ) > f (C 0 ).

Guillermo Palma Componentes fuertemente conexas 20 / 26

Lados entre componentes fuertemente conexas, cont.

Prueba del Lema 2
Caso 1 d(C ) < d(C 0 ):

ˆ Sea x el primer vértice descubierto por DFS en C .

ˆ Los demás vértices de C son descendientes de x.
ˆ Por Teorema de camino blanco los demás vértices en C son blancos.
ˆ Por el lado (u, v ), para cualquier vértice w ∈ C 0 hay camino
x u→v w.
ˆ En consecuencia, los vértices de C 0 son descendientes de x.
ˆ Por Teorema de camino blanco los vértices en C 0 son blancos.
ˆ Por Corolario anidamiento de intervalos de descendientes ∀u ∈ C tal
que u 6= x se tiene que x.f > u.f .
ˆ Entonces, por definición de f se tiene que x.f = f (C ).
ˆ Por Corolario anidamiento de intervalos de descendientes
x.f = f (C ) > f (C 0 ).
Guillermo Palma Componentes fuertemente conexas 21 / 26
Lados entre componentes fuertemente conexas, cont.

Prueba del Lema 2, cont.

Caso 2 d(C ) > d(C 0 ):

ˆ Sea y el primer vértice descubierto por DFS en C 0 .

ˆ Los demás vértices en C 0 son descendientes de y .
ˆ Por Teorema de camino blanco los demás vértices en C 0 son blancos.
ˆ Por Corolario anidamiento de intervalos de descendientes ∀w ∈ C 0
tal que w 6= x se tiene que y .f > w .f .
ˆ Entonces, por definición de f se tiene que y .f = f (C 0 ).
ˆ En el momento y es descubierto, los vértices de C están blancos.
ˆ Por Lema 1 no hay camino desde y hasta cualquier vértice de C .
ˆ En consecuencia, los vértices de C son descubiertos después que C 0
es finalizado.
ˆ Por lo tanto, ∀w ∈ C : w .f > y .f implica que f (C ) > f (C 0 ).

Guillermo Palma Componentes fuertemente conexas 22 / 26

Tiempo de finalización en un digrafo inverso

Corolario 1
Sean C y C 0 dos componentes fuertemente conexas de un digrafo
G = (V , E ) y sea G −1 = (V , E −1 ) su digrafo inverso. Suponga que
existe un arco (u, v ) ∈ E −1 , donde u ∈ C y v ∈ C 0 . Entonces
f (C ) < f (C 0 ).

Prueba del Corolario 1

ˆ Como (u, v ) ∈ E −1 , entonces por definición de grafo inverso
(v , u) ∈ E .
ˆ Se tiene que v ∈ C 0 y u ∈ C porque las componentes fuertemente
conexas en G y G −1 son las mismas.
ˆ Entonces, aplicando el Lema 2 se tiene por lo tanto que
f (C 0 ) > f (C ).

Guillermo Palma Componentes fuertemente conexas 23 / 26

Correctitud de componentes-fuertemente-conexas

Teorema correctitud de componentes-fuertemente-conexas

El algoritmo componentes-fuertemente-conexas obtiene las
componentes fuertemente conexas del digrafo G que se le da como
entrada.

Prueba de correctitud componentes-fuertemente-conexas

ˆ Por inducción: sobre los árboles del bosque (depth-first trees)
generados por DFS(G −1 ) en la lı́nea 4.
ˆ H.I.: suponemos que los primeros k árboles del bosque de
DFS(G −1 ) corresponden a componentes fuertemente conexa.
ˆ Caso base: k = 0 se cumple.
ˆ Queremos probar: el árbol (k + 1) del bosque de DFS(G −1 )
corresponde a una componente fuertemente conexa.

Guillermo Palma Componentes fuertemente conexas 24 / 26

Correctitud de componentes-fuertemente-conexas, cont.

Prueba de correctitud componentes-fuertemente-conexas, cont.

ˆ Sea u la raı́z del árbol (k + 1) y sea C la CFC de u.
ˆ En la lı́nea 4, se escogieron las raı́ces de DFS(G −1 ), por lo tanto
u.f = f (C ) > f (C 0 ) para toda otra CFC C 0 visitada.
ˆ u es el primer vértice descubierto por DFS(G −1 ) y por H.I., por lo
tanto los vértices de C son blancos.
ˆ Por Teorema de camino blanco los demás vértices de C son
descendientes de u en el árbol (k + 1).
ˆ Por H.I. y por Corolario 1, para cualquier (w , v ) ∈ E −1 se tiene que
w pertenece a una de las CFC C 0 visitadas anteriormente y v ∈ C .
ˆ Entonces, todos los descendientes de u están en C cuando
DFS(G −1 ) genera el árbol (k + 1).
ˆ Por lo tanto, los vértices en el árbol (k + 1) corresponden a una CFC
de G −1 y G .

Guillermo Palma Componentes fuertemente conexas 25 / 26

Referencias

[1] T. Cormen, C. Leirserson, R. Rivest, and C. Stein.

Introduction to Algorithms.
McGraw Hill, 3ra edition, 2009.

Guillermo Palma Componentes fuertemente conexas 26 / 26