Algoritmos y Estructuras de Datos (VJ1215)

Si desde un vértice s se puede llegar hasta todos los demás vértices siguiendo los arcos de entrada (es decir, recorriendo el grafo en contradirección) entonces desde todos los vértices se puede llegar hasta s siguiendo los arcos de salida (es decir, recorriendo el grafo en la dirección indicada por los arcos).

Mira las páginas 42 y 41 de estas transparencias "Graphs" de Kevin Wayne.

Para comprobar que un grafo dirigido es fuertemente conexo, podemos elegir un vértice cualquiera s y comprobar si se cumplen dos cosas:

1. Que desde s se puede llegar hasta todos los demás vértices. Para ello, podemos hacer una búsqueda en anchura desde s siguiendo los arcos de salida (ejercicio 3.b).

2. Que desde todos los demás vértices se puede llegar hasta s. Para ello, podemos hacer una búsqueda en anchura desde s siguiendo los arcos de entrada.

Si una de ellas no se cumple, entonces podemos concluir que el grafo no es fuertemente conexo, obviamente. Si ambas se cumplen, entonces podemos concluir que el grafo es fuertemente conexo, porque desde cualquier vértice u se puede llegar hasta cualquier vértice v pasando por s, combinando ambos resultados.