Vérifier la connexité forte d'un graphe

Énoncé

Soit M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix la matrice d'adjacence d'un graphe avec 3 sommets. Vérifier si ce graphe est fortement connexe.

Indice : Un graphe est fortement connexe si pour tout couple (i,j), il existe un chemin de i à j ET de j à i. Calcule M + M^2 + M^3 pour obtenir la matrice de connexité.

Correction

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

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

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

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

3. Étape 3 : Tous les coefficients non diagonaux de C sont strictement positifs. Cela signifie qu'il existe des chemins entre tous les couples de sommets dans les deux sens.
4. Étape 4 : Le graphe est donc fortement connexe.