Diferencia entre revisiones de «Componente fuertemente conexo»
m Revertidos los cambios de 181.29.6.11 (disc.) a la última edición de Semibot |
La palabra "máximo" (el más grande) no era correcta. La palabra corrrecta es "maximal" (que no se puede agrandar). |
||
| Línea 1: | Línea 1: | ||
[[Archivo:Scc.png|thumb|Un grafo dirigido, y sus componentes fuertemente conexos.]] |
[[Archivo:Scc.png|thumb|Un grafo dirigido, y sus componentes fuertemente conexos.]] |
||
En la '''[[Teoría de los grafos|Teoría de grafos]]''', un [[grafo]] [[grafo#Grafo dirigido|dirigido]] es llamado '''fuertemente conexo''' si para cada par de [[Grafo#Vértice|vértices]] ''u'' y ''v'' existe un [[Grafo#Camino|camino]] de ''u'' hacia ''v'' y un camino de ''v'' hacia ''u''. Los '''componentes fuertemente conexos''' ('''CFC''') de un [[Grafo#grafo dirigido|grafo dirigido]] son sus subgrafos |
En la '''[[Teoría de los grafos|Teoría de grafos]]''', un [[grafo]] [[grafo#Grafo dirigido|dirigido]] es llamado '''fuertemente conexo''' si para cada par de [[Grafo#Vértice|vértices]] ''u'' y ''v'' existe un [[Grafo#Camino|camino]] de ''u'' hacia ''v'' y un camino de ''v'' hacia ''u''. Los '''componentes fuertemente conexos''' ('''CFC''') de un [[Grafo#grafo dirigido|grafo dirigido]] son sus subgrafos maximales fuertemente conexos. Estos subgrafos forman una [[Partición (matemáticas)|partición]] del grafo. |
||
Un subgrafo fuertemente conexo es |
Un subgrafo fuertemente conexo es maximal si contiene todos los vértices del grafo o si al agregarle un vértice cualquiera deja de ser fuertemente conexo. |
||
El cálculo de los componentes fuertemente conexos de un [[grafo]] es uno de los problemas fundamentales de la [[Teoría de los grafos]]. El primer algoritmo que trabaja en [[tiempo lineal]] para resolver este problema fue propuesto por [[Robert Tarjan]]<ref>R.E. Tarjan, ''Depth-First search and linear graph algorithms,'' SIAM J. Comp. 1 (1972) 146-60.</ref> en [[1970]] a base de una [[búsqueda en profundidad]] (depth-first search). Otros algoritmos aparecen en los principales textos sobre [[algorítmica]].<ref>A.V. Aho, J.E. Hopcroft, J.D. Ullman, ''Data Structures ans Algorithms,'' Addison-Wesley, MA, 1983.</ref><ref>T.H. Cormen, C.E. Leiserson, R.L. Rivest, ''Introduction to Algorithms,'' [[MIT Press]], Cambridge, MA, 1990.</ref> |
El cálculo de los componentes fuertemente conexos de un [[grafo]] es uno de los problemas fundamentales de la [[Teoría de los grafos]]. El primer algoritmo que trabaja en [[tiempo lineal]] para resolver este problema fue propuesto por [[Robert Tarjan]]<ref>R.E. Tarjan, ''Depth-First search and linear graph algorithms,'' SIAM J. Comp. 1 (1972) 146-60.</ref> en [[1970]] a base de una [[búsqueda en profundidad]] (depth-first search). Otros algoritmos aparecen en los principales textos sobre [[algorítmica]].<ref>A.V. Aho, J.E. Hopcroft, J.D. Ullman, ''Data Structures ans Algorithms,'' Addison-Wesley, MA, 1983.</ref><ref>T.H. Cormen, C.E. Leiserson, R.L. Rivest, ''Introduction to Algorithms,'' [[MIT Press]], Cambridge, MA, 1990.</ref> |
||
Revisión del 11:45 6 sep 2017
En la Teoría de grafos, un grafo dirigido es llamado fuertemente conexo si para cada par de vértices u y v existe un camino de u hacia v y un camino de v hacia u. Los componentes fuertemente conexos (CFC) de un grafo dirigido son sus subgrafos maximales fuertemente conexos. Estos subgrafos forman una partición del grafo.
Un subgrafo fuertemente conexo es maximal si contiene todos los vértices del grafo o si al agregarle un vértice cualquiera deja de ser fuertemente conexo.
El cálculo de los componentes fuertemente conexos de un grafo es uno de los problemas fundamentales de la Teoría de los grafos. El primer algoritmo que trabaja en tiempo lineal para resolver este problema fue propuesto por Robert Tarjan[1] en 1970 a base de una búsqueda en profundidad (depth-first search). Otros algoritmos aparecen en los principales textos sobre algorítmica.[2][3]
La complejidad de este algoritmo es O(V+E).
Algoritmo
Sea un grafo dirigido:
- Aplicar búsqueda en profundidad sobre G
- Calcular el grafo traspuesto.
- Aplicar búsqueda en profundidad sobre (el grafo traspuesto) iniciando la búsqueda en los nodos de mayor a menor tiempo de finalización obtenidos en la primera ejecución de búsqueda en profundidad (paso 1)
- El resultado será un bosque de árboles. Cada árbol es un componente fuertemente conexo.
Las dos búsquedas en profundidad y la construcción del grafo reverso consumen tiempo lineal, de manera que el tiempo total es también lineal. En 2002, se publicó[4] una prueba simplificada de corrección de este algorítmo.
Referencias
- ↑ R.E. Tarjan, Depth-First search and linear graph algorithms, SIAM J. Comp. 1 (1972) 146-60.
- ↑ A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data Structures ans Algorithms, Addison-Wesley, MA, 1983.
- ↑ T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990.
- ↑ I. Wegener, A simplified correctness proof for a well-known algorithm computing strongly connected components, Information Processing Letters, 83 (2002) 17-19.