Forte connexité

Contrairement à la notion de connexité, celle de forte connexité n'est disponible que sur les réseaux orientés.

Autrement dit, dans un graphe fortement connexe, depuis un sommet, il est toujours possible de trouver un chemin aller retour vers chaque autre.

La décomposition d'un graphe orienté en composantes fortement connexes est un problème important dans l'étude des chaînes de Markov, car il permet de déduire une chaîne réduite mettant en évidence les états `` puits '' d'où l'on ne peut plus sortir. Le graphe de la figure (1.12) représente un graphe connexe mais non fortement connexe. Il est composé de deux composantes fortement connexes : $\{1,\,2,\,3\}$ et $\{4,\,5,\,6\}$. On dit que la composante $\{1,\,2,\,3\}$ est un puits : une fois que l'on y entre, l'on ne peut plus en ressortir.

Figure 1.12: Exemple d'un graphe non fortement connexe