Graphes
Corrigé
43
Ens. de spécialité
matT_1206_13_00C
Polynésie française • Juin 2012
Exercice 2 • 5 points
Jonathan est un sportif adepte du semi-marathon (course à pied de 21,1 km). Depuis le 1er janvier 2012, il a décidé de courir un semi-marathon par mois. Afin d’améliorer sa préparation, il décide d’enchaîner les courses pédestres de 10 km dans différentes villes.
PARTIE A
Le graphe pondéré ci-dessous représente les villes A, B, C, D, E, F, H organisant des courses de 10 km et la ville G est celle organisant le prochain semi-marathon auquel Jonathan est inscrit.
Le poids de chaque arête représente le temps, en minutes, nécessaire pour relier une ville à une autre grâce aux transports en commun.
Jonathan vient de courir dans la ville A et souhaite se rendre dans la ville G pour repérer le parcours de son prochain semi-marathon. Déterminer à l’aide d’un algorithme le chemin permettant de relier le plus rapidement la ville A à la ville G, et donner la durée de ce parcours en minutes.
PARTIE B
Grâce à son entraînement et à son expérience, Jonathan sait que :
- S’il a terminé la course lors de son précédent semi-marathon, il terminera le prochain semi-marathon avec une probabilité de 0,62.
- S’il a abandonné lors de son précédent semi-marathon, il terminera le prochain semi-marathon avec une probabilité de 0,8.
Jonathan a terminé son semi-marathon de janvier 2012. Pour tout entier naturel n, on note 
la matrice ligne 
traduisant l’état probabiliste du 
-ième mois écoulé depuis janvier 2012, où 
désigne la probabilité que Jonathan abandonne au semi-marathon du 
-ième mois et 
la probabilité que Jonathan termine le semi-marathon du 
-ième mois.
L’état probabiliste initial, correspondant à janvier 2012, est donc donné par :
. En déduire la probabilité que Jonathan ait abandonné lors du semi-marathon couru en mars 2012.
près.
Durée conseillée : 40 min.
Les thèmes en jeu
Graphes pondérés • Matrice associée à un graphe • Chaîne de longueur donnée • Graphes probabilistes.
Les conseils du correcteur
Partie A
Utilisez, par exemple, l’algorithme de Dijkstra.
Partie B
traduit l’état probabiliste de mars 2012.
et 
où 
est la matrice de transition.
PARTIE A
Déterminer sur un graphe pondéré le « plus court chemin » d’un sommet à un autre
Pour déterminer le chemin permettant de relier le plus rapidement la ville A à la ville G, on utilise l’algorithme de Dijkstra, résumé dans le tableau ci-dessous :
|
A |
B |
C |
D |
E |
F |
G |
H |
|
|---|---|---|---|---|---|---|---|---|
|
0 |
60 A |
70 A |
∞ |
20 A |
45 A |
∞ |
∞ |
A |
|
|
40 E |
70 A |
80 E |
20 A |
45 A |
∞ |
70 E |
E |
|
|
40 E |
50 B |
80 E |
|
45 A |
∞ |
70 E |
B |
|
|
|
50 B |
80 E |
|
45 A |
∞ |
70 E |
F |
|
|
|
50 B |
65 C |
|
|
∞ |
70 E |
C |
|
|
|
|
65 C |
|
|
85 D |
70 E |
D |
|
|
|
|
|
|
|
85 D |
70 E |
H |
|
|
|
|
|
|
|
85 D |
|
G |
PARTIE B
> 1. Traduire les données d’un énoncé par un graphe probabiliste
Notez bien
0,8 est la probabilité que Jonathan termine un semi-marathon sachant qu’il a abandonné lors du précédent ; 0,38 est la probabilité qu’il abandonne lors d’un semi-marathon sachant qu’il a terminé le précédent. Ce sont des probabilités conditionnelles.
Les données peuvent être traduites par le graphe probabiliste suivant :
> 2. Déterminer la matrice de transition associée à un graphe probabiliste
La matrice de transition associée au graphe précédent est :
> 3. Déterminer un état probabiliste à l’aide d’un graphe probabiliste et de sa matrice de transition
Conseil
Vérifiez que 
.
; 
, donc :
et 
.
> 4. a) Déterminer l’état stable associé à un graphe probabiliste
L’état stable est donné par la relation 
.
Avec 
, cette égalité équivaut à :
, soit 
De plus, 
, donc 
et 
, d’où :
et 
.
A 
près :
b) Interpréter l’état stable
