Exercice : Matrices d'adjacence et comptage de chemins

Étape 1

Pour obtenir la première ligne de la matrice $M^2 = M \times M$, on calcule le produit scalaire de la première ligne de $M$, soit $(0, 1, 2)$, avec chacune des trois colonnes de $M$ : - Le coefficient $(1,1)$ de $M^2$ est $0 \times 0 + 1 \times 2 + 2 \times 1 = 4$. - Le coefficient $(1,2)$ de $M^2$ est $0 \times 1 + 1 \times 0 + 2 \times k = 2k$. - Le coefficient $(1,3)$ de $M^2$ est $0 \times 2 + 1 \times 1 + 2 \times 0 = 1$. La première ligne de la matrice $M^2$ est donc : $$\begin{pmatrix} 4 & 2k & 1 \end{pmatrix}$$

Étape 2

D'après le cours, le nombre de chemins de longueur $3$ reliant le sommet $S_1$ au sommet $S_3$ correspond au coefficient de la première ligne et de la troisième colonne de la matrice $M^3$. Ce coefficient $(M^3)_{1,3}$ s'obtient en effectuant le produit de la première ligne de $M^2$ par la troisième colonne de $M$ : $$(M^3)_{1,3} = 4 \times 2 + 2k \times 1 + 1 \times 0 = 8 + 2k$$

Étape 3

On sait qu'il y a $18$ chemins de longueur $3$ reliant $S_1$ à $S_3$. On résout l'équation : $$8 + 2k = 18$$ Ce qui équivaut à $2k = 10$, d'où $k = 5$.