Étape 1
On ordonne les sommets selon l'ordre alphabétique $(A, B, C)$. La matrice d'adjacence $M$ associée au graphe orienté est la matrice carrée d'ordre 3 dont le coefficient d'indice $(i,j)$ vaut 1 s'il existe un arc reliant le sommet $i$ au sommet $j$, et 0 sinon : $$M = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$$
Étape 2
D'après le cours, le nombre de chemins de longueur $n$ reliant le sommet $B$ (deuxième sommet) au sommet $A$ (premier sommet) est donné par le coefficient situé à la 2e ligne et à la 1re colonne de la matrice $M^n$, noté $(M^n)_{2,1}$.
Étape 3
Calculons les premières puissances de $M$. Pour $n = 2$ : $$M^2 = M \times M = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 0 \end{pmatrix}$$ On a donc $(M^2)_{2,1} = 1$.
Étape 4
Pour $n = 3$ : $$M^3 = M \times M^2 = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}$$ On a $(M^3)_{2,1} = 1$.
Étape 5
Pour $n = 4$ : $$M^4 = M \times M^3 = \begin{pmatrix} 1 & 1 & 1 \\ 2 & 1 & 1 \\ 1 & 1 & 0 \end{pmatrix}$$ On a $(M^4)_{2,1} = 2$.
Étape 6
Pour $n = 5$ : $$M^5 = M \times M^4 = \begin{pmatrix} 2 & 1 & 1 \\ 2 & 2 & 1 \\ 1 & 1 & 1 \end{pmatrix}$$ On a $(M^5)_{2,1} = 2$.
Étape 7
Pour $n = 6$ : $$M^6 = M \times M^5 = \begin{pmatrix} 2 & 2 & 1 \\ 3 & 2 & 2 \\ 2 & 1 & 1 \end{pmatrix}$$ On a $(M^6)_{2,1} = 3$.
Étape 8
Pour $n = 7$ : $$M^7 = M \times M^6 = \begin{pmatrix} 3 & 2 & 2 \\ 4 & 3 & 2 \\ 2 & 2 & 1 \end{pmatrix}$$ On a $(M^7)_{2,1} = 4$.
Étape 9
Pour $n = 8$, on obtient $(M^8)_{2,1} = 5$. La suite des coefficients $(M^n)_{2,1}$ étant strictement croissante à partir de $n = 5$, le coefficient vaut 4 si et seulement si $n = 7$. Il existe donc exactement 4 chemins distincts reliant $B$ à $A$ pour la longueur $n = 7$.
Méthode clé
Associer au graphe sa matrice d'adjacence $M$, puis utiliser le théorème selon lequel le terme situé à la ligne $i$ et à la colonne $j$ de la matrice $M^n$ est égal au nombre de chemins de longueur $n$ allant du sommet $i$ au sommet $j$.
Piège à éviter
Tenter un dénombrement manuel direct des chemins de longueur élevée : le risque d'omettre un chemin ou de compter un cycle en trop augmente très vite avec la longueur.
