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

Maths expertes, terminale générale

Devoir corrigé de mathématiques en maths expertes, terminale générale sur les graphes et chaînes de Markov: calcul du nombre de chemins d'une longueur donnée dans un graphe et promenade aléatoire dans un labyrinthe..
Devoir de mathématiques posé en maths expertes, terminale générale, année scolaire 2024/2025

Exercice 1: Petit binôme de Newton pour calculer la puissance d'un complexe

On csondière le graphe suivant:

\[\psset{unit=.8cm} 
\begin{pspicture}(1,-2.3)(4.5,5.5)
\psline(4,4)(0,4)(0,0)(4,4)
\psline(0,0)(2,-2)
\psline(0,4)(6,5)
\psline(2,-2)(6,5)
\psline(4,4)(2,-2)
\pscircle[fillstyle=solid,fillcolor=white](0,4){.3}\rput(0,4){\bf$A$}
\pscircle[fillstyle=solid,fillcolor=white](4,4){.3}\rput(4,4){\bf$C$}
\pscircle[fillstyle=solid,fillcolor=white](0,0){.3}\rput(0,0){\bf$B$}
\pscircle[fillstyle=solid,fillcolor=white](2,-2){.3}\rput(2,-2){\bf$D$}
\pscircle[fillstyle=solid,fillcolor=white](6,5){.3}\rput(6,5){\bf$E$} 
\end{pspicture}\]

  1. Ce graphe est-il complet ? connexe ? (justifier)
  2. Donner la matrice d'adjacence de ce graphe. On cosnidère les sommets numérotés dans l'ordre alphabétique.
  3. Quel est le nombre de chemins de longueur 5 qui relient A à D

Correction exercice 1


  1. Ce graphe n'est pas complet, car par exemple A et D ne sont pas reliés.
    Ce graphe est connexe: il existe un chemin entre n'importe quel couple de sommets.
  2. La matrice d'adjacence est une matrice 5x5:
    \[M=\lp\begin{array}{ccccc}
0 & 1 & 1 & 0 & 1\\
1 & 0 & 1 & 1 & 0\\
1 & 1 & 0 & 1 & 0\\
0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 0
\enar\rp\]

  3. On calcule
    \[M^5=\lp\begin{array}{ccccc}
  26 & 51 & 51 & \pscircle[fillstyle=solid,linecolor=red,fillcolor=white](.2,.12){.3}26 & 40 \\
  51 & 40 & 41 & 51 & 22 \\
  51 & 41 & 40 & 51 & 22 \\
  26 & 51 & 51 & 26 & 40 \\
  40 & 22 & 22 & 40 &  8
  \enar\rp\]


    On trouve dans cette matrice qu'il y a 26 chaînes de longueur 5 qui relient A à D.


Cacher la correction

Exercice 2: Labyrinthe aléatoire: probabilité de sortir au hasard

Sortir aléatoirement d'un labyrinthe
On démarre dans le labyrinthe suivant dans la pièce A, la sortie se situe en G.
On se déplace suivant la règle suivante: lorsque je suis dans une pièce je me déplace forcément dans une autre pièce adjacente et accessible et au hasard, avec équiprobabilité. Lorsque j'arrive en G, bien sûr, je suis arrivé et je ne repars pas en arrière: je reste à coup sûr en G ensuite.
On note $\pi_n$ la distribution des probabilités de se trouver dans chaque pièce (numérotées dans l'ordre alphabétique) après $n$ déplacements.
Comme on part de A, on a donc initialement $\pi_0=\lp\begin{array}{ccccccc}1&0&0&0&0&0&0\enar\rp$

\[\psset{unit=.5cm}\begin{pspicture}(0,0)(10,10)
  \psline(.6,.6)(.6,9.4)(10,9.4)(10,6)
  \psline(10,4)(10,.6)(.6,.6)  
  \psline(1,8)(2,8)(2,9)(8,9)(8,8)(10,8)(10,9.4)
  \psline(2,5.2)(4,5.2)\psline(2,4.8)(4,4.8)\psline[linewidth=2pt](3,4.8)(3,5.2)
  \psline(1,8)(1,6)(2,6)(2,5.2)
  \psline(2,4.8)(2,4)(1,4)(1,2)(2,2)(2,1)
  \psline(2,1)(4,1)(4,2)(4.8,2)(4.8,4)(4,4)(4,4.8)
  \psline(4,5.2)(4,6)(6,6)(6,5.2)
  \psline(6,5.2)(8,5.2)(8,6)(10,6)
  \psline(6,4.8)(8,4.8)(8,4)(10,4)
  \psline(6,4.8)(6,4)(5.2,4)(5.2,2)(6,2)(6,1)(10,1)
  \rput(1.3,8.6){A}
  \rput(8.8,8.6){B}
  \rput(1.3,5){C}
  \rput(5,5){D}
  \rput(1.3,1.3){E}
  \rput(5,1.3){F}
  \rput(9,5){G}
\end{pspicture}\]

  1. On considère le graphe probabiliste dont les sommets sont les différentes pièces du labyrinthe numérotées dans l'ordre alphabétique.
    Écrire la matrice $M$ de transition associée à ce graphe.
  2. Calculer la distribution de probabilités $\pi_1$ et interpréter ce résultat.
  3. Calculer la probabilité de sortir du labyrinthe en 5 déplacements.
  4. Calculer la probabilité de sortir du labyrinthe en 10 déplacements.
  5. Calculer la probabilité de sortir du labyrinthe en 20 déplacements.
  6. Combien de déplacements faut-il prévoir pour avoir au moins une chance sur deux de sortir de ce labyrinthe ?
  7. Je lance un dé à six faces bien équilibré pour choisir au hasard la pièce à partir de laquelle je démarre le labyrinthe: si j'obtiens un 1 je démarre le labyrinthe en 1, si j'obtiens un deux je le démarre en B, …
    Commbien de déplacements faut-il alors prévoir pour avoir au moins une chance sur deux de sortir de ce labyrinthe ?

Correction exercice 2



  1. \[M=\lp\begin{array}{*7c}
  0 & \frac12 & \frac12 & 0 & 0 & 0 & 0\\
  1 & 0 & 0 & 0 & 0 & 0 & 0 \\
  \frac12 & 0 & 0 & 0 & \frac12 & 0 & 0 \\
  0 & 0 & 0 & 0 & 0 & \frac12 & \frac12\\
  0 & 0 & \frac12 & 0 & 0 & \frac12 & 0  \\
  0 & 0 & 0 & \frac12 & \frac12 & 0  & 0\\
  0 & 0 & 0 & 0 & 0 & 0 & 1  
  \enar\rp\]


  2. On a
    \[\pi_1=\pi_0M=\lp\begin{array}{*7c}0&\frac12&\frac12&0&0&0&0\enar\rp\]

    On commence en A et après un déplacement, on une chance sur deux d'être en B et une chance sur deux d'être en C, et aucune chance d'être ailleurs en 1 déplacement.
    Ce résultat se trouve directement, dans la définition même du labyrinthe, sans avoir à faire le calcul matriciel.
  3. Pour sortir en 5 déplamcents, il n'y a qu'un seule possibilité, se déplacer toujours vers la sortie, soit le chemin A-C-E-F-D-G.
    À chaque déplacement, il y a une chance sur deux d'aller dans la bonne direction, soit la probabilité de sortir en exacetement 5 déplacements:
    \[p=\lp\dfrac12\rp^5=\dfrac1{2^5}=\dfrac1{32}\simeq0,031\]



    On peut aussi calculer la distribution complète des probabilités au bout de 5 déplacements:
    \[\begin{array}{ll}\pi_5&=\pi_0M^5\\[.5em]&\simeq\lp\begin{array}{*7c}0 & 0,312 & 0,469 & 0 & 0 & 0,188 & 0.031\enar\rp\enar\]

  4. On calcule la distribution des probabilités au bout de 10 déplacements, soit
    \[\begin{array}{ll}\pi_{10}&=\pi_0M^{10}\\[.5em]&\simeq\lp\begin{array}{*7c}0.45 & 0 & 0 & 0.11 & 0.31 & 0 & 0.13\enar\rp\enar\]

    On trouve donc que la probabilité de sortir du labyrinthe, c'est-à-dire d'être en G, est d'environ 0,13.
  5. On calcule de même pour 20 déplacements,
    \[\begin{array}{ll}\pi_{20}&=\pi_0M^{20}\\[.5em]&\simeq\lp\begin{array}{*7c}0.311&0&0&0,083&0,227&0 &0,378]\enar\rp\enar\]

    On trouve donc que cette fois la probabilité de sortir du labyrinthe est d'environ 0,378.
  6. La probabilité de sortir du labyrinthe croît bien sûr lorsqu'on augmente le nombre $n$ de déplacements, et en testant avec la calculatrice on trouve que la probabilité de sortie est d'environ 0,495 pour 26 déplacements et est d'environ 0,529 pour 27 déplacements.
    Il faut donc prévoir $n=27$ déplacements pour avoir plus d'une chance sur deux de sortir de ce labyrinthe, en s'y déplaçant au hasard.
  7. La distribution initiale est maintenant
    \[\pi_0=\lp\begin{array}{ccccccc}\dfrac16&\dfrac16&\dfrac16&\dfrac16&\dfrac16&\dfrac16&0\enar\rp\]

    et on reprend alors les calculs de la question précédente en calculant successivement les matrices $\pi_n=\pi_OM^n$ jusqu'à ce que le dernier éléments de cette matrice, donc la probabilité $\pi_n=P(X_n=G)$, soit supérieur ou égal à 0,5.
    On trouve cette fois $n=17$.


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