Devoir surveillé — Graphes et chaînes de Markov

Une collectivité relie cinq sites informatiques, notés A, B, C, D et E, par un réseau de fibres optiques. Ce réseau est modélisé par le graphe non orienté ci-dessous : chaque sommet représente un site, chaque arête une liaison directe en fibre.

Les liaisons existantes sont : A–B, A–C, A–D, B–C, C–D, C–E et D–E.

1. (1 pt) Donner l'ordre du graphe, puis le degré de chacun de ses sommets. Vérifier la cohérence entre la somme des degrés et le nombre d'arêtes.

2. (0,5 pt) Le graphe est-il connexe ? Justifier brièvement.

3. (1 pt) Le graphe est-il complet ? Combien d'arêtes faudrait-il ajouter pour obtenir le graphe complet $K_5$ ? Préciser lesquelles.

4. (1 pt) Écrire la matrice d'adjacence $A$ du graphe, les sommets étant rangés dans l'ordre alphabétique.

5. (1 pt) On ne demande pas de calculer $A^2$ en entier. Calculer à la main le coefficient de $A^2$ situé ligne B, colonne E, en détaillant le produit « ligne par colonne ». Interpréter ce coefficient, puis lister la ou les chaînes de longueur $2$ reliant B à E.

6. (0,5 pt) Déterminer, sans calculer $A^2$, le nombre de chaînes de longueur $2$ reliant C à lui-même. Quelle caractéristique du sommet C retrouve-t-on ainsi ?

Après une chute de neige, un agent municipal doit déneiger toutes les rues d'un quartier. Le plan du quartier est modélisé par le graphe non orienté ci-dessous : les sommets M, N, P, Q et R représentent les carrefours, les arêtes représentent les rues.

Les rues sont : M–N, M–P, N–P, N–Q, P–Q, P–R et Q–R. L'agent souhaite organiser une tournée qui emprunte chaque rue exactement une fois.

1. (1 pt) Question de cours. Énoncer la condition, portant sur les degrés des sommets d'un graphe connexe, qui caractérise l'existence d'une chaîne eulérienne.

2. (1 pt) La tournée souhaitée est-elle possible ? Si oui, de quel(s) carrefour(s) doit-elle nécessairement partir, et où doit-elle s'achever ? Justifier.

3. (1 pt) Proposer explicitement une telle tournée, en listant les carrefours dans l'ordre de passage. On vérifiera que chaque rue est empruntée exactement une fois.

4. (1 pt) La commune envisage de percer une nouvelle rue reliant directement les carrefours M et R. L'agent pourrait-il alors effectuer une tournée fermée (partant d'un carrefour et y revenant) empruntant chaque rue exactement une fois ? Une tournée ouverte resterait-elle seulement possible ? Justifier.

Une salle de sport étudie, mois après mois, l'évolution de ses abonnements au sein d'une population fixe de $1000$ personnes. Chaque personne est, chaque mois, soit abonnée (état $A$), soit non abonnée (état $N$). On observe que, d'un mois au suivant :

• $80\mathrm{\%}$ des abonnés restent abonnés, $20\mathrm{\%}$ résilient ;
• $30\mathrm{\%}$ des non-abonnés s'abonnent, $70\mathrm{\%}$ restent non abonnés.

On modélise la situation par une chaîne de Markov à deux états, dans l'ordre $(A,N)$. Au mois $0$, $40\mathrm{\%}$ de la population est abonnée : la distribution initiale est ${\pi }_0=\left(\begin{array}{cc}\mathrm{0,4}& \mathrm{0,6}\end{array}\right)$. Pour tout entier naturel $n$, on note ${\pi }_n$ la distribution au mois $n$ et $a_n$ la proportion d'abonnés au mois $n$, de sorte que $a_0=\mathrm{0,4}$.

1. (1 pt) Représenter le graphe pondéré associé à cette chaîne de Markov, puis écrire sa matrice de transition $P$.

2. (1 pt) Calculer ${\pi }_1$ puis ${\pi }_2$, en détaillant les calculs.

3. (0,5 pt) En déduire le nombre d'abonnés au mois $2$.

4. (1 pt) À l'aide de la formule des probabilités totales, justifier que pour tout entier naturel $n$ : $a_{n+1}=\mathrm{0,8}{a}_n+\mathrm{0,3}(1-a_n)$, puis en déduire que $a_{n+1}=\mathrm{0,5}{a}_n+\mathrm{0,3}$.

5. (1 pt) On pose, pour tout entier naturel $n$, $v_n=a_n-\mathrm{0,6}$. Montrer que la suite $(v_n)$ est géométrique de raison $\mathrm{0,5}$ et préciser son premier terme $v_0$.

6. (0,5 pt) En déduire l'expression de $a_n$ en fonction de $n$.

7. (0,5 pt) Déterminer la limite de la suite $(a_n)$ et interpréter le résultat dans le contexte de l'exercice.

8. (0,5 pt) Vérifier par le calcul que $\pi =\left(\begin{array}{cc}\mathrm{0,6}& \mathrm{0,4}\end{array}\right)$ est une distribution invariante de la chaîne.

Une machine industrielle est, chaque jour, dans l'un des trois régimes suivants : fonctionnement normal (état $N$), fonctionnement ralenti (état $R$) ou panne (état $P$). On modélise l'évolution du régime, d'un jour au suivant, par une chaîne de Markov dont les états sont rangés dans l'ordre $(N,R,P)$. Les observations de l'exploitant sont les suivantes :

• si la machine fonctionne normalement, elle reste en fonctionnement normal le lendemain avec la probabilité $\mathrm{0,8}$, passe en régime ralenti avec la probabilité $\mathrm{0,1}$ et tombe en panne avec la probabilité $\mathrm{0,1}$ ;
• si elle est en régime ralenti, un réglage la ramène en fonctionnement normal avec la probabilité $\mathrm{0,4}$ ; elle reste au ralenti avec la probabilité $\mathrm{0,45}$ et tombe en panne avec la probabilité $\mathrm{0,15}$ ;
• si elle est en panne, le service de maintenance intervient dans la journée : le lendemain, la machine repart en fonctionnement normal avec la probabilité $\mathrm{0,6}$ ou en régime ralenti avec la probabilité $\mathrm{0,4}$. Elle n'est donc jamais en panne deux jours de suite.

Le jour $0$, la machine fonctionne normalement : la distribution initiale est ${\pi }_0=\left(\begin{array}{ccc}1& 0& 0\end{array}\right)$. Pour tout entier naturel $n$, on note ${\pi }_n$ la distribution au jour $n$.

1. (1 pt) Écrire la matrice de transition $P$ de la chaîne. Vérifier que la somme des coefficients de chaque ligne vaut $1$.

2. (0,5 pt) Représenter le graphe pondéré associé à cette chaîne de Markov.

3. (1,5 pt) Calculer ${\pi }_1$ puis ${\pi }_2$, en détaillant les calculs.

4. (0,5 pt) En déduire la probabilité que la machine soit en panne le jour $2$.

5. (1,5 pt) On admet que la suite $({\pi }_n)$ converge vers l'unique distribution invariante $\pi =\left(\begin{array}{ccc}x& y& z\end{array}\right)$ de la chaîne. Écrire le système vérifié par $x$, $y$ et $z$ (sans oublier la condition $x+y+z=1$), le résoudre, puis interpréter le résultat pour l'exploitant de la machine.