Exercice 17

1. Redessinons le graphe pour lister ses arcs :

Les sept arcs sont $A\to B$, $B\to A$, $B\to C$, $B\to D$, $C\to A$, $C\to C$ et $D\to C$. En rangeant les sommets dans l'ordre $A$, $B$, $C$, $D$ : $$\boxed{M=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}}$$

2. On utilise le théorème du cours : le coefficient en ligne $i$ et colonne $j$ de $M^{n}$ donne le nombre de chemins de longueur $n$ allant du sommet $i$ au sommet $j$.

(a) On calcule les puissances successives : $$M^{2}=\begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 1 & 2 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \end{pmatrix} \qquad M^{4}=\left(M^{2}\right)^{2}=\begin{pmatrix} 3 & 1 & 3 & 1 \\ 4 & 3 & 5 & 1 \\ 3 & 2 & 4 & 1 \\ 2 & 1 & 2 & 1 \end{pmatrix}$$ Le coefficient cherché est celui de la ligne $D$ et de la colonne $A$, c'est-à-dire la ligne $4$ et la colonne $1$ : $$\boxed{\text{il existe } 2 \text{ chemins de longueur } 4 \text{ reliant } D \text{ à } A}$$ Ce sont $D\to C\to A\to B\to A$ et $D\to C\to C\to C\to A$, ce dernier empruntant trois fois la boucle en $C$.

(b) De même : $$M^{6}=\left(M^{2}\right)^{3}=\begin{pmatrix} 8 & 4 & 9 & 3 \\ 13 & 8 & 16 & 4 \\ 10 & 6 & 12 & 3 \\ 6 & 3 & 7 & 2 \end{pmatrix}$$ Le coefficient de la ligne $B$ et de la colonne $C$, c'est-à-dire la ligne $2$ et la colonne $3$, vaut : $$\boxed{\text{il existe } 16 \text{ chemins de longueur } 6 \text{ reliant } B \text{ à } C}$$