Étape 1
D'après le cours, le nombre de chemins de longueur 3 reliant le sommet 3 au sommet 4 est égal au coefficient situé à la troisième ligne et quatrième colonne de la matrice $M^3$, noté $(M^3)_{3,4}$.
Étape 2
On sait que $M^3 = M^2 \times M$. Le coefficient $(M^3)_{3,4}$ s'obtient donc en effectuant le produit scalaire entre la troisième ligne de $M^2$ et la quatrième colonne de $M$.
Étape 3
Déterminons les coefficients de la troisième ligne de $M^2 = M \times M$. Pour chaque colonne $j$ de $M$, on a : $$(M^2)_{3,j} = M_{3,1}M_{1,j} + M_{3,2}M_{2,j} + M_{3,3}M_{3,j} + M_{3,4}M_{4,j}$$ Comme $M_{3,1} = k$, $M_{3,2} = 0$, $M_{3,3} = 0$ et $M_{3,4} = 1$, cette relation se simplifie en : $$(M^2)_{3,j} = k \times M_{1,j} + 1 \times M_{4,j}$$
Étape 4
On calcule successivement les termes de cette ligne : pour $j = 1$, $(M^2)_{3,1} = k \times 0 + 1 \times 1 = 1$ ; pour $j = 2$, $(M^2)_{3,2} = k \times 1 + 1 \times 1 = k + 1$ ; pour $j = 3$, $(M^2)_{3,3} = k \times 1 + 1 \times 0 = k$ ; pour $j = 4$, $(M^2)_{3,4} = k \times 0 + 1 \times 0 = 0$. La troisième ligne de $M^2$ est donc $\begin{pmatrix} 1 & k+1 & k & 0 \end{pmatrix}$.
Étape 5
La quatrième colonne de $M$ étant donnée par $\begin{pmatrix} 0 \\ 2 \\ 1 \\ 0 \end{pmatrix}$, on en déduit : $$(M^3)_{3,4} = 1 \times 0 + (k+1) \times 2 + k \times 1 + 0 \times 0 = 2k + 2 + k = 3k + 2$$
Étape 6
L'énoncé indique qu'il y a 23 chemins de longueur 3 du sommet 3 au sommet 4, ce qui se traduit par : $$3k + 2 = 23$$ d'où $3k = 21$, soit $k = 7$.
Méthode clé
D'après le cours sur les représentations matricielles des graphes, le coefficient situé à la ligne $i$ et à la colonne $j$ de la matrice $M^n$ est égal au nombre de chemins de longueur $n$ reliant le sommet $i$ au sommet $j$.
Piège à éviter
Attention à ne pas calculer la totalité de la matrice $M^2$ ou $M^3$ : seuls les coefficients de la troisième ligne de $M^2$ sont nécessaires pour déterminer $(M^3)_{3,4}$.
