Composante fortement connexe — Wikipédia
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e1/Scc-1.svg/220px-Scc-1.svg.png)
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
[modifier | modifier le code]Le 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
[modifier | modifier le code]Plusieurs 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
[modifier | modifier le code]Certains 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 | modifier le code]- 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
[modifier | modifier le code]Bibliographie
[modifier | modifier le code]- (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 | modifier le code]- 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