Exercices — Graphes et chaînes de Markov

Six élèves d'une classe, notés A, B, C, D, E et F, sont inscrits sur un réseau social. On modélise les relations d'amitié par le graphe ci-dessous : chaque sommet représente un élève, et une arête relie deux sommets lorsque les deux élèves sont amis.

1. Quel est l'ordre de ce graphe ?

2. Déterminer le degré de chaque sommet. On pourra présenter les résultats dans un tableau.

3. Quels sont les sommets adjacents à C ? Interpréter concrètement ce résultat.

4. Vérifier que la somme des degrés de tous les sommets est égale au double du nombre d'arêtes.

5. Ce graphe est-il complet ? Justifier.

Lors d'une réunion, $n$ personnes sont présentes. Certaines se serrent la main, d'autres non. On modélise la situation par un graphe : chaque sommet représente une personne, et une arête relie deux sommets lorsque les deux personnes correspondantes se sont serré la main.

a. Que représente le degré d'un sommet dans ce modèle ?

b. Démontrer que la somme des degrés de tous les sommets d'un graphe est toujours un nombre pair.

c. En déduire que le nombre de personnes ayant serré un nombre impair de mains est nécessairement pair.

d. Est-il possible que $9$ personnes aient chacune serré exactement $3$ mains ? Justifier.

Pour tout entier $n⩾2$, on note $K_n$ le graphe complet d'ordre $n$ : il possède $n$ sommets, et deux sommets quelconques sont toujours reliés par une arête.

a. Dessiner le graphe $K_4$.

b. Quel est le degré de chaque sommet de $K_n$ ? Justifier.

c. Démontrer que $K_n$ possède exactement ${\displaystyle \frac{n(n-1)}{2}}$ arêtes. On pourra utiliser la somme des degrés.

d. Application. Un tournoi de football réunit $12$ équipes ; chaque équipe rencontre exactement une fois chacune des autres. Combien de matchs sont joués au total ?

On considère les deux graphes $G_1$ et $G_2$ représentés ci-dessous. Le graphe $G_1$ a pour sommets A, B, C, D, E ; le graphe $G_2$ a pour sommets M, N, P, Q, R, S.

a. Donner une chaîne de longueur $3$ reliant A à E dans $G_1$.

b. Les graphes $G_1$ et $G_2$ sont-ils connexes ? Justifier.

c. Le graphe $G_1$ possède-t-il un cycle ? Si oui, en donner un.

d. Combien d'arêtes faut-il ajouter, au minimum, au graphe $G_2$ pour le rendre connexe ? Proposer une telle arête.

On considère le graphe $G$ ci-dessous, dont les sommets sont A, B, C et D.

a. Écrire la matrice d'adjacence $A$ du graphe $G$, en rangeant les sommets dans l'ordre alphabétique.

b. Que représente la somme des coefficients d'une ligne de $A$ ? Vérifier sur la ligne de B.

c. Réciproquement, dessiner le graphe dont les sommets sont $S_1$, $S_2$, $S_3$, $S_4$ et dont la matrice d'adjacence est

$$M=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 1\\ 0& 1& 0& 0\\ 1& 1& 0& 0\end{array}\right)$$

Le graphe ci-dessous représente un réseau informatique : les sommets A, B, C, D sont des serveurs, et chaque arête est une liaison directe entre deux serveurs.

Sa matrice d'adjacence, dans l'ordre alphabétique des sommets, est

$$A=\left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 0\\ 1& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right)$$

a. Calculer $A^2$.

b. Interpréter le coefficient de $A^2$ situé à la ligne de B et à la colonne de D, puis lister explicitement les chaînes correspondantes.

c. Que représente le coefficient diagonal de $A^2$ situé à la ligne de A ? Justifier sans calcul supplémentaire.

d. Combien existe-t-il de chaînes de longueur $3$ reliant B à D ? On calculera uniquement le coefficient utile de $A^3$, puis on listera ces chaînes.

Soit $G$ un graphe dont les sommets sont numérotés de $1$ à $p$, et soit $A=(a_{ij})$ sa matrice d'adjacence. Pour tout entier $n⩾1$, on note $a_{ij}^{(n)}$ le coefficient de la matrice $A^n$ situé à la ligne $i$ et à la colonne $j$.

On souhaite démontrer par récurrence la propriété ${\mathcal{P}}_n$ : « pour tous sommets $i$ et $j$, le coefficient $a_{ij}^{(n)}$ est égal au nombre de chaînes de longueur $n$ reliant $i$ à $j$ ».

a. Initialisation. Justifier que ${\mathcal{P}}_1$ est vraie. Que vaut $a_{ij}$ selon que les sommets $i$ et $j$ sont adjacents ou non, et qu'est-ce qu'une chaîne de longueur $1$ de $i$ à $j$ ?

b. Hérédité. Soit $n⩾1$ tel que ${\mathcal{P}}_n$ est vraie. En utilisant $A^{n+1}=A^n\cdot A$, justifier que pour tous sommets $i$ et $j$ :

$$a_{ij}^{(n+1)}=\sum _{k=1}^p{a}_{ik}^{(n)}{a}_{kj}$$

c. Expliquer pourquoi, pour un sommet $k$ fixé, le produit $a_{ik}^{(n)}{a}_{kj}$ compte exactement les chaînes de longueur $n+1$ de $i$ à $j$ dont l'avant-dernier sommet est $k$.

d. Conclure la démonstration.

Au XVIIIe siècle, la ville de Königsberg était traversée par une rivière enjambée par sept ponts, reliant la rive nord (N), la rive sud (S), une île centrale (I) et une île à l'est (E). Les habitants se demandaient s'il était possible de se promener en traversant chaque pont exactement une fois. En 1736, Leonhard Euler résolut ce problème en inventant la théorie des graphes : on modélise la ville par le multigraphe ci-dessous, où chaque arête représente un pont.

Les ponts sont : deux ponts entre N et I, deux ponts entre S et I, un pont N–E, un pont S–E et un pont I–E.

a. Déterminer le degré de chaque sommet.

b. La promenade souhaitée par les habitants revient à trouver une chaîne eulérienne dans ce graphe. Est-elle possible ? Justifier à l'aide du théorème d'Euler.

c. La municipalité détruit le pont I–E, puis construit un nouveau pont reliant directement N et S. Déterminer les nouveaux degrés des sommets. La promenade devient-elle possible ? Si oui, peut-on de plus revenir à son point de départ ?

On souhaite tracer la figure ci-dessous (« l'enveloppe ») sans lever le crayon et sans repasser deux fois sur le même trait. On la modélise par un graphe à cinq sommets A, B, C, D, E dont les arêtes sont les huit traits de la figure : A–B, A–C, A–D, B–C, B–D, C–D, C–E et D–E.

a. Déterminer le degré de chaque sommet, et vérifier la cohérence avec le nombre d'arêtes.

b. Traduire le problème du tracé en termes de graphes : que cherche-t-on exactement ?

c. Un tel tracé est-il possible ? Si oui, quels sont les points de départ et d'arrivée possibles ? Justifier.

d. Donner explicitement un tracé qui convient, en vérifiant que chaque trait est utilisé exactement une fois.

e. Expliquer pourquoi il est impossible de réussir le tracé en partant du sommet E.

Deux opérateurs de téléphonie mobile, Alpha et Bêta, se partagent le marché d'une région. On observe le comportement des clients d'une année sur l'autre :

• chaque année, $90\mathrm{\%}$ des clients d'Alpha restent chez Alpha, et les $10\mathrm{\%}$ restants partent chez Bêta ;
• chaque année, $70\mathrm{\%}$ des clients de Bêta restent chez Bêta, et les $30\mathrm{\%}$ restants passent chez Alpha.

On suppose que ces proportions restent les mêmes chaque année et qu'aucun client ne quitte le marché.

1. Justifier que la situation peut se modéliser par une chaîne de Markov à deux états. On précisera quels sont les états.

2. Dessiner le graphe orienté pondéré associé à cette chaîne de Markov.

3. Écrire la matrice de transition $P$ de la chaîne, en prenant les états dans l'ordre (Alpha, Bêta).

4. Que vaut la somme des coefficients de chaque ligne de $P$ ? Expliquer pourquoi ce résultat était prévisible.

Un salarié se rend chaque jour à son travail, soit à vélo (état V), soit en voiture (état T). On observe que :

• s'il vient à vélo un jour, il revient à vélo le lendemain avec probabilité $\mathrm{0,7}$ ;
• s'il vient en voiture un jour, il vient à vélo le lendemain avec probabilité $\mathrm{0,4}$.

On modélise la situation par une chaîne de Markov à deux états, pris dans l'ordre (V, T). Le lundi, considéré comme le jour $0$, il vient à vélo : la distribution initiale est donc ${\pi }_0=\left(\begin{array}{cc}1& 0\end{array}\right)$.

1. Écrire la matrice de transition $P$ de la chaîne.

2. Calculer ${\pi }_1$ puis ${\pi }_2$, les distributions aux jours $1$ et $2$.

3. Quelle est la probabilité que le salarié vienne à vélo le mercredi ?

4. Calculer $P^2$. Interpréter concrètement le coefficient situé ligne V, colonne V de cette matrice.

Deux opérateurs de téléphonie, Alpha et Bêta, se partagent le marché d'une région. Chaque année, $90\mathrm{\%}$ des clients d'Alpha restent chez Alpha et $10\mathrm{\%}$ partent chez Bêta, tandis que $70\mathrm{\%}$ des clients de Bêta restent chez Bêta et $30\mathrm{\%}$ passent chez Alpha. La matrice de transition de la chaîne de Markov associée, les états étant pris dans l'ordre (Alpha, Bêta), est :

$$P=\left(\begin{array}{cc}\mathrm{0,9}& \mathrm{0,1}\\ \mathrm{0,3}& \mathrm{0,7}\end{array}\right)$$

1. On pose $\pi =\left(\begin{array}{cc}x& y\end{array}\right)$ avec $x⩾0$, $y⩾0$ et $x+y=1$. Écrire le système d'équations traduisant la relation $\pi =\pi P$.

2. Résoudre ce système et en déduire la distribution invariante de la chaîne.

3. On admet que la suite des distributions $({\pi }_n)$ converge vers l'unique distribution invariante, quelle que soit la répartition initiale des clients. Interpréter ce résultat pour les deux opérateurs.

Trois plateformes de streaming vidéo, notées A, B et C, se partagent les abonnés d'un pays. On étudie l'évolution des parts d'audience d'un mois au suivant : chaque abonné est inscrit à une seule plateforme et peut changer de plateforme à la fin de chaque mois. Le graphe orienté pondéré ci-dessous décrit les probabilités de transition d'un mois au suivant.

1. À l'aide du graphe, écrire la matrice de transition $P$ de cette chaîne de Markov, les états étant pris dans l'ordre (A, B, C).

2. Vérifier que la somme des coefficients de chaque ligne de $P$ vaut $1$.

3. Au mois $0$, les parts d'audience sont de $50\mathrm{\%}$ pour A, $30\mathrm{\%}$ pour B et $20\mathrm{\%}$ pour C, soit ${\pi }_0=\left(\begin{array}{ccc}\mathrm{0,5}& \mathrm{0,3}& \mathrm{0,2}\end{array}\right)$. Calculer la distribution ${\pi }_1$ au mois $1$.

4. Calculer la distribution ${\pi }_2$ au mois $2$.

5. Commenter l'évolution des parts d'audience des trois plateformes sur ces deux mois.

Une petite ville dispose de trois stations de vélos en libre-service : Gare (G), Mairie (M) et Parc (R). On suit la position d'un vélo d'une journée à la suivante. Chaque jour :

• un vélo stationné à la Gare y reste avec probabilité $\mathrm{0,6}$, part à la Mairie avec probabilité $\mathrm{0,2}$ et au Parc avec probabilité $\mathrm{0,2}$ ;
• un vélo stationné à la Mairie y reste avec probabilité $\mathrm{0,7}$, part à la Gare avec probabilité $\mathrm{0,1}$ et au Parc avec probabilité $\mathrm{0,2}$ ;
• un vélo stationné au Parc y reste avec probabilité $\mathrm{0,7}$, part à la Gare avec probabilité $\mathrm{0,1}$ et à la Mairie avec probabilité $\mathrm{0,2}$.

On modélise la position du vélo par une chaîne de Markov à trois états, pris dans l'ordre (G, M, R).

1. Écrire la matrice de transition $P$ de la chaîne et vérifier que chaque ligne somme à $1$.

2. On pose $\pi =\left(\begin{array}{ccc}x& y& z\end{array}\right)$ avec $x$, $y$, $z$ positifs et $x+y+z=1$. Écrire le système d'équations traduisant la relation $\pi =\pi P$.

3. Résoudre ce système et en déduire la distribution invariante de la chaîne.

4. On admet que la suite des distributions $({\pi }_n)$ converge vers cette distribution invariante. Interpréter le résultat pour l'exploitant du service : comment le parc de vélos se répartit-il à long terme entre les trois stations ?

On considère le graphe ci-dessous : un triangle dont les sommets sont numérotés $1$, $2$ et $3$, avec les arêtes $1$–$2$, $2$–$3$ et $1$–$3$.

Un pion se déplace sur ce graphe : à chaque étape, il quitte le sommet où il se trouve et rejoint l'un des deux sommets voisins, choisi au hasard de façon équiprobable.

1. Justifier que la position du pion définit une chaîne de Markov à trois états, et donner sa matrice de transition $P$, les états étant pris dans l'ordre $(1,2,3)$.

2. Le pion part du sommet $1$ : la distribution initiale est ${\pi }_0=\left(\begin{array}{ccc}1& 0& 0\end{array}\right)$. Calculer ${\pi }_1$ puis ${\pi }_2$.

3. Quelle est la probabilité que le pion revienne au sommet $1$ en exactement deux étapes ?

4. Déterminer la distribution invariante de la chaîne. On pourra s'appuyer sur la symétrie du graphe, puis vérifier par le calcul.

5. Question de synthèse. On note $p_n$ la probabilité que le pion se trouve au sommet $1$ à l'étape $n$.

a. À l'aide de la formule des probabilités totales, montrer que pour tout entier naturel $n$ : $p_{n+1}={\displaystyle \frac{1}{2}}(1-p_n)$.

b. On pose $v_n=p_n-{\displaystyle \frac{1}{3}}$. Montrer que la suite $(v_n)$ est géométrique et en déduire l'expression de $p_n$ en fonction de $n$.

c. Déterminer la limite de $(p_n)$ et commenter le lien avec la question 4.

Deux urnes A et B contiennent à elles deux $2$ boules. À chaque étape, on choisit l'une des $2$ boules au hasard, de façon équiprobable, et on la change d'urne. On s'intéresse au nombre de boules contenues dans l'urne A : ce nombre définit une chaîne de Markov dont les états sont $0$, $1$ et $2$.

Ce modèle, dû aux physiciens Paul et Tatiana Ehrenfest, décrit de façon simplifiée la diffusion d'un gaz entre deux compartiments.

1. Justifier les transitions suivantes : depuis l'état $0$, on passe nécessairement à l'état $1$ ; depuis l'état $1$, on passe à l'état $0$ avec probabilité ${\displaystyle \frac{1}{2}}$ et à l'état $2$ avec probabilité ${\displaystyle \frac{1}{2}}$ ; depuis l'état $2$, on passe nécessairement à l'état $1$. En déduire la matrice de transition $P$, les états étant pris dans l'ordre $(0,1,2)$.

2. Dessiner le graphe orienté pondéré de la chaîne.

3. Au départ, l'urne A est vide : ${\pi }_0=\left(\begin{array}{ccc}1& 0& 0\end{array}\right)$. Calculer ${\pi }_1$, ${\pi }_2$ et ${\pi }_3$.

4. Que remarque-t-on ? La suite des distributions $({\pi }_n)$ converge-t-elle ?

5. Déterminer toutes les distributions invariantes de la chaîne : on posera $\pi =\left(\begin{array}{ccc}x& y& z\end{array}\right)$ et on résoudra le système traduisant $\pi =\pi P$ avec $x+y+z=1$.

6. Interpréter la distribution invariante obtenue : quel est l'état le plus probable en régime stationnaire, et pourquoi cela est-il conforme à l'intuition ?