Déterminer les composantes fortement connexes
Énoncé
Soit M = (0 , 1 , 0 , 0 ; 0 , 0 , 1 , 0 ; 0 , 0 , 0 , 1 ; 0 , 0 , 0 , 0) 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² + M³. Deux sommets i et j sont dans la même composante si cᵢ,ⱼ > 0 ET cⱼ,ᵢ > 0.
Correction
- É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ᵢ,ⱼ > 0 ET cⱼ,ᵢ > 0.
- É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₁ → s₂ → s₃ → s₄, sans aucun retour.
- Étape 3 : Les puissances, chacune décalant les 1 d'un cran vers la droite :
M² = (0, 0, 1, 0 ; 0, 0, 0, 1 ; 0, 0, 0, 0 ; 0, 0, 0, 0) M³ = (0, 0, 0, 1 ; 0, 0, 0, 0 ; 0, 0, 0, 0 ; 0, 0, 0, 0)
- Étape 4 : La matrice de connexité :
C = M + M² + M³ = (0, 1, 1, 1 ; 0, 0, 1, 1 ; 0, 0, 0, 1 ; 0, 0, 0, 0)
- Étape 5 : C est triangulaire supérieure stricte, et c'est la réponse. Pour tout couple i < j : cᵢ,ⱼ > 0 mais cⱼ,ᵢ = 0. On peut aller vers la droite, jamais revenir.
c₁,₂ = 1 > 0 mais c₂,₁ = 0
- Étape 6 : Aucun couple de sommets distincts ne communique dans les deux sens. Chaque sommet est donc seul dans sa composante :
{s₁}, {s₂}, {s₃}, {s₄} 4 composantes
- É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₄ depuis s₁, 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ᵢ,ᵢ > 0.
Ici la diagonale de C est nulle : aucun circuit, donc aucune composante non réduite à un point.