Exercices de Graphes, Terminale (page 3)

On considère une chaîne de Markov homogène sur un espace fini d'états $\{1,2,\dots ,s\}$ avec $s\in \{2,3\}$. On note $P=(p_{ij}{)}_{1⩽i,j⩽s}$ sa matrice de transition, où $p_{ij}=P(X_{n+1}=j\mid X_n=i)$. Pour tout $n\in \mathbb{N}$, on note ${\pi }_n=\left(\begin{array}{ccc}P(X_n=1)& \dots & P(X_n=s)\end{array}\right)$ la matrice ligne représentant la distribution à l'étape $n$.

Un mobile se déplace sur les trois sommets $A,B$ et $C$ d'un triangle selon une marche aléatoire. À chaque seconde, le mobile effectue un saut vers l'un des deux autres sommets selon les règles suivantes :
- Lorsqu'il se trouve en $A$, il saute vers $B$ avec une probabilité de $\frac{2}{3}$, et vers $C$ avec une probabilité de $\frac{1}{3}$.
- Lorsqu'il se trouve en $B$, il saute vers $A$ avec une probabilité de $\frac{1}{2}$, et vers $C$ avec une probabilité de $\frac{1}{2}$.
- Lorsqu'il se trouve en $C$, il saute vers $A$ avec une probabilité de $\frac{3}{4}$, et vers $B$ avec une probabilité de $\frac{1}{4}$.
Le mobile ne reste jamais sur place lors d'un saut.

On étudie une version simplifiée du modèle de diffusion d'Ehrenfest comprenant deux compartiments communicants $U_1$ et $U_2$ et deux particules. À chaque étape temporelle, l'une des deux particules est choisie au hasard avec équiprobabilité et transférée dans l'autre compartiment. L'état du système à l'étape $n$ est défini par le nombre $X_n$ de particules présentes dans le compartiment $U_1$. Les états possibles sont donc $0,1$ et $2$.

On modélise un micro-réseau internet constitué de trois pages web notées $A,B$ et $C$. Un internaute virtuel navigue aléatoirement d'une page à l'autre selon les règles du modèle PageRank sans téléportation :
- Depuis la page $A$, deux liens pointent vers les pages $B$ et $C$. L'internaute choisit chacun d'eux avec probabilité $0,5$.
- Depuis la page $B$, un unique lien pointe vers la page $C$. L'internaute se rend en $C$ avec certitude (probabilité $1$).
- Depuis la page $C$, un unique lien pointe vers la page $A$. L'internaute se rend en $A$ avec certitude (probabilité $1$).

Un réseau de télécommunications comporte cinq nœuds de commutation numérotés de $1$ à $5$. La matrice d'adjacence des connexions directes est :$$M=\left(\begin{array}{ccccc}0& 1& 1& 0& 1\\ 1& 0& 1& 1& 0\\ 1& 1& 0& 1& 1\\ 0& 1& 1& 0& 1\\ 1& 0& 1& 1& 0\end{array}\right)$$Le calcul de la puissance quatrième de la matrice $M$ fournit le résultat suivant :$$M^4=\left(\begin{array}{ccccc}24& 16& 24& 24& 16\\ 16& 24& 24& 16& 24\\ 24& 24& 32& 24& 24\\ 24& 16& 24& 24& 16\\ 16& 24& 24& 16& 24\end{array}\right)$$

Une particule se déplace sur un segment discret constitué de trois cases adjacentes notées $1,2$ et $3$. À chaque seconde, la particule effectue un déplacement selon les règles probabilistes suivantes :
- Si elle se trouve en position 1 (bord gauche), elle avance en 2 avec une probabilité de $0,8$, et reste en 1 avec une probabilité de $0,2$.
- Si elle se trouve en position 2 (centre), elle recule en 1 avec une probabilité de $0,4$, et avance en 3 avec une probabilité de $0,6$.
- Si elle se trouve en position 3 (bord droit), elle recule en 2 avec une probabilité de $0,7$, et reste en 3 avec une probabilité de $0,3$.

On considère un réseau de surveillance environnementale modélisé par un graphe simple non orienté $G$ comportant 6 stations notées $A,B,C,D,E$ et $F$.
Les liaisons de communication existantes entre ces stations sont données par les arêtes suivantes : $AB,BC,CD,DE,EA$ et $AC$.

Soit $G$ un graphe simple non orienté dont les sommets sont ordonnés sous la forme $(S_1,S_2,S_3,S_4)$.
On note $M$ la matrice d'adjacence associée à $G$ :$$M=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 1\\ 0& 1& 0& 1\\ 1& 1& 1& 0\end{array}\right)$$

Un robot de nettoyage autonome évolue chaque heure entre deux modes : le mode Nettoyage (noté $N$) et le mode Recharge (noté $R$).
- Lorsqu'il est en mode Nettoyage, il y reste l'heure suivante avec une probabilité de $0,75$, sinon il bascule en mode Recharge.
- Lorsqu'il est en mode Recharge, il reste en recharge l'heure suivante avec une probabilité de $0,40$, sinon il reprend le nettoyage.

Dans une chaîne d'assemblage automatisée, une pièce peut être dans l'un des trois états suivants : Conforme ($C$), En retouche ($R$) ou Défectueuse définitive ($D$).
L'évolution horaire de l'état de la pièce est modélisée par la matrice de transition suivante, les états étant rangés dans l'ordre $(C,R,D)$ :$$P=\left(\begin{array}{ccc}0,88& 0,10& 0,02\\ 0,65& 0,25& 0,10\\ 0& 0& 1\end{array}\right)$$

Une plateforme éducative en ligne propose deux parcours d'entraînement : Découverte ($D$) et Approfondissement ($A$).
D'une semaine à la suivante, les choix des apprenants sont modélisés par la matrice de transition $P$, les états étant ordonnés selon $(D,A)$ :$$P=\left(\begin{array}{cc}0,60& 0,40\\ 0,15& 0,85\end{array}\right)$$À la rentrée (semaine 0), tous les apprenants s'inscrivent dans le parcours Découverte. La distribution initiale est donc représentée par la matrice ligne ${\pi }_0=\left(\begin{array}{cc}1& 0\end{array}\right)$.

Un complexe de recherche est composé de 5 laboratoires désignés par les lettres $A,B,C,D$ et $E$.
Des passerelles piétonnes directes permettent de circuler dans les deux sens entre certains laboratoires. Le graphe $G$ associé a pour arêtes : $AB,BC,CD,BE$ et $DE$.

Un réseau fluvial reliant 4 étangs notés $E_1,E_2,E_3$ et $E_4$ est aménagé avec des écluses imposant un sens unique d'écoulement.
Les canaux orientés sont les suivants : de $E_1$ vers $E_2$ et vers $E_3$ ; de $E_2$ vers $E_4$ ; de $E_3$ vers $E_2$ et vers $E_4$ ; de $E_4$ vers $E_1$.

On considère un graphe simple non orienté à 4 sommets $S_1,S_2,S_3,S_4$ dont la matrice d'adjacence est donnée par :$$M=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right)$$

Une compagnie aérienne régionale assure des liaisons directes entre 4 villes notées $A,B,C$ et $D$.
La matrice d'adjacence associée à ce réseau est :$$M=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 0& 1\\ 1& 0& 0& 1\\ 0& 1& 1& 0\end{array}\right)$$On donne les puissances calculées de cette matrice :$$M^2=\left(\begin{array}{cccc}2& 0& 0& 2\\ 0& 2& 2& 0\\ 0& 2& 2& 0\\ 2& 0& 0& 2\end{array}\right)\text{et}{M}^3=\left(\begin{array}{cccc}0& 4& 4& 0\\ 4& 0& 0& 4\\ 4& 0& 0& 4\\ 0& 4& 4& 0\end{array}\right)$$

La qualité d'une parcelle agricole est évaluée chaque année selon deux états : Enrichi ($E$) ou Neutre ($N$).
L'évolution d'une année sur l'autre est modélisée par une chaîne de Markov dont la matrice de transition est, pour l'ordre $(E,N)$ :$$P=\left(\begin{array}{cc}0,7& 0,3\\ 0,4& 0,6\end{array}\right)$$Au départ (année 0), le sol de la parcelle est dans l'état Neutre. La distribution initiale est donc ${\pi }_0=\left(\begin{array}{cc}0& 1\end{array}\right)$.
On admet que :$$P^2=\left(\begin{array}{cc}0,61& 0,39\\ 0,52& 0,48\end{array}\right)$$

Un opérateur de télécommunications doit raccorder une station côtière $S$ à une île $I$ en déployant un câble sous-marin qui peut transiter par trois relais intermédiaires notés $A,B$ et $C$.
Le réseau des connexions possibles est un graphe pondéré non orienté dont les arêtes portent les coûts d'installation (exprimés en milliers d'euros) :
- Liaisons issues de $S$ : $SA$ (coût 14) et $SB$ (coût 18) ;
- Liaisons entre relais : $AB$ (coût 6), $AC$ (coût 20) et $BC$ (coût 11) ;
- Liaisons vers $I$ : $AI$ (coût 35), $BI$ (coût 26) et $CI$ (coût 12).

Un institut de sondage étudie les abonnements d'un quotidien proposé sous deux formats : Papier ($P$) et Numérique ($N$).
Un rapport provisoire présente le tableau d'évolution annuel suivant sous forme matricielle pour les états ordonnés $(P,N)$ :$$M=\left(\begin{array}{cc}0,75& 0,40\\ 0,25& 0,60\end{array}\right)$$

Deux opérateurs de recharge de véhicules électriques, Voltix ($V$) et Ampère ($A$), se partagent les usagers d'une métropole.
D'un mois sur l'autre :
- un client de Voltix lui reste fidèle avec une probabilité de $0,80$, ou s'abonne chez Ampère avec une probabilité de $0,20$ ;
- un client d'Ampère lui reste fidèle avec une probabilité de $0,70$, ou rejoint Voltix avec une probabilité de $0,30$.

Une infrastructure cloud répartit le traitement de ses requêtes entre trois centres de données situés à Paris ($P$), Lyon ($L$) et Marseille ($M$).
Chaque seconde, une requête est réorientée d'un centre vers un autre selon la matrice de transition suivante, les états étant ordonnés dans l'ordre $(P,L,M)$ :$$T=\left(\begin{array}{ccc}0,5& 0,3& 0,2\\ 0,2& 0,6& 0,2\\ 0,3& 0,3& 0,4\end{array}\right)$$

On considère une chaîne de Markov à deux états $E_1$ et $E_2$ dont la matrice de transition est :$$P=\left(\begin{array}{cc}0,75& 0,25\\ 0,15& 0,85\end{array}\right)$$Pour tout entier naturel $n$, on note ${\pi }_n=\left(\begin{array}{cc}{p}_n& q_n\end{array}\right)$ la distribution à l'étape $n$, où $p_n$ est la probabilité de se trouver dans l'état $E_1$ et $q_n=1-p_n$.
Au départ, le système est dans l'état $E_1$, de sorte que $p_0=1$.

Un service municipal organise la collecte des déchets dans un éco-quartier formé de 6 carrefours notés $A,B,C,D,E$ et $F$.
Les rues à double sens reliant ces carrefours sont modélisées par les arêtes du graphe non orienté $G$ suivant : $AB,BC,CD,DE,EF,FA,AE,BD$ et $CF$.

Un équipementier industriel compare deux politiques préventives de maintenance pour un compresseur pouvant se trouver dans deux états : Bon état ($B$) ou Dégradé ($D$).
- Dans le cadre de la politique 1 (inspection mensuelle simple), la matrice de transition s'écrit, pour l'ordre $(B,D)$ :$$P_1=\left(\begin{array}{cc}0,85& 0,15\\ 0,60& 0,40\end{array}\right)$$- Dans le cadre de la politique 2 (remplacement systématique des pièces d'usure), la matrice de transition s'écrit :$$P_2=\left(\begin{array}{cc}0,92& 0,08\\ 0,48& 0,52\end{array}\right)$$

Soit $G$ un graphe d'ordre $p⩾2$ dont les sommets sont notés $S_1,S_2,\dots ,S_p$.
On note $A=(a_{ij}{)}_{1⩽i,j⩽p}$ sa matrice d'adjacence, où $a_{ij}$ désigne le nombre d'arêtes (ou d'arcs) reliant $S_i$ à $S_j$.
L'objectif de cet exercice est d'établir la démonstration exigible du programme officiel :
Pour tout entier naturel $n⩾1$, le nombre de chaînes (ou chemins) de longueur $n$ reliant le sommet $S_i$ au sommet $S_j$ est égal au coefficient situé sur la ligne $i$ et la colonne $j$ de la matrice $A^n$, noté $(A^n{)}_{ij}$.

On considère une chaîne de Markov homogène à $p$ états ($p\in \{2,3\}$) de matrice de transition $P$.
On note ${\pi }_n$ la matrice ligne représentant la distribution de probabilité sur les états à l'instant $n\in \mathbb{N}$.
On rappelle que la relation de transition d'une étape à la suivante est : ${\pi }_{n+1}={\pi }_{n}P$.

Un moteur de recherche classe trois pages web notées $P_1,P_2,P_3$ reliées par des hyperliens selon le modèle élémentaire du PageRank.
On suppose qu'un internaute parcourt le web aléatoirement : lorsqu'il consulte une page, il clique de façon équiprobable sur l'un des hyperliens sortants de cette page.
Les liens sortants existants sont :
- La page $P_1$ contient des liens pointant vers $P_2$ et vers $P_3$ ;
- La page $P_2$ contient un seul lien pointant vers $P_3$ ;
- La page $P_3$ contient un seul lien pointant vers $P_1$.

On modélise la diffusion de deux particules de gaz réparties entre deux récipients communicants $A$ et $B$.
À chaque seconde, l'une des deux particules est choisie au hasard avec équiprobabilité et transférée dans l'autre récipient.
L'état du système à la seconde $n$ est modélisé par le nombre de particules présentes dans le récipient $A$, noté $X_n$. Les états possibles sont donc 0, 1 ou 2.

Quatre salles d'un musée, notées $A$, $B$, $C$ et $D$, sont reliées par des couloirs : $AB$, $BC$, $CD$ et $BD$. On modélise le musée par un graphe non orienté $G$ dont les sommets sont les salles et les arêtes les couloirs.

1. Écrire la matrice d'adjacence $M$ de $G$, les sommets étant rangés dans l'ordre alphabétique.
2. À la calculatrice, calculer la matrice $S=M+M^2+M^3$.
3. En déduire que le graphe $G$ est connexe. Pourquoi est-il inutile de calculer $M^4$ ?
4. Un jour de travaux, le couloir $AB$ est fermé. On note $M^{\prime }$ la matrice d'adjacence du nouveau graphe $G^{\prime }$ et $S^{\prime }=M^{\prime }+M^{\prime 2}+M^{\prime 3}$. Calculer $S^{\prime }$ et conclure sur la connexité de $G^{\prime }$.

Cinq stations de mesure, notées $A$, $B$, $C$, $D$ et $E$, communiquent par radio. Les liaisons existantes sont : $AB$, $BC$, $CA$ et $DE$. On modélise le réseau par un graphe non orienté $\Gamma$, et on note $N$ sa matrice d'adjacence (sommets dans l'ordre alphabétique).

1. Écrire $N$.
2. À la calculatrice, calculer $S=N+N^2+N^3+N^4$.
3. Le réseau permet-il à toute station de communiquer, directement ou par relais, avec toute autre ? Justifier à l'aide de $S$ et préciser quels sont les groupes de stations qui communiquent entre eux.
4. On installe une nouvelle liaison $CD$. Sans refaire de calcul, que peut-on dire de l'effet sur $S$ ? Vérifier en calculant la nouvelle matrice $S_1$ à la calculatrice.

Une ville est composée de deux îlots reliés par un pont. Le premier îlot compte trois places $A$, $B$, $C$ reliées deux à deux par des rues ($AB$, $BC$, $CA$). Le second îlot compte trois places $D$, $E$, $F$ reliées deux à deux par des rues ($DE$, $EF$, $FD$). Un pont relie les places $C$ et $D$ ($CD$). On modélise la ville par un graphe dont les sommets sont les places et les arêtes les rues et le pont.

1. Déterminer le degré de chaque sommet.
2. Justifier qu'il existe une chaîne eulérienne et préciser par quel(s) sommet(s) elle commence et se termine.
3. On part de $C$. Expliquer pourquoi la première arête empruntée ne doit pas être $CD$.
4. Construire une chaîne eulérienne en écrivant, arête par arête, la suite des sommets parcourus.

Un service de voirie doit déneiger les rues d'un quartier en passant exactement une fois dans chaque rue, puis revenir à son point de départ. Le quartier est constitué de deux îlots carrés qui se touchent en un carrefour $C$ : le premier îlot est le circuit $ABCD$ (rues $AB$, $BC$, $CD$, $DA$) et le second le circuit $CEFG$ (rues $CE$, $EF$, $FG$, $GC$).

1. Justifier qu'un circuit de déneigement existe, c'est-à-dire qu'il existe un cycle eulérien.
2. Le chauffeur part de $A$ et emprunte successivement $AB$ puis $BC$. Quelles arêtes sont alors disponibles en $C$ ? Laquelle est un pont du graphe restant à parcourir ? Pourquoi faut-il l'éviter pour l'instant ?
3. Construire un cycle eulérien complet partant de $A$, en écrivant la suite des sommets.
4. Combien d'arêtes comporte ce cycle ? Vérifier que ce nombre est cohérent avec le graphe.

Un parc comporte un jardin carré dont les quatre carrefours sont $A$, $B$, $C$, $D$ (allées $AB$, $BC$, $CD$, $DA$), prolongé depuis $D$ par un sentier $DE$ puis $EF$ qui mène à la sortie $F$. On modélise le parc par un graphe dont les sommets sont les carrefours et les arêtes les allées et sentiers. On souhaite parcourir chaque allée et chaque sentier exactement une fois.

1. Montrer qu'il existe une chaîne eulérienne et préciser ses extrémités possibles.
2. Camille part de $D$, emprunte $DE$ puis $EF$ et se retrouve bloquée en $F$ alors qu'il reste des allées à parcourir. Expliquer son erreur en nommant l'arête qu'elle n'aurait pas dû emprunter en premier.
3. Construire une chaîne eulérienne partant de $D$, arête par arête.
4. Que se passe-t-il si l'on part de $F$ ? Écrire une chaîne eulérienne partant de $F$ et expliquer pourquoi la difficulté de la question 2 n'apparaît plus.