Étape 1
D'après le cours sur la théorie des graphes, si $M$ est la matrice d'adjacence d'un graphe, alors pour tout entier $n \ge 1$, le coefficient $m_{i,j}^{(n)}$ situé à la $i$-ème ligne et $j$-ème colonne de la matrice $M^n$ représente exactement le nombre de chemins de longueur $n$ reliant le sommet $S_i$ au sommet $S_j$.
Étape 2
On cherche la plus petite valeur de $n \ge 1$ telle que le coefficient $m_{1,2}^{(n)}$ de la matrice $M^n$ soit supérieur ou égal à $5$.
Étape 3
Pour $n = 1$, le nombre de chemins de longueur $1$ de $S_1$ à $S_2$ est $m_{1,2}^{(1)} = 1$.
Étape 4
Calculons la matrice $M^2 = M \times M$ : $$M^2 = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 & 2 \\ 1 & 1 & 2 & 0 \\ 2 & 0 & 1 & 1 \\ 0 & 2 & 1 & 1 \end{pmatrix}$$ Le coefficient $m_{1,2}^{(2)} = 1 < 5$.
Étape 5
Calculons la matrice $M^3 = M^2 \times M$ : $$M^3 = \begin{pmatrix} 1 & 1 & 0 & 2 \\ 1 & 1 & 2 & 0 \\ 2 & 0 & 1 & 1 \\ 0 & 2 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 3 & 1 & 3 & 1 \\ 1 & 3 & 1 & 3 \\ 1 & 3 & 3 & 1 \\ 3 & 1 & 1 & 3 \end{pmatrix}$$ Le coefficient $m_{1,2}^{(3)} = 1 < 5$.
Étape 6
Calculons la matrice $M^4 = M^3 \times M$ : $$M^4 = \begin{pmatrix} 3 & 1 & 3 & 1 \\ 1 & 3 & 1 & 3 \\ 1 & 3 & 3 & 1 \\ 3 & 1 & 1 & 3 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 6 & 4 & 4 \\ 6 & 2 & 4 & 4 \\ 4 & 4 & 2 & 6 \\ 4 & 4 & 6 & 2 \end{pmatrix}$$ Le coefficient $m_{1,2}^{(4)} = 6 \ge 5$.
Étape 7
Ainsi, la plus petite longueur $n \ge 1$ pour laquelle il existe au moins $5$ chemins distincts reliant $S_1$ à $S_2$ est $n = 4$.
Méthode clé
Le nombre de chemins de longueur $n$ allant du sommet $S_i$ au sommet $S_j$ est donné par le coefficient situé à la ligne $i$ et à la colonne $j$ de la matrice $M^n$.
Piège à éviter
Confondre la ligne et la colonne lors de la lecture du coefficient (lire le coefficient $(2,1)$ au lieu de $(1,2)$).
