Exercices de Graphes en maths Terminale (page 2)

41. $Chaîne de Markov à paramètre et distribution invariante$

42. $Équilibre de transmission génétique simplifiée et état stable$

Dans une population d'insectes, un individu peut être Porteur (

P

) ou Non porteur (

N

) d'une mutation génétique.
À chaque génération, la probabilité pour la descendance d'un porteur d'être porteuse est de

0, 75

, et d'être non porteuse de

0, 25

.
Pour un individu non porteur, la probabilité que sa descendance devienne porteuse par mutation spontanée est de

0, 10

, et de rester non porteuse de

0, 90

.
1. Dresser la matrice de transition

T

associée à cette dynamique dans l'ordre

(P, N)

.
2. Déterminer la distribution invariante de la mutation dans cette population.
3. Interpréter la proportion théorique d'insectes porteurs de la mutation à l'équilibre démographique.

Corrigé réservé aux abonnésVoir le corrigé

43. $Inspection d'un réseau de canalisations et graphe eulérien$

Un technicien de maintenance doit inspecter un ensemble de canalisations reliant six carrefours

A, B, C, D, E, F

.
Le graphe connexe modélisant ce réseau comprend les liaisons suivantes :

A B, B C, C D, D E, E F, F A, A E

B D

.
1. Déterminer le degré de chacun des 6 sommets du graphe.
2. Le technicien peut-il parcourir l'ensemble des canalisations en passant une seule et unique fois par chacune d'elles, sans contrainte sur le point de départ et le point d'arrivée ? Justifier.
3. Est-il possible d'effectuer une telle inspection en partant du carrefour

A

et en revenant au carrefour

A

Corrigé réservé aux abonnésVoir le corrigé

44. $Démonstration par récurrence du théorème du nombre de chaînes$

Soit

G

un graphe non orienté d'ordre

p

dont les sommets sont numérotés de

1

p

, et soit

A = (a_{ij})_{1 ⩽ i, j ⩽ p}

sa matrice d'adjacence.
Pour tout entier naturel

n ⩾ 1

et pour tout couple de sommets

(i, j)

, on note

c_{ij}^{(n)}

le nombre de chaînes de longueur

n

reliant le sommet

i

au sommet

j

.
Démontrer par récurrence sur

n ⩾ 1

que pour tout entier

n ⩾ 1

et pour tout couple

(i, j) \in {1, \dots, p}^{2}

, on a :

c_{ij}^{(n)} = (A^{n})_{ij}

où

(A^{n})_{ij}

désigne le coefficient situé à la ligne

i

et à la colonne

j

de la matrice

A^{n}

Corrigé réservé aux abonnésVoir le corrigé

45. $Démonstration de la formule de distribution d'une chaîne de Markov$

Soit une chaîne de Markov à

m

états (

m \in {2, 3}

) de matrice de transition

P

.
On note

π_{n}

la matrice ligne représentant la distribution de probabilité à l'étape

n \in N

.
On rappelle la relation de transition d'une étape à la suivante :

π_{n + 1} = π_{n} \times P

.
1. Justifier rigoureusement, à l'aide de la formule des probabilités totales, la relation

π_{n + 1} = π_{n} \times P

.
2. Démontrer par récurrence que pour tout

n \in N

π_{n} = π_{0} \times P^{n}

, où

P^{0} = I_{m}

désigne la matrice identité d'ordre

m

.
3. En déduire l'interprétation probabiliste du coefficient situé en ligne

i

et colonne

j

de la matrice

P^{n}

Corrigé réservé aux abonnésVoir le corrigé

46. $Marche aléatoire sur les sommets d'un triangle$

Une puce saute aléatoirement sur les sommets d'un triangle équilatéral

A, B, C

.
À chaque saut, si elle se trouve sur un sommet, elle a une probabilité de

0, 2

d'y rester, et saute vers chacun des deux autres sommets avec une probabilité égale de

0, 4

.
On note

π_{n} = (a_{n} b_{n} c_{n})

la distribution de probabilité à l'étape

n

, où

a_{n} + b_{n} + c_{n} = 1

.
Au départ (

n = 0

), la puce est sur le sommet

A

, donc

π_{0} = (100)

.
1. Écrire la matrice de transition

P

de cette chaîne de Markov.
2. Montrer par récurrence que pour tout

n \in N

b_{n} = c_{n}

.
3. En déduire que pour tout

n \in N

a_{n + 1} = - 0, 2 a_{n} + 0, 4

.
4. Établir l'expression explicite de

a_{n}

en fonction de

n

, puis déterminer la limite de

π_{n}

quand

n \to + \infty

Corrigé réservé aux abonnésVoir le corrigé

47. $Modèle de diffusion d'Ehrenfest à deux urnes et deux particules$

On considère un modèle simplifié de diffusion thermique dit d'Ehrenfest.
Deux urnes

U_{1}

U_{2}

contiennent au total 2 particules indiscernables.
À chaque unité de temps, une particule est choisie au hasard de manière équiprobable parmi les 2 et change d'urne.
L'état du système à l'étape

n

est défini par le nombre de particules présentes dans l'urne

U_{1}

. Il existe trois états possibles :

E_{0}

(0 particule),

E_{1}

(1 particule) et

E_{2}

(2 particules).
1. Déterminer les probabilités de transition entre ces trois états et donner la matrice de transition

P

selon l'ordre

(E_{0}, E_{1}, E_{2})

.
2. Déterminer la distribution invariante

π = (π_{0} π_{1} π_{2})

telle que

π P = π

π_{0} + π_{1} + π_{2} = 1

.
3. Interpréter physiquement ce résultat au regard d'une loi binomiale.

Corrigé réservé aux abonnésVoir le corrigé

48. $Algorithme PageRank élémentaire sur un mini-réseau de trois pages$

Un moteur de recherche modélise la navigation d'un internaute sur trois pages web notées

A, B

C

reliées par des liens hypertextes :
- La page

A

contient des liens sortants vers

B

et vers

C

;
- La page

B

contient un unique lien sortant vers

C

;
- La page

C

contient un unique lien sortant vers

A

.
Lorsqu'il consulte une page, l'internaute clique de façon équiprobable sur l'un des liens sortants disponibles.
1. Déterminer la matrice de transition

P

de cette chaîne de Markov pour les pages ordonnées

(A, B, C)

.
2. Déterminer la distribution invariante

π = (x y z)

telle que

π P = π

x + y + z = 1

.
3. En déduire le classement d'importance (score PageRank) des trois pages web.

Corrigé réservé aux abonnésVoir le corrigé

49. $Dénombrement avancé et matrice d'adjacence d'un graphe d'incompatibilité$

Cinq applications logicielles notées

L_{1}, L_{2}, L_{3}, L_{4}, L_{5}

partagent les ressources d'un serveur informatique.
Pour des raisons d'incompatibilité, certaines paires d'applications ne peuvent pas être exécutées simultanément.
Le graphe des incompatibilités est donné par sa matrice d'adjacence :

M = 0110010110110010100100110

On donne également la puissance 3 de cette matrice :

M^{3} = 2442242651462152510421540

1. Quel est le nombre total de chaînes de longueur 3 reliant le sommet

L_{2}

au sommet

L_{3}

?
2. Déterminer le nombre de ces chaînes qui débutent par un aller-retour immédiat vers un sommet voisin de

L_{2}

(c'est-à-dire de la forme

L_{2} - L_{k} - L_{2} - L_{3}

).
3. En déduire le nombre de chaînes de longueur 3 reliant

L_{2}

L_{3}

qui ne repassent jamais par le sommet de départ

L_{2}

Corrigé réservé aux abonnésVoir le corrigé

50. $Chaîne de Markov à deux états et convergence vers l'état stable$

Une particule quantique évolue sur deux niveaux d'énergie notés

0

1

.
À chaque unité de temps, son niveau évolue selon les probabilités suivantes :
- Si elle se trouve au niveau

0

, elle passe au niveau

1

avec une probabilité

p \in] 0; 1 [

, et reste au niveau

0

avec la probabilité

1 - p

.
- Si elle se trouve au niveau

1

, elle repasse au niveau

0

avec une probabilité

q \in] 0; 1 [

, et reste au niveau

1

avec la probabilité

1 - q

.
On note

π_{n} = (x_{n} y_{n})

la distribution de probabilité à l'étape

n

, où

x_{n} + y_{n} = 1

.
1. Écrire la matrice de transition

P

associée dans l'ordre

(0, 1)

.
2. Montrer que pour tout

n \in N

, la suite

(x_{n})

vérifie la relation de récurrence :

x_{n + 1} = (1 - p - q) x_{n} + q

3. Démontrer que pour tout

n \in N

x_{n} = \frac{q}{p + q} + (x_{0} - \frac{q}{p + q}) (1 - p - q)^{n}

4. Justifier que

∣1 - p - q ∣ < 1

, puis en déduire la limite de

π_{n}

quand

n \to + \infty

Corrigé réservé aux abonnésVoir le corrigé

51. $Score d'influence sur un réseau social à trois comptes$

Trois créateurs de contenu notés

X, Y, Z

se mentionnent mutuellement dans leurs publications sur les réseaux sociaux :
- Le créateur

X

mentionne systématiquement le créateur

Y

;
- Le créateur

Y

mentionne

X

Z

avec des fréquences égales ;
- Le créateur

Z

mentionne

X

Y

avec des fréquences égales.
On modélise le parcours d'un abonné découvrant ces créateurs par une chaîne de Markov sur l'ensemble

{X, Y, Z}

.
1. Déterminer la matrice de transition

M

de ce graphe probabiliste pour les sommets classés dans l'ordre

(X, Y, Z)

.
2. Déterminer la distribution stationnaire

π = (a b c)

vérifiant

π M = π

a + b + c = 1

.
3. En déduire quel créateur possède la plus forte influence à long terme et donner son pourcentage de visibilité.

Corrigé réservé aux abonnésVoir le corrigé

52. $Analyse structurelle d'un réseau ferroviaire régional$

Un réseau ferroviaire régional relie cinq gares notées

A

B

C

D

E

. Les liaisons directes bidirectionnelles entre ces gares sont modélisées par les arêtes d'un graphe non orienté

G

{A, B}

{A, C}

{B, C}

{B, D}

{C, D}

{C, E}

{D, E}

Q1-Déterminer l'ordre du graphe

G

ainsi que le degré de chacun de ses sommets.

Q2-Ce graphe est-il simple ? Justifier.

Q3-Ce graphe est-il complet ? Justifier la réponse.

Voir le corrigé

1. L'ordre d'un graphe correspond au nombre total de ses sommets. Le réseau comporte cinq gares distinctes (

A, B, C, D, E

), donc l'ordre du graphe

G

est égal à

5

.
Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes (c'est-à-dire le nombre de ses voisins directs) :
- Le sommet

A

est relié à

B

C

, donc

d (A) = 2

.
- Le sommet

B

est relié à

A

C

D

, donc

d (B) = 3

.
- Le sommet

C

est relié à

A

B

D

E

, donc

d (C) = 4

.
- Le sommet

D

est relié à

B

C

E

, donc

d (D) = 3

.
- Le sommet

E

est relié à

C

D

, donc

d (E) = 2

.
Remarquons au passage que la somme des degrés vaut

2 + 3 + 4 + 3 + 2 = 14 = 2 \times 7

, ce qui correspond bien au double du nombre d'arêtes.

2. Un graphe est dit simple s'il ne comporte aucune boucle (arête reliant un sommet à lui-même) et au plus une arête entre deux sommets distincts (pas d'arêtes multiples). Ici, la liste des liaisons ne contient aucune boucle de type

{X, X}

et chaque paire de sommets est reliée par au plus une arête. Le graphe

G

est donc un graphe simple.

3. Un graphe simple d'ordre

n

est complet si deux sommets distincts quelconques sont toujours adjacents. Pour un ordre

n = 5

, un graphe complet comporterait

\frac{5 \times 4}{2} = 10

arêtes, et chaque sommet serait de degré

4

. Or le graphe

G

ne possède que

7

arêtes, et par exemple les sommets

A

D

ne sont pas reliés par une arête directe. Par conséquent, le graphe

G

n'est pas complet.

53. $Matrice d'adjacence d'un réseau de capteurs environnementaux$

Un réseau de capteurs environnementaux est composé de quatre stations notées

S_{1}

S_{2}

S_{3}

S_{4}

. Deux stations communiquent directement par liaison radio si la distance qui les sépare est inférieure à leur portée d'émission. Les canaux ouverts sont :

{S_{1}, S_{2}}

{S_{1}, S_{3}}

{S_{2}, S_{4}}

{S_{3}, S_{4}}

Q1-Déterminer l'ordre du graphe et donner la liste des voisins de chaque sommet.

Q2-Écrire la matrice d'adjacence

M

associée à ce graphe en ordonnant les sommets par ordre croissant d'indice :

(S_{1}, S_{2}, S_{3}, S_{4})

Corrigé réservé aux abonnésVoir le corrigé

54. $Degrés et dénombrement des confrontations dans un tournoi$

Dans une compétition sportive, huit équipes notées

E_{1}, E_{2}, \dots, E_{8}

participent à une phase de qualification. Le calendrier est conçu de sorte que chaque équipe dispute exactement trois rencontres contre trois adversaires distincts. On modélise cette organisation par un graphe simple non orienté où les sommets représentent les équipes et les arêtes représentent les matchs programmés.

Q1-Quel est l'ordre du graphe modélisant cette phase de la compétition ? Quel est le degré de chacun de ses sommets ?

Q2-Rappeler le théorème reliant la somme des degrés des sommets au nombre d'arêtes d'un graphe.

Q3-En déduire le nombre total de matchs programmés lors de cette phase de qualification.

Corrigé réservé aux abonnésVoir le corrigé

55. $Faisabilité d'un réseau d'interconnexion par la parité des degrés$

Un administrateur système souhaite interconnecter cinq serveurs notés

S_{1}, S_{2}, S_{3}, S_{4}

S_{5}

par des câbles réseau directs. Pour des raisons de répartition de charge, il souhaite que le nombre de câbles reliés à chacun des serveurs soit respectivement égal à

4

3

3

2

1

Q1-Calculer la somme des degrés des sommets de ce réseau hypothétique.

Q2-Démontrer qu'aucun graphe simple ne peut satisfaire ces exigences.

Q3-Énoncer la propriété générale sur le nombre de sommets de degré impair dans tout graphe non orienté et vérifier la cohérence avec cette situation.

Corrigé réservé aux abonnésVoir le corrigé

56. $Matrice de transition d'un dispositif électronique à deux modes$

Un équipement électronique autonome alterne entre deux modes de fonctionnement : le mode Veille (

V

) et le mode Actif (

A

). Toutes les minutes, l'état de l'équipement peut changer selon les règles probabilistes suivantes :
- Lorsqu'il se trouve en mode Veille, il s'active à la minute suivante avec une probabilité de

0, 3

.
- Lorsqu'il se trouve en mode Actif, il bascule en veille à la minute suivante avec une probabilité de

0, 4

Q1-Préciser la probabilité que le dispositif conserve son mode actuel pour chacun des deux états.

Q2-Décrire les arcs et leurs poids dans le graphe probabiliste associé à ce système.

Q3-En choisissant l'ordre des états

(V, A)

, écrire la matrice de transition

P

de cette chaîne de Markov.

Corrigé réservé aux abonnésVoir le corrigé

57. $Modélisation matricielle des flux entre trois stations de vélos$

Un réseau de vélos en libre-service dispose de trois stations principales notées

A

B

C

. On modélise la circulation quotidienne des vélos par une chaîne de Markov dont la matrice de transition est :

P = 0, 5 0, 1 0, 4 0, 3 0, 7 0, 1 0, 2 0, 2 0, 5

où les états sont ordonnés selon

(A, B, C)

Q1-Vérifier que la matrice

P

est une matrice stochastique.

Q2-Interpréter concrètement le coefficient

p_{21} = 0, 1

ainsi que le coefficient

p_{13} = 0, 2

Q3-Un usager emprunte un vélo à la station

B

. Quelle est la probabilité que ce vélo soit restitué à la station

B

à la fin de la journée ?

Voir le corrigé

1. Une matrice carrée est dite stochastique (ou matrice de transition) si tous ses coefficients sont positifs ou nuls et si la somme des coefficients de chacune de ses lignes est égale à

1

.
Ici, tous les coefficients appartiennent à l'intervalle

[0; 1]

. Calculons la somme de chaque ligne :
- Première ligne :

0, 5 + 0, 3 + 0, 2 = 1, 0

.
- Deuxième ligne :

0, 1 + 0, 7 + 0, 2 = 1, 0

.
- Troisième ligne :

0, 4 + 0, 1 + 0, 5 = 1, 0

.
Toutes les sommes de lignes valent

1

, la matrice

P

est donc bien une matrice stochastique.

2. Dans la convention ligne :
- Le coefficient

p_{21} = 0, 1

est situé à la ligne 2 (station de départ

B

) et colonne 1 (station d'arrivée

A

). Il signifie qu'un vélo emprunté à la station

B

a une probabilité de

0, 1

(soit

10 %

) d'être déposé à la station

A

le soir.
- Le coefficient

p_{13} = 0, 2

est situé à la ligne 1 (station de départ

A

) et colonne 3 (station d'arrivée

C

). Il signifie qu'un vélo emprunté à la station

A

a une probabilité de

0, 2

(soit

20 %

) d'être déposé à la station

C

le soir.

3. La probabilité qu'un vélo emprunté à la station

B

soit restitué à la station

B

correspond au coefficient de transition de l'état

B

vers l'état

B

, c'est-à-dire le coefficient diagonal

p_{22}

situé à la ligne 2 et colonne 2. On lit directement :

p_{22} = 0, 7

Il y a donc une probabilité de

0, 7

(soit

70 %

) que ce vélo soit restitué à la station

B

58. $Répartition à court terme des souscriptions à une offre numérique$

Une plateforme de streaming propose deux types d'abonnements : Standard (

S

) et Premium (

P

). D'un mois au suivant :
-

85 %

des abonnés Standard renouvellent leur formule et

15 %

optent pour la formule Premium.
-

95 %

des abonnés Premium conservent leur abonnement et

5 %

choisissent la formule Standard.
Au lancement du service (mois

0

), la répartition initiale compte

60 %

d'abonnés Standard et

40 %

d'abonnés Premium.

Q1-Écrire la matrice de transition

T

associée à cette situation dans la base

(S, P)

ainsi que la matrice ligne

π_{0}

représentant la distribution initiale.

Q2-Calculer la matrice ligne

π_{1}

représentant la répartition des abonnés après un mois.

Q3-En déduire la proportion d'abonnés Premium observée au bout d'un mois.

Corrigé réservé aux abonnésVoir le corrigé

59. $Trajectoire probabiliste d'un drone de surveillance sur trois secteurs$

Un drone de surveillance patrouille au-dessus d'un complexe sécurisé divisé en trois zones notées

Z_{1}

Z_{2}

Z_{3}

. Les déplacements d'une ronde à la suivante sont régis par la matrice de transition :

M = 0 0, 5 0, 3 0, 6 0 0, 7 0, 4 0, 5 0

À l'instant initial

t = 0

, le drone se trouve avec certitude dans la zone

Z_{1}

Q1-Donner la matrice ligne

π_{0}

représentant la distribution initiale dans l'ordre

(Z_{1}, Z_{2}, Z_{3})

Corrigé réservé aux abonnésVoir le corrigé

60. $Restauration de la connexité d'un réseau informatique maillé$

Un réseau informatique interne relie six serveurs notés

A, B, C, D, E

F

. Les câbles de communication existants forment les liaisons directes suivantes :

{A, B}

{B, C}

{C, D}

{D, A}

{E, F}

Q1-Déterminer si ce graphe est connexe. Justifier soigneusement en identifiant les composantes connexes du réseau.

Q2-On installe un câble unique supplémentaire reliant directement le serveur

C

au serveur

E

. Démontrer que le nouveau graphe obtenu est connexe.

Q3-Dans ce réseau modifié, donner une chaîne reliant le serveur

A

au serveur

F

et préciser sa longueur. Peut-on trouver une chaîne de longueur strictement inférieure reliant

A

F

Corrigé réservé aux abonnésVoir le corrigé

61. $Modélisation matricielle d'un plan de circulation à sens uniques$

Le plan de circulation d'un quartier d'affaires dessert quatre places notées

1, 2, 3

4

. Les voies de circulation sont toutes à sens unique et correspondent aux arcs orientés suivants :

(1, 2)

(1, 3)

(2, 3)

(3, 1)

(3, 4)

(4, 2)

Q1-Écrire la matrice d'adjacence

A

de ce graphe orienté en ordonnant les sommets selon leur indice croissant.

Q2-Expliquer pourquoi la matrice

A

n'est pas symétrique en s'appuyant sur un exemple précis issu du graphe.

Q3-Calculer le produit de la ligne 1 par la colonne 4 de

A

. En déduire s'il est possible de relier directement la place 1 à la place 4 sans étape intermédiaire, puis donner un chemin reliant la place 1 à la place 4 en précisant sa longueur.

Corrigé réservé aux abonnésVoir le corrigé

62. $Chaînes de longueur deux et coefficients du carré de la matrice d'adjacence$

On considère un graphe simple non orienté à quatre sommets

A, B, C

D

. Les arêtes du graphe sont

{A, B}

{A, C}

{B, C}

{B, D}

{C, D}

Q1-Écrire la matrice d'adjacence

M

associée à ce graphe dans l'ordre

(A, B, C, D)

Q2-Calculer le carré

M^{2}

de cette matrice.

Q3-Interpréter le coefficient situé à la première ligne et quatrième colonne de

M^{2}

. Valider ce résultat en énumérant explicitement l'ensemble des chaînes de longueur

2

reliant le sommet

A

au sommet

D

Corrigé réservé aux abonnésVoir le corrigé

63. $Dénombrement des itinéraires logistiques via les puissances d'adjacence$

Un opérateur logistique dessert quatre plateformes notées

A, B, C

D

. La matrice d'adjacence des liaisons ferroviaires directes entre ces plateformes est :

M = 0110101111010110

Le calcul matriciel fournit la puissance troisième suivante :

M^{3} = 2552545555452552

Q1-Déterminer le nombre de trajets ferroviaires de longueur

3

reliant la plateforme

A

à la plateforme

D

Q2-Déterminer le nombre de trajets ferroviaires de longueur

3

reliant la plateforme

B

à la plateforme

C

Q3-Calculer le nombre total de trajets de longueur

3

ayant pour point de départ la plateforme

A

Corrigé réservé aux abonnésVoir le corrigé

64. $Projection tri-hebdomadaire du report modal vers les transports collectifs$

Dans une agglomération, on suit l'évolution des choix de déplacement des salariés entre les transports collectifs (

T

) et la voiture individuelle (

V

). D'une semaine à la suivante :
-

80 %

des usagers des transports collectifs renouvellent leur choix, tandis que

20 %

choisissent la voiture.
-

30 %

des automobilistes abandonnent la voiture au profit des transports collectifs, et

70 %

conservent leur voiture.
À la semaine initiale

n = 0

, la proportion d'usagers est de

40 %

pour

T

et de

60 %

pour

V

Q1-Écrire la matrice de transition

P

du graphe probabiliste associé dans la base

(T, V)

, ainsi que la matrice ligne

π_{0}

Q2-Calculer la distribution

π_{1}

des modes de transport à la semaine 1.

Q3-Calculer successivement les distributions

π_{2}

π_{3}

aux semaines 2 et 3.

Corrigé réservé aux abonnésVoir le corrigé

65. $Optimisation du déploiement de fibre optique par énumération exhaustive$

Un opérateur de télécommunications relie une antenne source

S

à un terminal récepteur

T

à travers un réseau local comportant trois relais intermédiaires

A

B

C

. Les longueurs de tranchée requises pour poser la fibre optique (exprimées en centaines de mètres) sont données par les poids des arêtes suivantes :
- Entre

S

A

4

- Entre

S

B

6

- Entre

A

B

1

- Entre

A

C

7

- Entre

B

C

3

- Entre

B

T

8

- Entre

C

T

2

Q1-Représenter la structure de ce réseau en précisant ses sommets et la liste complète de ses arêtes avec leurs poids respectifs.

Q2-Énumérer tous les chemins simples (chemins n'empruntant aucun sommet plus d'une fois) reliant la source

S

au terminal

T

Q3-Calculer la longueur totale associée à chacun de ces chemins.

Q4-En déduire le chemin qui minimise la longueur de tranchée à creuser, et donner la distance minimale correspondante en mètres.

Corrigé réservé aux abonnésVoir le corrigé

66. $Modélisation de la fidélisation d'une clientèle de paniers maraîchers$

Une association maraîchère propose chaque semaine des paniers de fruits et légumes biologiques. Elle classe ses adhérents en deux catégories : Adhérent régulier (

R

) et Adhérent ponctuel (

O

). Les observations collectées sur plusieurs mois permettent d'établir que :
- Un adhérent régulier commande un panier la semaine suivante dans

75 %

des cas, et devient ponctuel dans

25 %

des cas.
- Un adhérent ponctuel commande un panier la semaine suivante dans

40 %

des cas, et conserve son statut ponctuel dans

60 %

des cas.
Lors de la semaine de lancement (semaine 0), la communauté compte

20 %

d'adhérents réguliers et

80 %

d'adhérents ponctuels.

Q1-Représenter cette situation à l'aide d'un graphe probabiliste à deux états.

Q2-Écrire la matrice de transition

P

de cette chaîne de Markov dans la base

(R, O)

ainsi que la matrice ligne

π_{0}

de la semaine initiale.

Q3-Calculer la proportion d'adhérents réguliers attendue lors de la deuxième semaine d'activité (étape

n = 1

Corrigé réservé aux abonnésVoir le corrigé

67. $Rectification d'une inversion de convention stochastique$

Pour analyser les transferts d'utilisateurs entre deux applications mobiles concurrentes notées

A

B

, un chargé d'études propose la matrice suivante :

K = (0, 8 0, 2 0, 3 0, 7)

Il affirme que la probabilité qu'un utilisateur de l'application

A

bascule vers l'application

B

à l'étape suivante est égale au coefficient situé à la première ligne et deuxième colonne de

K

, soit

0, 3

Q1-Calculer la somme des coefficients de la première ligne de

K

. La matrice

K

est-elle une matrice de transition conforme à la convention du programme ?

Q2-Quelle confusion méthodologique le chargé d'études a-t-il commise ?

Q3-Donner la matrice de transition rectifiée

P

conforme aux normes du cours.

Q4-En déduire la véritable probabilité de transition de l'application

A

vers l'application

B

Corrigé réservé aux abonnésVoir le corrigé

68. $Analyse des hyperliens orientés d'un portail web et chemins de longueur deux$

Un portail documentaire en ligne est constitué de quatre pages web notées

1, 2, 3

4

. Les hyperliens orientés entre ces pages sont configurés ainsi :
- La page 1 contient des liens menant vers les pages 2 et 3.
- La page 2 contient un lien menant vers la page 4.
- La page 3 contient des liens menant vers les pages 2 et 4.
- La page 4 contient un lien de retour menant vers la page 1.

Q1-Écrire la matrice d'adjacence orientée

A

associée à ce mini-réseau dans l'ordre

(1, 2, 3, 4)

Q2-Calculer la matrice

A^{2}

Q3-Combien existe-t-il de chemins de longueur

2

reliant la page 1 à la page 4 ? Les énumérer explicitement.

Q4-Existe-t-il un circuit de longueur

2

partant de la page 4 et revenant à la page 4 ? Justifier la réponse à l'aide de

A^{2}

Corrigé réservé aux abonnésVoir le corrigé

69. $Dénombrement des cycles triangulaires par la trace matricielle$

On considère un graphe simple non orienté à quatre sommets notés

A, B, C

D

. Ses arêtes sont

{A, B}

{B, C}

{C, D}

{D, A}

{A, C}

Q1-Écrire la matrice d'adjacence

M

de ce graphe dans l'ordre

(A, B, C, D)

Q2-Le calcul matriciel fournit les termes diagonaux de la puissance troisième de

M

(M^{3})_{11} = 4

(M^{3})_{22} = 2

(M^{3})_{33} = 4

(M^{3})_{44} = 2

. Calculer la trace de

M^{3}

, notée

Tr (M^{3})

, égale à la somme de ses coefficients diagonaux.

Corrigé réservé aux abonnésVoir le corrigé

70. $Distribution stationnaire des parts de marché de deux fournisseurs d'électricité$

Sur le marché de l'électricité résidentielle, deux fournisseurs se partagent les contrats : un fournisseur d'énergie renouvelable (

V

) et un opérateur historique classique (

C

). Chaque année :
-

85 %

des clients de

V

lui restent fidèles et

15 %

souscrivent chez

C

.
-

10 %

des clients de

C

décident de passer chez

V

, tandis que

90 %

restent fidèles à

C

Q1-Écrire la matrice de transition

P

de cette chaîne de Markov dans la base

(V, C)

Q2-On note

π = (x y)

un état probabiliste stable, où

x

y

représentent les parts de marché asymptotiques respectives de

V

et de

C

. Écrire le système d'équations vérifié par

x

y

Corrigé réservé aux abonnésVoir le corrigé

71. $Fréquence asymptotique des régimes météorologiques régionaux$

Dans une zone côtière, on modélise les conditions météorologiques quotidiennes par une chaîne de Markov à trois états : Ensoleillé (

S

), Nuageux (

N

) et Pluvieux (

P

). La matrice de transition observée d'un jour au lendemain est :

T = 0, 6 0, 3 0, 2 0, 3 0, 4 0, 4 0, 1 0, 3 0, 4

où les états sont ordonnés selon

(S, N, P)

Q1-Justifier que cette chaîne de Markov admet un état stable

π = (x y z)

vérifiant

π T = π

x + y + z = 1

Corrigé réservé aux abonnésVoir le corrigé

72. $Étude analytique de la vitesse de convergence vers l'état stationnaire$

On considère un processus aléatoire à deux états

A

B

dont la matrice de transition est :

P = (0, 7 0, 2 0, 3 0, 8)

Pour tout entier naturel

n

, on note

π_{n} = (a_{n} b_{n})

la distribution de probabilité à l'étape

n

. À l'instant initial, le système se trouve dans l'état

A

de manière certaine, de sorte que

π_{0} = (10)

Q1-Exprimer

a_{n + 1}

en fonction de

a_{n}

et démontrer que pour tout

n \in N

a_{n + 1} = 0, 5 a_{n} + 0, 2

Corrigé réservé aux abonnésVoir le corrigé

73. $Analyse de la vulnérabilité d'un réseau ferroviaire par suppression d'un nœud central$

Un réseau ferroviaire relie cinq villes notées

A, B, C, D

E

. La ville

C

constitue la gare centrale de correspondance du réseau. Les lignes directes exploitées sont représentées par les arêtes suivantes :

{A, B}

{A, C}

{B, C}

{C, D}

{C, E}

{D, E}

Q1-Écrire la matrice d'adjacence

M

associée à ce réseau dans l'ordre

(A, B, C, D, E)

Q2-Le calcul matriciel fournit la puissance 3 de cette matrice :

M^{3} = 2352232522554552252322532

Combien existe-t-il d'itinéraires ferroviaires de longueur

3

reliant la ville

A

à la ville

E

dans ce réseau complet ? Donner explicitement ces itinéraires.

Corrigé réservé aux abonnésVoir le corrigé

74. $Optimisation d'un plan de déneigement par le théorème d'Euler$

Lors d'un épisode neigeux, les services municipaux doivent déneiger l'ensemble des rues d'un quartier comportant six intersections notées

A, B, C, D, E

F

. Les rues bidirectionnelles à traiter correspondent aux 9 arêtes suivantes :

{A, B}

{A, D}

{B, C}

{B, D}

{B, E}

{C, D}

{C, F}

{D, E}

{E, F}

Q1-Déterminer le degré de chacun des six sommets de ce graphe.

Q2-Justifier que ce graphe est connexe.

Q3-Un engin de déneigement peut-il parcourir chaque rue une fois et une seule en revenant à son point de départ (cycle eulérien) ? Justifier rigoureusement.

Q4-Est-il possible de traiter l'intégralité du quartier en empruntant chaque rue une fois et une seule sans obligation de revenir au point de départ (chaîne eulérienne ouverte) ? Dans l'affirmative, préciser à quelles intersections ce parcours peut commencer et s'achever.

Corrigé réservé aux abonnésVoir le corrigé

75. $Faisabilité d'une ronde de sécurité sans redondance de parcours$

Un complexe industriel comporte cinq pavillons de surveillance notés

A, B, C, D

E

. Les allées piétonnes aménagées entre ces pavillons sont au nombre de 5 :

{A, B}

{B, C}

{C, A}

{A, D}

{A, E}

Q1-Calculer le degré de chacun des cinq sommets du graphe modélisant ce complexe.

Q2-Le responsable de la sécurité souhaite instaurer une ronde quotidienne qui emprunte chaque allée exactement une fois en revenant au pavillon de départ. Démontrer qu'une telle ronde est actuellement impossible.

Q3-Pour rendre cette ronde réalisable sans redondance, la direction décide d'aménager une unique allée supplémentaire entre deux pavillons qui ne sont pas encore directement reliés. Quels pavillons doit-on relier pour créer un cycle eulérien ? Justifier la réponse.

Corrigé réservé aux abonnésVoir le corrigé

76. $Routage et latence minimale dans un sous-réseau orienté$

Un sous-réseau de transmission de données est composé de quatre routeurs notés

R_{1}, R_{2}, R_{3}

R_{4}

. Les canaux de communication orientés et leurs délais de transfert respectifs (en millisecondes) sont :
- De

R_{1}

vers

R_{2}

5

ms
- De

R_{1}

vers

R_{3}

12

ms
- De

R_{2}

vers

R_{3}

4

ms
- De

R_{2}

vers

R_{4}

15

ms
- De

R_{3}

vers

R_{4}

6

ms
- De

R_{3}

vers

R_{1}

8

Q1-Écrire la matrice d'adjacence booléenne

A

associée aux liaisons orientées de ce réseau dans l'ordre

(R_{1}, R_{2}, R_{3}, R_{4})

Corrigé réservé aux abonnésVoir le corrigé

77. $Arbitrage entre rétention et acquisition par comparaison d'états stables$

Une entreprise de logiciels sous licence annuelle

M

opère sur un marché face à l'ensemble de ses concurrents noté

C

. Pour orienter ses investissements, elle compare deux stratégies commerciales :
- Stratégie 1 (Acquisition agressive) : le budget est focalisé sur la prospection. Le taux de fidélisation de ses clients est de

80 %

, et l'entreprise capte chaque année

15 %

des clients de la concurrence.
- Stratégie 2 (Fidélisation prioritaire) : le budget est alloué au support technique et à la satisfaction client. Le taux de fidélisation atteint

90 %

, mais le taux de conquête auprès de la concurrence n'est que de

10 %

Q1-Écrire les matrices de transition

P_{1}

P_{2}

associées respectivement à la stratégie 1 et à la stratégie 2 dans la base

(M, C)

Q2-Déterminer la part de marché stationnaire

x_{1}

de l'entreprise

M

sous la stratégie 1.

Q3-Déterminer la part de marché stationnaire

x_{2}

de l'entreprise

M

sous la stratégie 2.

Q4-Comparer les deux distributions stables obtenues et formuler une recommandation stratégique à la direction de l'entreprise.

Corrigé réservé aux abonnésVoir le corrigé

78. $Détermination d'un paramètre stochastique et équilibre stationnaire$

On considère une chaîne de Markov à trois états

E_{1}, E_{2}

E_{3}

dont la matrice de transition dépend d'un paramètre réel

α

P = 0, 5 0, 1 0, 3 α 0, 7 0, 3 0, 2 0, 2 0, 4

Q1-Démontrer que la seule valeur possible pour le paramètre

α

est

α = 0, 3

Q2-On fixe

α = 0, 3

. Définir ce qu'est un état stable

π = (x y z)

pour cette chaîne de Markov.

Corrigé réservé aux abonnésVoir le corrigé

79. $Disponibilité opérationnelle et taux de panne d'une infrastructure serveur$

Un serveur informatique à haute disponibilité peut occuper à chaque heure l'un des deux états suivants : En fonctionnement nominal (

F

) ou En panne (

P

). Les observations techniques montrent que :
- Si le serveur fonctionne à l'heure

n

, la probabilité qu'il subisse une panne à l'heure

n + 1

est de

0, 02

.
- Si le serveur est en panne à l'heure

n

, un protocole automatique de redémarrage permet de le remettre en service à l'heure

n + 1

avec une probabilité de

0, 18

Q1-Écrire la matrice de transition

P

de ce système dans la base

(F, P)

Q2-Déterminer l'état stable

π = (x y)

de cette chaîne de Markov.

Q3-En déduire le taux de disponibilité moyen du serveur sur le long terme (exprimé en pourcentage).

Corrigé réservé aux abonnésVoir le corrigé

80. $Dynamique de transmission épidémique avec perte d'immunité$

Dans une collectivité fermée, on modélise l'évolution d'une infection saisonnière selon trois compartiments : Individu sain réceptif (

S

), Individu infecté (

I

) et Individu rétabli avec immunité temporaire (

R

). Les transitions hebdomadaires observées sont modélisées par la matrice suivante :

M = 0, 85 0 0, 10 0, 15 0, 30 0 0 0, 70 0, 90

où les états sont ordonnés selon

(S, I, R)

Q1-Interpréter concrètement le coefficient nul situé à la deuxième ligne et première colonne, ainsi que le coefficient

0, 10

situé à la troisième ligne et première colonne.

Q2-On recherche la distribution stationnaire

π = (x y z)

satisfaisant

π M = π

x + y + z = 1

.
Écrire le système d'équations et exprimer les proportions

y

z

en fonction de

x

Corrigé réservé aux abonnésVoir le corrigé

41.Chaîne de Markov à paramètre et distribution invariante

42.Équilibre de transmission génétique simplifiée et état stable

43.Inspection d'un réseau de canalisations et graphe eulérien

44.Démonstration par récurrence du théorème du nombre de chaînes

45.Démonstration de la formule de distribution d'une chaîne de Markov

46.Marche aléatoire sur les sommets d'un triangle

47.Modèle de diffusion d'Ehrenfest à deux urnes et deux particules

48.Algorithme PageRank élémentaire sur un mini-réseau de trois pages

49.Dénombrement avancé et matrice d'adjacence d'un graphe d'incompatibilité

50.Chaîne de Markov à deux états et convergence vers l'état stable

51.Score d'influence sur un réseau social à trois comptes

52.Analyse structurelle d'un réseau ferroviaire régional

53.Matrice d'adjacence d'un réseau de capteurs environnementaux

54.Degrés et dénombrement des confrontations dans un tournoi

55.Faisabilité d'un réseau d'interconnexion par la parité des degrés

56.Matrice de transition d'un dispositif électronique à deux modes

57.Modélisation matricielle des flux entre trois stations de vélos

58.Répartition à court terme des souscriptions à une offre numérique

59.Trajectoire probabiliste d'un drone de surveillance sur trois secteurs

60.Restauration de la connexité d'un réseau informatique maillé

61.Modélisation matricielle d'un plan de circulation à sens uniques

62.Chaînes de longueur deux et coefficients du carré de la matrice d'adjacence

63.Dénombrement des itinéraires logistiques via les puissances d'adjacence

64.Projection tri-hebdomadaire du report modal vers les transports collectifs

65.Optimisation du déploiement de fibre optique par énumération exhaustive

66.Modélisation de la fidélisation d'une clientèle de paniers maraîchers

67.Rectification d'une inversion de convention stochastique

68.Analyse des hyperliens orientés d'un portail web et chemins de longueur deux

69.Dénombrement des cycles triangulaires par la trace matricielle

70.Distribution stationnaire des parts de marché de deux fournisseurs d'électricité

71.Fréquence asymptotique des régimes météorologiques régionaux

72.Étude analytique de la vitesse de convergence vers l'état stationnaire

73.Analyse de la vulnérabilité d'un réseau ferroviaire par suppression d'un nœud central

74.Optimisation d'un plan de déneigement par le théorème d'Euler

75.Faisabilité d'une ronde de sécurité sans redondance de parcours

76.Routage et latence minimale dans un sous-réseau orienté

77.Arbitrage entre rétention et acquisition par comparaison d'états stables

78.Détermination d'un paramètre stochastique et équilibre stationnaire

79.Disponibilité opérationnelle et taux de panne d'une infrastructure serveur

80.Dynamique de transmission épidémique avec perte d'immunité

41. $Chaîne de Markov à paramètre et distribution invariante$

42. $Équilibre de transmission génétique simplifiée et état stable$

43. $Inspection d'un réseau de canalisations et graphe eulérien$

44. $Démonstration par récurrence du théorème du nombre de chaînes$

45. $Démonstration de la formule de distribution d'une chaîne de Markov$

46. $Marche aléatoire sur les sommets d'un triangle$

47. $Modèle de diffusion d'Ehrenfest à deux urnes et deux particules$

48. $Algorithme PageRank élémentaire sur un mini-réseau de trois pages$

49. $Dénombrement avancé et matrice d'adjacence d'un graphe d'incompatibilité$

50. $Chaîne de Markov à deux états et convergence vers l'état stable$

51. $Score d'influence sur un réseau social à trois comptes$

52. $Analyse structurelle d'un réseau ferroviaire régional$

53. $Matrice d'adjacence d'un réseau de capteurs environnementaux$

54. $Degrés et dénombrement des confrontations dans un tournoi$

55. $Faisabilité d'un réseau d'interconnexion par la parité des degrés$

56. $Matrice de transition d'un dispositif électronique à deux modes$

57. $Modélisation matricielle des flux entre trois stations de vélos$

58. $Répartition à court terme des souscriptions à une offre numérique$

59. $Trajectoire probabiliste d'un drone de surveillance sur trois secteurs$

60. $Restauration de la connexité d'un réseau informatique maillé$

61. $Modélisation matricielle d'un plan de circulation à sens uniques$

62. $Chaînes de longueur deux et coefficients du carré de la matrice d'adjacence$

63. $Dénombrement des itinéraires logistiques via les puissances d'adjacence$

64. $Projection tri-hebdomadaire du report modal vers les transports collectifs$

65. $Optimisation du déploiement de fibre optique par énumération exhaustive$

66. $Modélisation de la fidélisation d'une clientèle de paniers maraîchers$

67. $Rectification d'une inversion de convention stochastique$

68. $Analyse des hyperliens orientés d'un portail web et chemins de longueur deux$

69. $Dénombrement des cycles triangulaires par la trace matricielle$

70. $Distribution stationnaire des parts de marché de deux fournisseurs d'électricité$

71. $Fréquence asymptotique des régimes météorologiques régionaux$

72. $Étude analytique de la vitesse de convergence vers l'état stationnaire$

73. $Analyse de la vulnérabilité d'un réseau ferroviaire par suppression d'un nœud central$

74. $Optimisation d'un plan de déneigement par le théorème d'Euler$

75. $Faisabilité d'une ronde de sécurité sans redondance de parcours$

76. $Routage et latence minimale dans un sous-réseau orienté$

77. $Arbitrage entre rétention et acquisition par comparaison d'états stables$

78. $Détermination d'un paramètre stochastique et équilibre stationnaire$

79. $Disponibilité opérationnelle et taux de panne d'une infrastructure serveur$

80. $Dynamique de transmission épidémique avec perte d'immunité$