Connexité

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