Componente fuertemente conectado

Un grafo dirigido (dígrafo) se dice fuertemente conexo si dos de sus vértices s y t están fuertemente conexos, es decir, si hay un camino dirigido de a  y un camino dirigido simultáneamente de a

Los componentes fuertemente conectados de un dígrafo son sus subgrafos fuertemente conectados de máxima inclusión. Una región fuertemente conectada es un conjunto de vértices de componentes fuertemente conectados.

Definiciones

Un dígrafo que no pertenece a la clase de gráficos fuertemente conectados contiene algún conjunto de componentes fuertemente conectados y algún conjunto de aristas dirigidas que van de un componente a otro.

Cualquier vértice de un dígrafo está fuertemente conectado consigo mismo.

Algoritmos

El algoritmo más simple para resolver el problema de encontrar componentes fuertemente conectados en un dígrafo funciona de la siguiente manera:

  1. Usando el cierre transitivo , verificamos si es accesible desde y para todos los pares y
  2. Luego definimos tal gráfico no dirigido , que contiene una arista para cada par.
  3. La búsqueda de componentes conectados de tal gráfico no dirigido produce componentes fuertemente conectados del dígrafo.

Obviamente, el principal tiempo de ejecución de este algoritmo lo ocupa un cierre transitivo.

También hay tres algoritmos que resuelven este problema en tiempo lineal, es decir, V veces más rápido que el algoritmo anterior. Estos son los algoritmos de Kosaraju , búsqueda de componentes fuertemente conectados con dos pilas , y Tarjan .

Ejemplo

La figura muestra un dígrafo para el cual se muestran los tres componentes fuertemente conectados (áreas sombreadas delineadas por una línea de puntos).

Véase también

Literatura