Component fortament conexo
En teoria de grafos, un grafo dirigit és cridat fortament conexo si per a cada parell de vèrtiços o i v existix un camí de o cap a v i un camí de v cap a o. Els components fortament conexos (CFC) d'un grafo dirigit són els seus subgrafos maximales fortament conexos. Estos subgrafos formen una partició del grafo.
Un subgrafo fortament conexo és maximal si conté tots els vèrtiços del grafo o si en agregar-li un vèrtiç qualsevol deixa de ser fortament conexo.
El càlcul dels components fortament conexos d'un grafo és un dels problemes fonamentals de la Teoria dels grafos. El primer algoritme que treballa en temps llineal per a resoldre este problema va ser propost per Robert Tarjan[1] en 1970 a pur de una busca en profunditat (depth-first search). Atres algoritmes apareixen en els principals texts sobre algorítmica.[2][3]
La complexitat d'este algoritme és O(V+I).
Algoritme
[editar | editar còdic]Per a trobar els components fortament conexos es pot utilisar l'algoritme de Kosaraju el qual funciona de la següent forma:
Siga un grafo dirigit:
- Aplicar busca en profunditat sobre G
- Calcular el grafo trasponer.
- Aplicar busca en profunditat sobre (el grafo trasponer) iniciant la busca en els nodos de major a menor temps de finalisació obtinguts en la primera eixecució de busca en profunditat (pas 1)
- El resultat serà un bosc d'arbres. Cada arbre és un component fortament conexo.
Les dos busques en profunditat i la construcció del grafo revers consumixen temps llineal, de manera que el temps total és també llineal. En 2002, es va publicar[4] una prova simplificada de correcció d'este algoritme.
Vore també
[editar | editar còdic]Referències
[editar | editar còdic]- ↑ 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.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Componente fuertemente conexo» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.