Composante fortement connexe

Un article de Wikipédia, l'encyclopédie libre.
Ceci est la version actuelle de cette page, en date du 12 juillet 2019 à 09:22 et modifiée en dernier par Vivarés (discuter | contributions). L'URL présente est un lien permanent vers cette version.
(diff) ← Version précédente | Voir la version actuelle (diff) | Version suivante → (diff)
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 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 :

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]

  1. 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.
  2. 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

Articles connexes[modifier | modifier le code]