Composante fortement connexe
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En théorie des graphes, une composante fortement connexe d'un graphe orienté G est un sous-graphe de G possédant la propriété suivante, et qui est maximal pour cette propriété : pour tout couple (u, v) de nœuds dans ce sous-graphe, il existe un chemin de u à v.
Un graphe est dit fortement connexe s'il est formé d'une seule composante fortement connexe. De manière générale, un graphe se décompose de manière unique comme union de composantes fortement connexes deux à deux disjointes.
Graphe des composantes fortement connexes
modifierLe graphe H des composantes fortement connexes de G est défini de la manière suivante :
- à chaque composante fortement connexe de G lui est associé un nœud de H;
- il existe un arc (U, V) de H si et seulement s'il existe un arc (u, v) de G tel que u et v sont des nœuds respectifs des composantes fortement connexes U et V.
Le graphe des composantes fortement connexes est un graphe orienté toujours acyclique. Inversement, tout graphe acyclique est isomorphe au graphe de ses composantes fortement connexes.
Algorithmes
modifierPlusieurs algorithmes permettent de calculer la décomposition en composantes fortement connexes d'un graphe en temps linéaire :
- l'algorithme de Kosaraju, fondé sur l'algorithme de parcours en profondeur, nécessite deux parcours du graphe (plus précisément, un parcours du graphe et un de son transposé) ;
- l'algorithme de Tarjan ne nécessite qu'un seul parcours en profondeur ;
- l'algorithme de Gabow (Gabow 2000)[1].
Utilisations
modifierCertains algorithmes utilisent la décomposition en composantes fortement connexes comme une première étape, c'est le cas par exemple d'un algorithme pour le problème 2-SAT[2].
Notes et références
modifier- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition], notes du chapitre 22.
- Bengt Aspvall, Michael F. Plass et Robert E. Tarjan, « A linear-time algorithm for testing the truth of certain quantified boolean formulas », Information Processing Letters, vol. 8, no 3, , p. 121-123 (DOI 10.1016/0020-0190(79)90002-4, lire en ligne).
Voir aussi
modifierBibliographie
modifier- (en) Harold N. Gabow, « Path-based depth-first search for strong and biconnected components », Inf. Process. Lett., vol. 74, nos 3-4, , p. 107-114
- Alain Bretto, Alain Faisant et François Hennecart, Éléments de théorie des graphes, Paris, Springer-Verlag France, coll. « IRIS », , xix + 371 (ISBN 978-2-8178-0280-0 et 978-2-8178-0281-7, zbMATH 1250.68002), Chapitre 1. « Concepts fondamentaux ».
Articles connexes
modifier- Graphe connexe, la notion équivalente à la forte connexité pour les graphes non orientés.
- Composante connexe (théorie des graphes)
- Orientation forte
- Théorème de Robbins
