Component fortament connex
En teoria de grafs, un graf dirigit és fortament connex si per a cada parell de vèrtexs u i v hi ha un camí de u cap a v i un camí de v cap a u. Els components fortament connexos (CFC) d'un graf dirigit són els seus subgrafs màxims fortament connexos. Aquests subgrafs formen una partició del graf.
Un subgraf fortament connex és màxim si conté tots els vèrtexs del graf o si en afegir-hi un vèrtex més del graf deixa de ser fortament connex.
El càlcul dels components fortament connexos d'un graf és un dels problemes fonamentals de la teoria dels grafs. El primer algorisme que treballa en temps lineal per a resoldre aquest problema va ser proposat per Robert Tarjan[1] el 1970 a base d'una cerca en profunditat (depth-first search). Altres algorismes apareixen en els principals textos d'algorísmica.[2][3]
La complexitat d'aquest algorisme és O (V+E).
Algorisme modifica
Sigui un graf dirigit:
- S'aplica la cerca en profunditat sobre G
- Es calcula el graf traslladat.
- S'aplica la cerca en profunditat sobre (el graf traslladat) iniciant la recerca en els nodes de major a menor temps de finalització obtinguts en la primera execució de cerca en profunditat (pas 1)
- El resultat serà un bosc d'arbres. Cada arbre és un component fortament connexa.
Les dues recerques en profunditat i la construcció del graf revers consumeixen temps lineal, de manera que el temps total és també lineal. El 2002 es va publicar una demostració de correcció d'aquest algorisme.[4]
Referències modifica
- ↑ RE Tarjan, Depth-First search and linear graph algorithms, SIAM J. Comp. 1 (1972) 146-60.
- ↑ AV Aho, J.E. Hopcroft, J.D. Ullman, Data Structures ans Algorithms, Addison-Wesley, MA, 1983.
- ↑ TH Corman, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990
- ↑ I. Wegener, A simplificat correctness proof for a well-known algorithm computing strongly connected components, Information Processing Letters, 83 (2002) 17-19.