miniatura|Un graf dirigit, i els seus components fortament connexos. En teoria de grafs, un graf dirigit és fortament connex si per a cada parell de vèrtexs i hi ha un camí de cap a i un camí de cap a . 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 TarjanRE Tarjan, Depth-First search and linear graph algorithms, SIAM J. Comp. 1 (1972) 146-60. el 1970 a base d'una cerca en profunditat (depth-first search). Altres algorismes apareixen en els principals textos d'algorísmica.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
La complexitat d'aquest algorisme és .
Algorisme Sigui un graf dirigit: S'aplica la cerca en profunditat sobre 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 connex.
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.I. Wegener, A simplificat correctness proof for a well-known algorithm computing strongly connected components, Information Processing Letters, 83 (2002) 17-19.
Referències
Categoria:Teoria de grafs