Tema 6: Cálculo de componentes conexas (Sesión 30/11/2010)

CÁLCULO DE COMPONENTES CONEXAS

Existen 2 métodos para calcular las componentes conexas de un grafo dirigido:

MÉTODO 1

Paso 1 – Escogemos un vértice cualquiera, podemos empezar por el 1.

Paso 2 – Vemos donde interseccionan R(v1) con Q(v1), es decir, si por ejemplo tenemos una matriz de accesibilidad, vamos a la fila 1, osea R(v1), y la trasponemos para ver donde coinciden los “1” con la columna 1. Obtenemos la primera componente conexa.

Paso 3 – Descartamos los vértices anteriores que ya forman parte de la primera CC y vamos con los restantes, cogiendo uno de ellos y haciendo lo mismo que antes.

Siguiendo estos pasos llegamos a obtener la distintas CC.

Por ejemplo, a partir de la siguiente matriz de accesibilidad:

1. Escogemos el vértice 1 y hacemos:

R(v1) [1 1 1 0 1 1] ∩ Q(v1) [1 0 0 1 0 0] –> v1

CC1= v1

2. De los vértices restantes podemos escoger el 2:

R(v2) [0 1 1 0 1 1] ∩ Q(v2) [1 1 0 1 0 0] –> v2

CC2= v2

3. Ahora con el vértice 3:

R(v3) [0 0 1 0 1 1] ∩ Q(v3) [1 1 1 1 1 1] –> v3, v5, v6

CC3= v3, v5, v6

4. Ya solo nos queda el vértice 4, ya que el 5 y 6 ya pertenecen a una CC, pero vamos a comprobarlo igualmente:

R(v4) [1 1 1 1 1 1] ∩ Q(v4) [0 0 0 1 0 0] –> v4

CC4= v4

5. Por lo que ya tenemos las 4 componentes conexas que forman parte del grafo:

CC = {v1}, {v2}, {v3, v5, v6}, {v4}.

MÉTODO 2

Este método es mas simple, solo debemos multiplicar la matriz de accesibilidad por la de acceso (R x Q) y en la matriz resultante tendremos “1” en la fila i para la componente conexa de Xi.

Usando la matriz R del ejemplo anterior, obtenemos Q, es decir, su traspuesta, las multiplicamos y obtenemos la siguiente matriz:

Si nos fijamos en las filas, podemos distinguir 4 CC distintas:

Fila 1 -> v1

Fila 2 -> v2

Filas 3, 5 y 6 -> v3, v5, v6

Fila 4 -> v4

Para el caso de grafos no dirigidos es obvio que para calcular la componente conexa a la que pertenece un vértice basta con encontrar los vértices a los que puede alcanzar (o los que le pueden alcanzar a él), sea cual sea la longitud del camino. El conjunto de vértices que se pueden alcanzar entre si formaran parte de la misma CC.