Analyser un graphe avec matrice de connexité

Énoncé

Soit M = pmatrix 0 & 1 & 0 1 & 0 & 1 0 & 1 & 0 pmatrix la matrice d'adjacence d'un graphe. Calculer la matrice de connexité C et déterminer si le graphe est fortement connexe. En déduire le diamètre du graphe.

Indice : Calcule C = M + M^2 + M^3. Le graphe est fortement connexe si tous les coefficients non diagonaux sont strictement positifs. Le diamètre est la distance maximale entre deux sommets.

Correction

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

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

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

   C = pmatrix 1 & 3 & 1 3 & 2 & 3 1 & 3 & 1 pmatrix

3. Étape 3 : Tous les coefficients non diagonaux de C sont strictement positifs. Le graphe est donc fortement connexe.
4. Étape 4 : Pour trouver le diamètre, on cherche la distance maximale. On voit que :
5. Étape 5 : - d(s_1, s_3) = 2 (car (M)_{1,3} = 0 mais (M^2)_{1,3} = 1)
6. Étape 6 : - Toutes les autres distances sont 1 ou 2. Le diamètre est donc diam(G) = 2.