Retour
Composante fortement connexe
Un graphe orienté est un ensemble de sommets reliés par des arcs dirigés, où chaque arc représente un chemin allant d'un sommet à un autre.
Dans un graphe orienté, un sous-graphe est fortement connexe si, pour chaque paire de sommets $u$ et $v$, il existe un chemin dirigé de $u$ à $v$ et de $v$ à $u$. Une composante fortement connexe (CFC) est un sous-graphe maximal vérifiant cette propriété.
Un graphe orienté peut contenir plusieurs CFC sans être lui-même fortement connexe. Un graphe fortement connexe est un graphe ne comportant qu'une seule CFC.
Algorithme de Kosaraju
L'algorithme de Kosaraju identifie les composantes fortement connexes d'un graphe orienté en trois étapes :
- Réalisation d'un premier parcours en profondeur pour déterminer l'ordre de sortie des sommets (post-ordre) qui est stocké dans une pile.
- Transposition du graphe en inversant tous les arcs.
- Réalisation d'un second parcours en profondeur sur le graphe transposé, en suivant l'ordre décroissant donné par la pile. Chaque composante trouvée correspond à une composante fortement connexe.
Complexité
L'algorithme de Kosaraju a une complexité en temps de $O(V+E)$, car chaque parcours en profondeur et la transposition sont linéaires par rapport au nombre de sommets $V$ et d'arcs $E$.
Lien avec le problème 2-SAT
Le problème 2-SAT consiste à décider si une formule booléenne, où chaque clause est une disjonction de deux littéraux, est satisfiable. Ce problème se résout grâce aux composantes fortement connexes.
En représentant les contraintes sous forme d'un graphe des implications, l'analyse des composantes permet de vérifier que chaque littéral et son complément ne sont pas dans la même composante fortement connexe, assurant ainsi la satisfiabilité.
Illustration
Soit la formule $(¬x∨y)∧(¬y∨z)∧(¬z∨x)$. Le graphe des implications montre que cette formule est satisfiable car les CFC ne contiennent pas un littéral et son complément simultanément.
