Graphe connexe

• Deux sommets $u$ et $v$ d’un graphe^EN non orienté $G$ sont dits connectés s’il existe une chaîne entre $u$ et $v$. On peut alors définir sur l’ensemble des sommets $X$ la relation d’équivalence suivante :

$uRv\iff u=v$ où $u$ et $v$ sont connectés.

Les classes d’équivalence de cette relation sont appelées « composantes connexes de $G$ ». Les sommet d’une même composante connexe sont tous connectés entre eux. Deux sommets appartenant à deux composantes connexes différentes ne sont pas connectés.

Un graphe $G$ non orienté est donc dit connexe s’il admet une seule composante connexe $X$. Sinon il est dit non connexe.

• Pour les digraphes (graphes orientés), on définit la relation d’équivalence comme suit :

$uRv\iff u=v$ où $v$ est accessible à partir de $u$ et vice versa.

Les classes d’équivalence de cette relation sont appelées « composantes fortement connexes de $G$ ». Les sommet d’une même composante fortement connexes sont tous accessibles entre eux. Il n’existe aucun chemin entre deux sommets appartenant à deux composantes fortement connexes différentes.