Calculer la distance entre deux sommets

Énoncé

Soit M = pmatrix 0 & 1 & 0 & 0 0 & 0 & 1 & 0 0 & 0 & 0 & 1 1 & 0 & 0 & 0 pmatrix la matrice d'adjacence d'un graphe avec 4 sommets. Calculer la distance d(s_1, s_4) entre les sommets s_1 et s_4.

Indice : La distance est la longueur du plus court chemin. Calcule M, M^2, M^3 jusqu'à trouver (M^k)_{1,4} > 0.

Correction

1. Étape 1 : On vérifie d'abord (M)_{1,4} = 0, donc il n'y a pas d'arc direct de s_1 à s_4.
2. Étape 2 : On calcule M^2.

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

3. Étape 3 : On vérifie (M^2)_{1,4} = 0, donc il n'y a pas de chemin de longueur 2.
4. Étape 4 : On calcule M^3.

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

5. Étape 5 : On vérifie (M^3)_{1,4} = 1 > 0, donc il existe un chemin de longueur 3 de s_1 à s_4.
6. Étape 6 : La distance est donc d(s_1, s_4) = 3. Le chemin est s_1 s_2 s_3 s_4.