next up previous
suivant: Arbres monter: Connexité, forte connexité précédent: Connexité

Forte connexité

Contrairement à la notion de connexité, celle de forte connexité n'est disponible que sur les réseaux orientés.
\begin{defi}[Forte connexité]
On dit qu'un graphe $G$\ est fortement connexe si...
...$i$\ à $j$\ et un chemin permettant de joindre $j$\ à $i$\ dans $G$.
\end{defi}
Autrement dit, dans un graphe fortement connexe, depuis un sommet, il est toujours possible de trouver un chemin aller retour vers chaque autre.
\begin{defi}[Composante fortement connexe]
On appelle \emph{composante fortement connexe} un sous graphe fortement
connexe maximal.
\end{defi}
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
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=nfort.eps}
\end{center}
\end{figure}



Bruno Garcia 2000-12-17