Composante fortement connexe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Décomposition d'un graphe en composantes fortement connexes

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 sommets 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 disjointes.

Graphe des composantes[modifier | modifier le code]

À partir d'un graphe orienté G, le graphe G’ des composantes de G est défini de la manière suivante :

  • les sommets de G’ sont les composantes fortement connexes de G ;
  • pour toute arête (u, v) de G telle que u et v sont dans deux composantes distinctes U et V, on ajoute une arête de U à V dans G’.

Le graphe des composantes est toujours acyclique. Inversement, tout graphe acyclique est égal au graphe de ses composantes.

Algorithmes[modifier | modifier le code]

Plusieurs algorithmes permettent de calculer la décomposition en composantes fortement connexes d'un graphe en temps linéaire :

Bibliographie[modifier | modifier le code]

Harold N. Gabow, « Path-based depth-first search for strong and biconnected components », Inf. Process. Lett., vol. 74,‎ 2000, p. 107-114

Notes et références[modifier | modifier le code]

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l’algorithmique, Dunod,‎ 2002, 2e éd., 1146 p. [détail de l’édition] (ISBN 2-10-003922-9), notes du chapitre 22.

Voir aussi[modifier | modifier le code]