Graphe connexe

La notion de connexité formalise l'idée intuitive de "graphe en un seul morceau". Soit $G$ un graphe non-orienté et $(u,v)$ une paire de sommets. $u$ et $v$ sont dits connectés si il existe une chaîne reliant $u$ et $v$.

Si la chaîne est de longueur 1, autrement dit si il existe une arête reliant $u$ et $v$, les sommets sont dits adjacents.

Par convention, $u$ est relié à $u$ de sorte que "être connecté" est une relation d'équivalence.

Autrement dit un graphe non-orienté connexe ne possède pas de partie isolée.

On peut généraliser cette notion à des graphes orientés : soit $G$ un graphe orienté :

Un graphe fortement connexe est de connexité unilatérale. De même, un graphe de connexité unilatérale est faiblement connexe.

Lorsqu'un graphe n'est pas connexe, on peut vouloir parler des différents morceaux qui le constituent : soit $G$ un graphe non-orienté. Une composante connexe de $G$ est un sous-graphe induit connexe maximal de $G$.

Autrement dit, une composante connexe est un sous-graphe connexe de $G$ tel qu'on ne puisse pas lui ajouter de sommets sans perdre la connexité.

"Être connecté à" étant une relation d'équivalence, on peut définir une composante connexe comme classe d'équivalence pour cette relation. En particulier, chaque sommet appartient à une et une seule composante connexe et un graphe non-orienté est connexe si et seulement si il contient une unique composante connexe.

On peut, de même, parler de composante faiblement, fortement et unilatéralement connexe dans le cas des graphes orientés.

Le nombre $C_n$ de graphes connexes à $n$ sommets est donné par la relation de récurrence $C_n = 2^{\binom{n}{2}} - \frac{1}{n} \sum_{k=1}^{n-1} k \binom{n}{k} 2^{\binom{n-k}{2}} C_k $ dont les premières itérations donnent $1$, $1$, $4$, $38$, $728$, $26704$, $1866256$ et $251548592$ (Séquence A001187 sur l'OEIS)