Calculer le nombre de chemins de longueur 2

Énoncé

Soit M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix la matrice d'adjacence d'un graphe. Calculer M^2 et interpréter le coefficient (M^2)_{1,3}.

Indice : Calcule M^2 en multipliant M par elle-même. Le coefficient (M^2)_{i,j} donne le nombre de chemins de longueur 2 de s_i à s_j.

Correction

1. Étape 1 : On calcule M^2 = M M.

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

2. Étape 2 : On effectue le produit matriciel.

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

3. Étape 3 : Le coefficient (M^2)_{1,3} = 1 signifie qu'il existe exactement 1 chemin de longueur 2 du sommet 1 au sommet 3.
4. Étape 4 : Ce chemin est : s_1 s_2 s_3 (car m_{1,2} = 1 et m_{2,3} = 1).