Exercices de Graphes, Terminale

2) Deux espèces placées dans le même aquarium doivent pouvoir cohabiter : deux sommets reliés par une arête dans le graphe d'incompatibilité de la question 1 ne doivent jamais se retrouver dans le même aquarium.
Proposer une répartition des huit espèces dans quatre aquariums qui respecte cette contrainte, en la justifiant à l'aide du graphe.

Une assurance automobile propose à ses clients un contrat dont les tarifs dépendent des accidents déclarés et responsables. Il existe trois catégories de tarifs : Bas, Intermédiaire et Haut.

La réglementation est la suivante :
- La première année, l'assuré paie le tarif Intermédiaire.
- Sans accident déclaré pendant une année, il passe au tarif inférieur (sauf dans le cas où il est déjà au tarif le plus bas).
- Si l'assuré déclare au moins un accident responsable durant une année, il passe au tarif supérieur (sauf dans le cas où il est déjà au tarif le plus haut).

Une étude récente réalisée par l'assurance montre qu'un assuré pris au hasard a une probabilité de 10% d'être responsable d'au moins un accident au cours d'une année.

Le graphe probabiliste ci-dessous traduit l'évolution du tarif payé par un assuré pris au hasard. Compléter ce graphe par les probabilités de passer d'un tarif à l'autre.

On note $b_n$, $i_n$ et $h_n$ les probabilités qu'un assuré pris au hasard l'année $n$ soit respectivement au tarif Bas, Intermédiaire et Haut. Construire un arbre de probabilité résumant les probabilités de transition de l'année $n$ à l'année $n+1$.

On note $P_n=(b_n{i}_n{h}_n)$ la matrice ligne des probabilités après l'année $n$.
Déterminer la matrice de transition $T$ tel que : $P_{n+1}=P_n\times T$.

En admettant la convergence de $P_n$, déterminer la matrice limite $P=(bih)$ définissant l'état stable et en déduire quelle sera à long terme la répartition des assurés entre les trois catégories de tarif.
Aide : On rappelle que : $b+i+h=1$.

Sur la carte des 13 régions de France métropolitaine (découpage en vigueur depuis 2016), on souhaite colorer chaque région de telle sorte que deux régions voisines ne soient pas de la même couleur.

1)

2) On cherche à colorer la carte de sorte que deux régions voisines, c'est-à-dire deux sommets adjacents du graphe de la question 1, n'aient jamais la même couleur.

Au Pays Maudit, la météo est assez simple : soit il fait beau (noté B), soit il pleut (noté P) ou soit il grêle (noté G).
Le temps passe d'un état à un autre en respectant invariablement les règles suivantes :
- S'il fait beau un jour, il ne fera pas beau le lendemain et il y a autant de chances qu'il pleuve ou qu'il grêle.
- S'il pleut ou s'il grêle, il y a une chance sur deux qu'il fasse le même temps le lendemain et une chance sur quatre qu'il fasse beau le lendemain.

S'il grêle aujourd'hui, quel temps fera-t-il demain ? Répondre en utilisant un arbre de probabilité.

Construire le graphe probabiliste (sommets $B$, $P$, $G$) résumant la situation.

On note $b_n$, $p_n$ et $g_n$ les probabilités respectives qu'au $n$-ième jour il fasse beau avec une probabilité $b_n$, qu'il pleuve avec une probabilité $p_n$ et qu'il grêle avec une probabilité $g_n$.
Construire un arbre de probabilité résumant les probabilités de transition du jour $n$ au jour $n+1$.

On considère un graphe simple non orienté d'ordre 5 dont les sommets sont notés $A,B,C,D,E$.
Les arêtes de ce graphe sont $AB,AC,BC,CD$ et $DE$.
1. Déterminer le degré de chacun des sommets de ce graphe.
2. Ce graphe est-il complet ? Justifier la réponse.

Soit $G$ un graphe simple non orienté d'ordre 4 dont les sommets sont notés $S_1,S_2,S_3,S_4$.
Les arêtes de $G$ sont $S_1{S}_2,S_1{S}_3,S_2{S}_3,S_2{S}_4$ et $S_3{S}_4$.
Donner la matrice d'adjacence $M$ associée au graphe $G$, les sommets étant ordonnés selon leurs indices croissants.

Un réseau local de communication relie 6 ordinateurs notés de $C_1$ à $C_6$.
On modélise ce réseau par un graphe non orienté où chaque ordinateur est un sommet et chaque câble direct est une arête.
Les degrés respectifs des sommets sont : $\mathrm{deg}(C_1)=3$, $\mathrm{deg}(C_2)=3$, $\mathrm{deg}(C_3)=2$, $\mathrm{deg}(C_4)=4$, $\mathrm{deg}(C_5)=2$ et $\mathrm{deg}(C_6)=2$.
1. Calculer la somme des degrés des sommets de ce graphe.
2. En déduire le nombre total d'arêtes reliant ces ordinateurs.

Une équipe technique souhaite relier 5 capteurs autonomes de telle sorte que leurs degrés de connexion respectifs soient exactement $3,3,3,2$ et $2$.
Est-il possible de réaliser un tel graphe ? Justifier soigneusement la réponse à l'aide d'un théorème du cours.

Un équipement industriel peut se trouver chaque matin dans l'un des deux états suivants : en service ($S$) ou en veille ($V$).
L'observation statistique montre que :
- S'il est en service un matin, la probabilité qu'il soit encore en service le lendemain est de $0,80$, et qu'il passe en veille de $0,20$.
- S'il est en veille un matin, la probabilité qu'il soit remis en service le lendemain est de $0,65$, et qu'il reste en veille de $0,35$.
Déterminer la matrice de transition $P$ de cette chaîne de Markov, les états étant ordonnés dans l'ordre $(S,V)$.

Un service météorologique classe le temps quotidien d'un massif montagneux selon trois états : Beau ($B$), Variable ($V$) ou Neigeux ($N$).
Les probabilités conditionnelles de transition d'un jour au lendemain sont les suivantes :
- Après un jour Beau : probabilité $0,7$ d'avoir Beau le lendemain, $0,2$ d'avoir Variable, et $0,1$ d'avoir Neigeux.
- Après un jour Variable : probabilité $0,3$ d'avoir Beau le lendemain, $0,4$ d'avoir Variable, et $0,3$ d'avoir Neigeux.
- Après un jour Neigeux : probabilité $0,1$ d'avoir Beau le lendemain, $0,5$ d'avoir Variable, et $0,4$ d'avoir Neigeux.
Écrire la matrice de transition $P$ associée à cette chaîne de Markov, les états étant ordonnés dans l'ordre $(B,V,N)$.

On considère la matrice suivante associée aux deux états $E_1$ et $E_2$ d'un processus stochastique :$$T=\left(\begin{array}{cc}0,45& 0,55\\ 0,30& 0,70\end{array}\right)$$1. Justifier que la matrice $T$ est une matrice stochastique par lignes.
2. Interpréter concrètement le coefficient situé à la deuxième ligne et première colonne de la matrice $T$.

Un lecteur emprunte chaque mois soit un roman ($R$), soit une bande dessinée ($B$).
L'évolution de ses choix d'un mois sur l'autre est modélisée par une chaîne de Markov dont la matrice de transition pour les états rangés dans l'ordre $(R,B)$ est :$$P=\left(\begin{array}{cc}0,6& 0,4\\ 0,3& 0,7\end{array}\right)$$Le premier mois ($n=0$), le lecteur emprunte avec certitude une bande dessinée, ce qui est représenté par la matrice ligne ${\pi }_0=\left(\begin{array}{cc}0& 1\end{array}\right)$.
Calculer la matrice ligne ${\pi }_1$ représentant la distribution de probabilité au mois 1 et interpréter les résultats.

Un réseau de distribution électrique relie six postes de transformation notés $A,B,C,D,E,F$.
Les lignes électriques directes existantes sont $AB,BC,CD,DA$ d'une part, et $EF$ d'autre part.
1. Le graphe non orienté représentant ce réseau est-il connexe ? Justifier rigoureusement.
2. On installe une nouvelle ligne électrique reliant les postes $C$ et $E$. Le graphe devient-il connexe ? Si oui, donner une chaîne reliant le poste $A$ au poste $F$ et préciser sa longueur.

On considère un graphe orienté dont les sommets sont numérotés $1,2,3,4$.
Les liaisons orientées (arcs) sont les suivantes : $(1,2),(1,3),(2,4),(3,2),(3,4)$ et $(4,1)$.
1. Écrire la matrice d'adjacence orientée $A$ associée à ce graphe.
2. Justifier par un exemple que la matrice $A$ n'est pas symétrique et interpréter ce fait en termes de circulation.

Soit $G$ le graphe non orienté d'ordre 4 dont les sommets sont $A,B,C,D$ et les arêtes sont $AB,BC,CD,DA$ et $AC$.
1. Écrire la matrice d'adjacence $M$ associée dans l'ordre $(A,B,C,D)$.
2. Calculer la matrice $M^2$.
3. En déduire le nombre de chaînes de longueur 2 reliant le sommet $A$ au sommet $D$. Confirmer le résultat en citant explicitement la ou les chaînes.

Un réseau informatique relie 4 serveurs $P_1,P_2,P_3,P_4$. La matrice d'adjacence orientée du réseau est :$$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 1& 1\\ 1& 0& 0& 1\\ 0& 1& 0& 0\end{array}\right)$$On dispose du calcul de la puissance 3 de cette matrice :$$A^3=\left(\begin{array}{cccc}1& 3& 1& 1\\ 0& 2& 2& 1\\ 1& 0& 2& 3\\ 1& 1& 0& 1\end{array}\right)$$1. Combien existe-t-il de chemins orientés de longueur 3 permettant de transmettre un paquet du serveur $P_1$ au serveur $P_2$ ?
2. Combien existe-t-il de chemins orientés de longueur 3 reliant le serveur $P_2$ au serveur $P_3$ ?
3. Combien existe-t-il de circuits orientés fermés de longueur 3 partant du serveur $P_3$ et revenant au serveur $P_3$ ?

Deux opérateurs de téléphonie mobile $A$ et $B$ se partagent l'ensemble d'un marché régional captif. Chaque année :
- $10\%$ des clients de l'opérateur $A$ migrent vers l'opérateur $B$ ;
- $20\%$ des clients de l'opérateur $B$ migrent vers l'opérateur $A$.
La matrice de transition dans l'ordre $(A,B)$ est $P=\left(\begin{array}{cc}0,90& 0,10\\ 0,20& 0,80\end{array}\right)$.
À l'année initiale ($n=0$), les parts de marché respectives sont de $40\%$ pour $A$ et $60\%$ pour $B$, soit ${\pi }_0=\left(\begin{array}{cc}0,40& 0,60\end{array}\right)$.
1. Calculer la distribution de probabilité ${\pi }_1$ au bout d'un an.
2. Calculer la distribution de probabilité ${\pi }_2$ au bout de deux ans et interpréter les parts de marché obtenues.

Un transporteur de fret doit acheminer un chargement d'un dépôt $A$ vers un destinataire $E$.
Le réseau routier est modélisé par un graphe pondéré de sommets $A,B,C,D,E$ dont les liaisons et coûts associés (en dizaines d'euros) sont :
- $AB$ : 5 ; $AC$ : 8 ;
- $BD$ : 6 ; $BC$ : 2 ;
- $CD$ : 3 ; $CE$ : 7 ;
- $DE$ : 4.
Déterminer par une énumération exhaustive et raisonnée l'ensemble des chemins simples reliant $A$ à $E$, puis en déduire l'itinéraire de coût minimal et la valeur de ce coût.

Une plateforme de vidéo à la demande propose deux types d'abonnements : Standard ($S$) et Premium ($P$).
L'observation mensuelle du comportement des abonnés montre que :
- $85\%$ des abonnés Standard restent en formule Standard le mois suivant, et $15\%$ basculent vers la formule Premium ;
- $90\%$ des abonnés Premium conservent leur abonnement Premium le mois suivant, et $10\%$ passent en formule Standard.
1. Représenter la situation à l'aide d'un graphe probabiliste à 2 états en précisant la valeur de chaque transition.
2. Écrire la matrice de transition $M$ associée dans l'ordre $(S,P)$.
3. Au lancement du service, l'ensemble des clients souscrit la formule Standard, de sorte que ${\pi }_0=\left(\begin{array}{cc}1& 0\end{array}\right)$. Déterminer la répartition des clients au bout d'un mois.

Un élève ingénieur propose la matrice suivante pour décrire les probabilités de déplacement entre trois zones $Z_1,Z_2,Z_3$ :$$Q=\left(\begin{array}{ccc}0,5& 0,3& 0,1\\ 0,4& 0,5& 0,2\\ 0,1& 0,2& 0,7\end{array}\right)$$1. Calculer la somme des coefficients de la première ligne de la matrice $Q$. En déduire pourquoi $Q$ ne respecte pas la convention des matrices de transition adoptée en cours.
2. En analysant son travail, on réalise que l'élève a organisé les états de départ selon les colonnes. Proposer la matrice de transition $P$ rectifiée et vérifier qu'elle est stochastique par lignes.

Un réseau hydraulique de distribution relie 3 réservoirs $B_1,B_2,B_3$. L'eau circule dans des conduites orientées équipées de vannes réglant les débits nominaux (en m${}^3$/h) :
- Du réservoir $B_1$ vers le réservoir $B_2$ avec un débit de 4 m${}^3$/h ;
- Du réservoir $B_1$ vers le réservoir $B_3$ avec un débit de 6 m${}^3$/h ;
- Du réservoir $B_2$ vers le réservoir $B_3$ avec un débit de 3 m${}^3$/h ;
- Du réservoir $B_3$ vers le réservoir $B_1$ à l'aide d'une pompe de relevage avec un débit de 2 m${}^3$/h.
1. Construire la matrice d'adjacence pondérée $M$ de ce graphe orienté pour les sommets ordonnés $(B_1,B_2,B_3)$.
2. Calculer la somme des éléments de la première ligne et interpréter sa signification physique.

On considère le graphe complet non orienté à 3 sommets noté $K_3$, dont les sommets sont $A,B,C$.
Sa matrice d'adjacence est $M=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)$.
1. Calculer la matrice $M^2$.
2. Calculer la matrice $M^3$.
3. En déduire le nombre de circuits de longueur 3 partant du sommet $A$ et revenant en $A$. Citer explicitement ces chaînes.

Un complexe sportif propose deux activités principales : Natation ($N$) et Fitness ($F$).
Chaque mois, les choix des abonnés évoluent selon les règles suivantes :
- $30\%$ des adeptes de Natation choisissent le Fitness le mois suivant (et $70\%$ continuent la Natation) ;
- $20\%$ des adeptes de Fitness choisissent la Natation le mois suivant (et $80\%$ continuent le Fitness).
La matrice de transition associée pour les états classés dans l'ordre $(N,F)$ est :$$P=\left(\begin{array}{cc}0,70& 0,30\\ 0,20& 0,80\end{array}\right)$$1. Définir ce qu'est un état stable (ou distribution invariante) $\pi =\left(\begin{array}{cc}x& y\end{array}\right)$ pour cette chaîne de Markov.
2. Écrire le système d'équations vérifié par les réels $x$ et $y$, puis le résoudre rigoureusement.
3. En déduire la répartition prévisible des adhérents à long terme.

Un réseau de vélos partagés est implanté autour de 3 stations principales nommées $A,B$ et $C$.
Les flux journaliers des vélos sont modélisés par une chaîne de Markov dont la matrice de transition pour l'ordre $(A,B,C)$ est :$$P=\left(\begin{array}{ccc}0,6& 0,2& 0,2\\ 0,1& 0,7& 0,2\\ 0,2& 0,2& 0,6\end{array}\right)$$On recherche la distribution invariante $\pi =\left(\begin{array}{ccc}x& y& z\end{array}\right)$ telle que $\pi =\pi P$ et $x+y+z=1$.
1. Écrire le système linéaire vérifié par les réels $x,y,z$.
2. Résoudre ce système et donner la proportion théorique de vélos dans chaque station à l'état stable sous forme de fractions irréductibles.

On considère une chaîne de Markov à deux états $E_1$ et $E_2$ de matrice de transition :$$P=\left(\begin{array}{cc}0,8& 0,2\\ 0,4& 0,6\end{array}\right)$$On note ${\pi }_n=\left(\begin{array}{cc}{p}_n& q_n\end{array}\right)$ l'état probabiliste à l'étape $n$, où $p_n+q_n=1$.
1. Démontrer que pour tout $n\in \mathbb{N}$, $p_{n+1}=0,4p_n+0,4$.
2. Déterminer la valeur $\alpha$ telle que $\alpha =0,4\alpha +0,4$.
3. On pose, pour tout entier $n$, $u_n=p_n-\alpha$. Montrer que la suite $(u_n)$ est géométrique et préciser sa raison.
4. En déduire l'expression de $p_n$ en fonction de $n$ et de $p_0$, puis déterminer $\underset{n\to +\infty }{\lim }{p}_n$.

On considère un réseau de communication modélisé par un graphe à 4 sommets $A,B,C,D$.
La matrice d'adjacence du graphe du réseau est :$$M=\left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 0\\ 1& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right)$$On donne le calcul de $M^3$ :$$M^3=\left(\begin{array}{cccc}4& 5& 5& 5\\ 5& 2& 5& 2\\ 5& 5& 4& 5\\ 5& 2& 5& 2\end{array}\right)$$1. Déterminer le nombre total de chaînes de longueur 3 reliant le sommet $A$ au sommet $B$.
2. En raison d'une panne, le sommet $C$ est rendu totalement inaccessible. Dresser la matrice d'adjacence $M^{\prime }$ du sous-graphe privé du sommet $C$ pour les sommets restants ordonnés $(A,B,D)$.
3. Calculer $M^{\prime 3}$ et en déduire le nombre de chaînes de longueur 3 reliant $A$ à $B$ qui n'empruntent jamais le sommet $C$.

Un agent d'entretien doit inspecter l'ensemble des allées d'un parc paysager modélisé par un graphe connexe de sommets $A,B,C,D,E$.
Chaque arête représente une allée à parcourir exactement une fois.
Les degrés des sommets du graphe sont les suivants : $\mathrm{deg}(A)=4$, $\mathrm{deg}(B)=3$, $\mathrm{deg}(C)=4$, $\mathrm{deg}(D)=2$ et $\mathrm{deg}(E)=3$.
1. L'agent peut-il effectuer son inspection sous la forme d'un cycle fermé (revenant à son point de départ) ? Justifier rigoureusement.
2. L'agent peut-il effectuer son inspection sous la forme d'une chaîne ouverte ? Si oui, quels doivent nécessairement être les sommets de départ et d'arrivée de sa tournée ?

Une entreprise de coursiers urbains dessert 4 dépôts $A,B,C,D$. En raison des sens uniques imposés dans le centre historique :
- Depuis $A$, on peut rejoindre directement $B$ et $C$ ;
- Depuis $B$, on peut rejoindre directement $C$ et $D$ ;
- Depuis $C$, on peut rejoindre directement $A$ et $D$ ;
- Depuis $D$, on peut rejoindre uniquement $A$.
1. Dresser la matrice d'adjacence orientée $T$ de ce réseau pour les dépôts classés dans l'ordre alphabétique.
2. Calculer la matrice $T^2$.
3. En déduire l'ensemble des circuits orientés de longueur 2 reliant un dépôt à lui-même.

Une enseigne de commerce électronique teste deux stratégies de fidélisation, notées $S_1$ et $S_2$, pour fidéliser ses acheteurs.
Le comportement des clients est modélisé par une chaîne de Markov à deux états : Fidèle ($F$) et Inactif ($I$).
- Pour la stratégie $S_1$, la matrice de transition est : $P_1=\left(\begin{array}{cc}0,85& 0,15\\ 0,40& 0,60\end{array}\right)$ ;
- Pour la stratégie $S_2$, la matrice de transition est : $P_2=\left(\begin{array}{cc}0,90& 0,10\\ 0,25& 0,75\end{array}\right)$.
1. Déterminer la distribution stationnaire ${\pi }^{(1)}$ associée à la stratégie $S_1$.
2. Déterminer la distribution stationnaire ${\pi }^{(2)}$ associée à la stratégie $S_2$.
3. En comparant les pourcentages de clients fidèles à long terme, indiquer quelle stratégie est la plus performante pour l'enseigne.