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 : Deux sommets sont dans la même composante fortement connexe quand on peut aller de l'un à l'autre et revenir. Il faut donc vérifier les deux sens, et le test porte sur un COUPLE de coefficients. Même composante fortement connexe : i et j sont dans la même composante lorsque c_{i,j} > 0 ET c_{j,i} > 0.
2. Étape 2 : La forme de M est parlante : tous les 1 sont au-dessus de la diagonale, et la dernière ligne est nulle. Le graphe est le chemin s_1 s_2 s_3 s_4, sans aucun retour.
3. Étape 3 : Les puissances, chacune décalant les 1 d'un cran vers la droite :

   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

4. Étape 4 : La matrice de connexité :

   C = M + M^2 + M^3 = pmatrix 0&1&1&1 0&0&1&1 0&0&0&1 0&0&0&0 pmatrix

5. Étape 5 : C est triangulaire supérieure stricte, et c'est la réponse. Pour tout couple i < j : c_{i,j} > 0 mais c_{j,i} = 0. On peut aller vers la droite, jamais revenir.

   c_{1,2} = 1 > 0 c_{2,1} = 0

6. Étape 6 : Aucun couple de sommets distincts ne communique dans les deux sens. Chaque sommet est donc seul dans sa composante :

   \{s_1\},\ \{s_2\},\ \{s_3\},\ \{s_4\} 4 composantes

7. Étape 7 : À comparer avec le 39008. Là-bas C était pleine de 1 : une seule composante contenant tout le graphe. Ici C est triangulaire : autant de composantes que de sommets. Ce sont les deux cas extrêmes. Un chemin dans un sens ne suffit jamais : On atteint s_4 depuis s_1, donc le graphe est bien « d'un seul tenant » — il est FAIBLEMENT connexe. Mais la forte connexité exige l'aller ET le retour, et il n'y a aucun retour ici. Tester un seul sens est l'erreur classique de l'exercice. La diagonale de C donne la réponse d'un coup d'œil : Un sommet appartient à une composante d'au moins deux éléments seulement s'il est sur un circuit, donc si c_{i,i} > 0. Ici la diagonale de C est nulle : aucun circuit, donc aucune composante non réduite à un point.