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

  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ᵢ,ⱼ > 0 ET cⱼ,ᵢ > 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₁ → s₂ → s₃ → s₄, sans aucun retour.
  3. É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)

  4. É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)

  5. É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

  6. É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

  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₄ 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.