Devoir corrigé de maths en Première générale, spécialité mathématiques

Graphes et chaînes de Markov

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. Un dstribution 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


Voir aussi:
ccc