Traffic aérien entre 4 villes

Exercice corrigé - Maths expertes, terminale générale

Énoncé

On considère quatre villes $V_1$, $V_2$ , $V_3$ et $V_4$ et le traffic aérien qui permet de relier ces quatre villes: il existe seulement des vols directs
  • de $V_1$ vers $V_2$ et de $V_1$ vers $V_4$,
  • de $V_2$ vers $V_3$,
  • de $V_3$ vers $V_1$ et de $V_3$ vers $V_4$,
  • de $V_4$ vers $V_2$

  1. Recopier et compléter le graphe suivant.
    \[\psset{arrowsize=7pt}\begin{pspicture}(-4,-3.5)(4,3.5) \rput(0,3){$\bullet$}\rput(0,3.3){$V_1$} \rput(-3,0){$\bullet$}\rput[r](-3.2,0){$V_2$} \rput(3,0){$\bullet$}\rput[l](3.2,0){$V_4$} \rput(0,-3){$\bullet$}\rput(0,-3.3){$V_3$} \psarc{<-}(0,0){3}{5}{85} \psarc{->}(0,0){3}{95}{175} \end{pspicture}\]


  2. Écrire la matrice $M$ associée à ce graphe, en prenant les villes dans leur ordre de numération.
  3. Donner les matrices $M^2$, $M^3$ et $M+M^2+M^3$.
  4. Combien de vols comportant au plus deux escales permettent de relier $V_2$ à $V_4$ ?
  5. Existe t-il au moins un vol de chaque ville $V_i$ vers chaque ville $V_j$ comportant au plus deux escales ? Pourquoi ?



Correction

Correction


  1. \[\psset{unit=.8cm,arrowsize=7pt}\begin{pspicture}(-4,-3.5)(4,2.2) \rput(0,3){$\bullet$}\rput(0,3.3){$V_1$} \rput(-3,0){$\bullet$}\rput[r](-3.2,0){$V_2$} \rput(3,0){$\bullet$}\rput[l](3.2,0){$V_4$} \rput(0,-3){$\bullet$}\rput(0,-3.3){$V_3$} \psarc{<-}(0,0){3}{5}{85} \psarc{->}(0,0){3}{95}{175} % \psarc{->}(0,0){3}{185}{265} \psarc{->}(0,0){3}{275}{355} \psarc{->}(-3,0){4.3}{318}{42} \psarc{->}(0,-3.2){4.3}{50}{131} \end{pspicture}\]


  2. La matrice associée à ce graphe est $M=\lp\begin{array}{cccc} 0&1&0&1\\ 0&0&1&0\\ 1&0&0&1\\ 0&1&0&0\enar\rp$.
    On a ensuite $M^2=\lp\begin{array}{cccc} 0&1&1&0\\ 1&0&0&1\\ 0&2&0&1\\ 0&0&1&0\enar\rp$. et $M^3=\lp\begin{array}{cccc} 1&0&1&1\\ 0&2&0&1\\ 0&1&2&0\\ 1&0&0&1\enar\rp$. et donc $M+M^2+M^3= \lp\begin{array}{cccc} 1&2&2&2\\ 1&2&1&2\\ 1&3&2&2\\ 1&1&1&1\enar\rp$.
  3. La matrice d'adjacence $M$ contient les vols directs entre les villes, $M^2$ contient les nombres de vols avec exactement une escale, et $M^3$ les nombres de vols avec exactement 2 escales.
    On trouve ainsi, dans la matrice $M+M^2+M^3$ qu'il y a 2 vols avec au plus deux escales qui permettent de relier $V_2$ à $V_4$.
  4. Comme la matrice $M+M^2+M^3$ ne contient aucun zéro, toute ville $V_i$ peut être reliée à chaque ville $V_j$ avec au plus deux escales.


Tag:Chaines de Markov

Autres sujets au hasard: Lancer de dés


Voir aussi:

Quelques devoirs


LongPage: h2: 3 - h3: 0