Exercice 19 Liaisons aériennes

1. Le graphe orienté est le suivant.

Chaque flèche violette représente un vol direct, dans le seul sens indiqué. La matrice d'adjacence est : $$\boxed{A=\begin{pmatrix} 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \end{pmatrix}}$$ Elle n'est pas symétrique : par exemple, on peut aller de Paris à Lyon, mais pas directement de Lyon à Paris.

2. La calculatrice donne : $$A^{2}=\begin{pmatrix} 0 & 0 & \textcolor{#9e0018}{1} & 0 & 2 \\ 2 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \end{pmatrix} \qquad A^{3}=\begin{pmatrix} 3 & 0 & \textcolor{#9e0018}{0} & 1 & 0 \\ 0 & 2 & 0 & 2 & 1 \\ 1 & 0 & 1 & 0 & 2 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 2 \end{pmatrix}$$ On lit en ligne $1$, colonne $3$ : il existe un seul trajet de Paris à Marseille en exactement deux vols, $P\to L\to M$, et aucun en exactement trois vols.

3. D'après la Proposition 2, le coefficient $(i\,;j)$ de $S$ est la somme des nombres de trajets de $i$ à $j$ en $1$, $2$ et $3$ vols : c'est le nombre de trajets de $i$ à $j$ comportant au plus trois vols.

4. La calculatrice donne : $$S=\begin{pmatrix} 3 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 3 & 2 \\ 2 & 1 & 1 & 2 & 3 \\ 1 & 1 & \textcolor{#9e0018}{0} & 1 & 1 \\ 1 & 1 & 1 & 1 & 2 \end{pmatrix}$$ Tous les coefficients hors diagonale sont non nuls, sauf celui en ligne $N$ et colonne $M$. On ne peut donc pas aller de Nice à Marseille en au plus trois vols. Depuis Nice, le seul vol mène à Bordeaux, puis à Paris, puis à Lyon ou à Nice : il faut un quatrième vol, de Lyon à Marseille. $$\boxed{\text{Nice} \to \text{Marseille demande au minimum } 4 \text{ vols : } N\to B\to P\to L\to M}$$ On peut le confirmer en calculant $A^{4}$, dont le coefficient en ligne $4$, colonne $3$ vaut $1$.