2.4 Connexité

Definition 2.6 (Connexité) Une composante connexe de \(G=(V,E)\) est un sous-ensemble \(C=\{v_1,\dots, v_k\}\subset V\) tel que pour tous \(v_i,v_j\in C\), il existe un chemin dans \(G\) de \(v_i\) à \(v_j\).

Un graphe \(G=(V,E)\) est dit connexe s’il possède une unique composante connexe, i.e. pour tous \(i,j\in V\), il existe un chemin de \(i\) à \(j\) dans \(G\).

La connexité d’un graphe dirigé est définie à partir des chemins non dirigés.

Un noeud qui n’a pas de voisins est dit isolé et il forme une composante connexe à lui seul.

Proposition 2.1 Tout graphe peut être décomposé en un unique ensemble de composantes connexes (maximales). Le nombre de composantes connexes d’un graphe est supérieur ou égal à \(n-|E|\).

Proof. On vérifie facilement que si \(|E|=0\) alors il y a \(n\) composantes connexes. De même si \(|E|=1\) on a exactement \(n-1\) composantes connexes. Par induction sur le nombre d’arêtes: supposons que \(G=(V,E)\) est un graphe avec \(c\) composantes connexes tel que \(c\ge n - |E|\). On ajoute une arête à \(G\) pour fabriquer \(G'=(V, E')\) et on note \(c'\) le nombre de composantes connexes de \(G'\). Alors soit \(c'=c\) (l’arête ajoutée relie deux noeuds qui sont déjà dans la même composante connexe), soit \(c'=c-1\) (l’arête ajoutée relie deux composantes connexes entre elles pour n’en créer plus qu’une). Dans le premier cas on a \(c'=c\geq n - |E| \geq n-|E|-1 = n-|E'|\). Dans le second cas, on a \(c'=c-1 \geq n - |E| -1 = n- (|E|+1)= n - |E'|\). La relation est toujours vérifiée.

Composante connexe géante

Soit \(G=(V,E)\) un graphe et \(C\) une composante connexe de ce graphe. La taille relative de \(C\) est définie par \(|C|/|V|\), i.e. le nombre de noeuds de la composante sur le nombre de noeuds total. Soit \((G_n)_{n \ge 1}\) une suite de graphes telle que \(G_n\) est un graphe à \(n\) noeuds et \((C_n)_{n\ge 1}\) suite croissante (\(C_n\subset C_{n+1}\)) telle que \(C_n\) est une composante connexe de \(G_n\). Alors \(C_n\) est dite géante si sa taille relative \(|C_n|/n\) ne tend pas vers 0 lorsque \(n\) devient grand.