Déterminer les composantes fortement connexes

Énoncé

Soit M = pmatrix 0 & 1 & 0 & 0 0 & 0 & 1 & 0 0 & 0 & 0 & 1 0 & 0 & 0 & 0 pmatrix la matrice d'adjacence d'un graphe avec 4 sommets. Déterminer les composantes fortement connexes de ce graphe.

Indice : Calcule la matrice de connexité C = M + M^2 + M^3. Deux sommets i et j sont dans la même composante si c_{i,j} > 0 ET c_{j,i} > 0.

Correction

1. Étape 1 : On calcule M^2 et M^3.

   M^2 = pmatrix 0 & 0 & 1 & 0 0 & 0 & 0 & 1 0 & 0 & 0 & 0 0 & 0 & 0 & 0 pmatrix, M^3 = pmatrix 0 & 0 & 0 & 1 0 & 0 & 0 & 0 0 & 0 & 0 & 0 0 & 0 & 0 & 0 pmatrix

2. Étape 2 : On calcule la matrice de connexité C = M + M^2 + M^3.

   C = pmatrix 0 & 1 & 1 & 1 0 & 0 & 1 & 1 0 & 0 & 0 & 1 0 & 0 & 0 & 0 pmatrix

3. Étape 3 : Pour qu'un couple (i,j) soit dans la même composante fortement connexe, il faut c_{i,j} > 0 ET c_{j,i} > 0.
4. Étape 4 : On vérifie : c_{1,2} = 1 > 0 mais c_{2,1} = 0, donc s_1 et s_2 ne sont pas dans la même composante.
5. Étape 5 : De même pour tous les autres couples : il n'y a pas de chemins dans les deux sens entre des sommets distincts.
6. Étape 6 : Chaque sommet forme sa propre composante fortement connexe. Il y a donc 4 composantes : \{s_1\}, \{s_2\}, \{s_3\}, \{s_4\}.