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

Connexité


\begin{defi}[Connexité]
On dit qu'un graphe $G$\ est connexe si et seulement si...
...$, il existe une chaîne permettant de
joindre $i$\ à $j$\ dans $G$.
\end{defi}
Cette notion s'applique aussi bien aux graphes orientés qu'aux graphes non orientés. Plus prosaiquement, elle traduit le fait qu'un graphe est `` d'un seul tenant ''. La figure (1.10)

Figure 1.10: Exemple d'un graphe connexe
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=conn1.eps}
\end{center}
\end{figure}


\begin{defi}[Composante connexe]
Une \emph{composante connexe} est un sous graphe connexe maximal.
\end{defi}
Il est toujours possible de partitionner un graphe en composantes connexes. Par exemple, sur la figure (1.11), le graphe est scindé en 3 composantes connexes.

Figure 1.11: Exemple d'un graphe non connexe en 3 composantes connexes
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=nconn.eps}
\end{center}
\end{figure}



Bruno Garcia 2000-12-17