Devoir de maths corrigé, Graphes et chaînes de Markov

Terminale générale, mathématiques expertes

Devoir de mathématiques, et corrigé, posé en maths expertes, terminale générale, année scolaire 2023/2024

Exercice 1: Traffic aérien entre 4 villes

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 exercice 1



  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.


Cacher la correction

Exercice 2: Calcul d'un état stable

On considère une chaîne de Markov $\left( X_n\rp$ dans l'espace des états $\Omega=\left\{}\newcommand{\ra}{\right\} e_1;e_2\ra$, dont la matrice $A$ de transition associée est
\[A=\lp\begin{array}{cc}0,1&0,9\\0,4&0,6\enar\rp\]

On note $\pi_n$ la distribution à l'étape des états à l'étape $n$. Initialement $\pi_0=\left( 0,2 \quad 0,8\rp$.
  1. Déterminer $\pi_1$, $\pi_2$ et $\pi_{10}$.
  2. Déterminer les éventuels états stables (ou distributions invariantes).

Correction exercice 2



  1. \[\begin{array}{ll}\pi_1&=\pi_0A\\&=\left( 0,2 \quad 0,8\rp\left(\begin{array}{cc}0,1&0,9\\0,4&0,6\enar\rp\\
  &=( 0,34 \quad 0,66 )\enar\]

    puis, éventuellement à l'aide d'une calculatrice
    \[\pi_2=\pi_1A=( 0,298 \quad 0,702)\]

    puis
    \[\pi_{10}=\pi_0A^{10}\simeq( 0,3077 \quad 0,6923)\]


  2. Une distribution stable, ou invariante, est $\pi=(x\quad y)$ avec $x+y=1$ et
    \[\begin{array}{ll}\pi A= \pi
  &\iff
  \la\begin{array}{lclcl}
  0,1x&+&0,4y&=&x\\
  0,9x&+&0,6y&=&y\enar\right.\\[1.3em]
  &\iff
  \la\begin{array}{lclcl}
  -0,9x&+&0,4y&=&0\\
  0,9x&-&0,4y&=&0\enar\right.
  \enar\]

    Ces deux équations sont équivalentes (l'opposée l'une de l'autre), et équivalente à
    \[x=\dfrac{0,4}{0,9}y=\dfrac49y\]

    Comme de plus $x+y=1$, on a donc
    \[x+y=\dfrac49y+y=\dfrac{13}9y=1\iff y=\dfrac9{13}\]

    On trouve alors aussi
    \[x+y=1 \iff x=1-y=\dfrac4{13}\]

    La seule distribution invariante est donc $\pi=\lp\dfrac4{13} \quad \dfrac9{13}\rp$


Cacher la correction

Exercice 3: Equilibre de gaz entre deux réservoirs

Deux compartiments, A et B, contiennent un gaz. Ces deux compartiments sont reliés entre eux, et le gaz peut donc librement passer d'un compartiment à l'autre.
Initialement le compartement $A$ contient 10% du gaz et les 90% restants sont dans le compartiment B.
À chaque seconde, 40% du gaz présent dans le compartiment A passe dans le compartiment B, et de même 40% du gaz dans le compartiment B passe dans le A. On note alors $\pi_n=\left( p_A \quad p_B\rp$ la répartition du gaz respectivement dans les compartiments A et B, au bout de $n$ secondes.
  1. Représenter l'évolution de la proportion de gaz entre les deux compartiments par un graphe pondéré.
  2. La matrice de transition associée à ce graphe est $M=\lp\begin{array}{cc}0,6&0,4\\0,4&0,6\enar\rp$.
    Donner la répartition du gaz au bout 1 seconde, puis au bout de 10 secondes.
  3. On considère la matrice $P=\lp\begin{array}{cc}1&1\\-1&1\enar\rp$.
    Montrer que cette matrice est inversible, puis que son inverse est $P^{-1}=\dfrac12\lp\begin{array}{cc}1&-1\\1&1\enar\rp$.
  4. Déterminer les nombres réels $x$ et $y$ dans la matrice $D=\lp\begin{array}{cc}x&0\\0&y\enar\rp$ tel qu'on ait
    \[M=PDP^{-1}\]


  5. Calculer $D^2$ et donner, pour tout entier $n$, la matrice $D^n$.
  6. Établir à l'aide d'un raisonnement par récurrence que, pour tout entier $n$ non nul, on a $M^n=PD^nP^{-1}$.
  7. Déterminer la limite $L$ de la matrice $D^n$ lorsque $n\to+\infty$. En déduire la distribution limite $\pi$ de la suite des distributions $(\pi_n)$.

Correction exercice 3



  1. \[\psset{arrowsize=8pt}\begin{pspicture}(0,-.3)(4.5,2.)
    %\psline{->}(1,1)(2.9,1)
    \psarc{->}(.3,1){.6}{20}{335}
    \psarc{->}(5.7,1){.6}{210}{160}
    \psarc{<-}(3,0){2.2}{35}{145}
    \psarc{<-}(3,2){2.2}{215}{325}
    \rput(1,1){$\bullet$}\rput(.7,1){$A$}
    \rput(5,1){$\bullet$}\rput(5.3,1){$B$}
    %
    \rput(-.65,1){0,6}
    \rput(6.6,1){0,6}
    \rput(3,1.9){0,4}
    \rput(3,0){0,4}
  \end{pspicture}\]

  2. On a $\pi_0=\left( 0,1 \quad 0,9\rp$ et au bout de 1s,
    \[\begin{array}{ll}\pi_1&=\pi_0M\\&=\left( 0,1 \quad 0,9\rp\left(\begin{array}{cc}0,4&0,6\\0,6&0,4\enar\rp\\
  &\simeq( 0,42 \quad 0,58 )\enar\]


    Au bout de 10 secondes, la distribution est
    \[\pi_{10}=\pi_0M^{10}\simeq(0,5 \quad 0,5)\]

    à $10^{-8}$ près.
  3. $P=\lp\begin{array}{cc}1&1\\-1&1\enar\rp$.
    On a $\det(P)=1\tm1-(-1)\tm1=2\not=0$, ce qui montre que cette matrice est inversible.
    Ensuite, on calcule de $PP^{-1}=\lp\begin{array}{cc}1&0\\0&1\enar\rp=I_2$, ce qui montre que cette matrice $P^{-1}$ est bien la matrice inverse de $P$.
  4. On calcule
    \[\begin{array}{ll}
  PDP^{-1}
  &=\lp\begin{array}{cc}1&1\\-1&1\enar\rp\lp\begin{array}{cc}x&0\\0&y\enar\rp\dfrac12\lp\begin{array}{cc}1&-1\\1&1\enar\rp\\[1.3em]
  &=\dfrac12\lp\begin{array}{cc}x&y\\-x&y\enar\rp\lp\begin{array}{cc}1&-1\\1&1\enar\rp\\[1.3em]
  &=\dfrac12\lp\begin{array}{cc}x+y&-x+y\\-x+y&x+y\enar\right)
  \enar\]

    Ainsi, pour avoir $M=PDP^{-1}$, on doit avoir
    \[\la\begin{array}{lcrcr}
  \dfrac12(\ x+y)&=&0,6\\[1em]
  \dfrac12(-x+y)&=&0,4
  \enar\right.\]

    soit encore
    \[\la\begin{array}{rclcl}
  x&+&y&=&1,2\\[1em]
  -x&+&y&=&0,8
  \enar\right.\]

    et donc, en ajoutant les deux équations, on obtient $2y=2$ soit $y=1$ et de même, en les soustrayant, on obtient $2x=0,4$ soit $x=0,2$
    On trouve donc la matrice diagonale $D=\lp\begin{array}{cc}0,2&0\\0&1\enar\rp$
  5. On calcule facilement $D^2=\lp\begin{array}{ll}0,2^2&0\\0&1\enar\rp$ et plus généralement, $D^n=\lp\begin{array}{ll}0,2^n&0\\0&1\enar\rp$ pour tout entier $n$.
  6. Initialisation: pour $n=1$, on a $M^1=PD^1P^{-1}$ d'après le calcul de la question précédente.

    Hérédité: Supposons que, pour un entier $n\geqslant1$ on ait $M^n=PD^nP^{-1}$,
    alors,
    \[\begin{array}{ll}
  M^{n+1}&=M^nM\\
  &=PD^nP^{-1}M
  \enar\]

    or on sait que $M=PDP^{-1}$, d'où
    \[\begin{array}{ll}
  M^n&=PD^n\underbrace{P^{-1}P}_{=I_2}DP^{-1}\\[1.6em]
  &=PD^nDP^{-1}\\[.6em]
  &=PD^{n+1}P^{-1}
  \enar\]

    ce qui montre que la formule est encore vraie au rang $n+1$.

    Conclusion: on vient donc de démontrer, d'après le principe de récurrence, que pour tout entier $n$ non nul, $M^n=PD^nP^{-1}$.
  7. Comme $-1<0,2<1$, on a $\dsp\lim_{n\to+\infty}0,2^n=0$ et alors,
    \[\lim_{n\to+\infty}D^n=L=\lp\begin{array}{cc}0&0\\0&1\enar\rp\]

    Comme
    \[\pi_n=\pi_0M^n=\pi_0PD^nP^{-1}\]

    on en déduit que
    \[\lim_{n\to+\infty}\pi_n=\pi_0PLP^{-1}\]

    Il reste à faire les produits matriciels, et on trouve que
    \[\pi_0PLP^{-1}=( 0,5 \quad 0,5 )\]

    d'où la limite
    \[\lim_{n\to+\infty}\pi_n=( 0,5 \quad 0,5 )\]

    Après un temps assez long, le gaz s'équilibre exactement entre les deux compartiments: 50% dans chaque compartiment.


Cacher la correction


Quelques autres devoirs



Quelques exercices corrigés

Exercices corrigés
Matrice d'adjacence d'un graphe et nombre de chemins


Exercices corrigés
Part de marché


Exercices corrigés
Flux de population entre un village et une grande ville


Exercices corrigés
Répartition en deux opérateurs téléphoniques


Exercices corrigés
Traffic aérien entre 4 villes






Voir aussi:
ccc