Matrices et graphes • Graphes probabilistes
Corrigé
38
Ens. de spécialité
matT_1306_07_06C
France métropolitaine • Juin 2013
Exercice 4 • 5 points
Un chauffeur-livreur réside en Italie dans la ville d’Aoste.
Quatre fois par mois, son employeur l’envoie livrer du matériel informatique dans la ville de Florence.
Il est établi que le trajet en camion coûte, en carburant, 0,51 euro au kilomètre. Le chauffeur dispose d’un budget mensuel de 2 200 euros pour son carburant. Ce qu’il réussit à économiser lui permet de toucher une prime P équivalente en fin de mois.
Il consulte donc la carte routière ci-dessous pour optimiser ses trajets.
Le graphe ci-dessous indique les distances entre différentes villes d’Italie : Aoste, Milan, Parme, Turin, Gènes, La Spézia, Bologne et Florence. Chaque ville est désignée par son initiale.
Partie A
Étude du trajet
En déduire le montant de la prime P qui lui sera versée en fin de mois, à l’euro près. (0,75 point)
Partie B
Traversée de Parme
Durant son trajet, le chauffeur est obligé de traverser Parme et ses très nombreux feux tricolores. Lorsque le feu est orange, le chauffeur se comporte comme lorsqu’il est rouge, il s’arrête.
L’expérience lui a permis d’établir que, s’il se présente à un feu, il se produit les événements suivants :
- Arrivé au feu, celui-ci est au vert (V) : la probabilité que le suivant soit vert est de 0,85.
- Arrivé au feu, celui-ci est orange ou rouge (R) : la probabilité que le suivant soit vert est de 0,30.
du graphe, en considérant les sommets dans l’ordre (V, R) en ligne comme en colonne. (0,5 point)
donnant l’état initial est donc (1 0).
et 
. (Le détail des calculs n’est pas demandé.) (1 point)
de l’événement « le chauffeur doit s’arrêter au troisième feu ». (0,75 point)
Les thèmes en jeu
Graphe pondéré • Graphe probabiliste • Matrice associée à un graphe.
Les conseils du correcteur
Partie A
Partie B
de l’événement « Le chauffeur doit s’arrêter au troisième feu » est la probabilité que le troisième feu soit orange ou rouge ; c’est l’un des coefficients de la matrice 
.
Partie A
> 1. Déterminer un trajet minimal sur un graphe
Pour déterminer le trajet le plus court entre Aoste et Florence, on utilise l’algorithme de Dijkstra qui peut être résumé par le tableau suivant :
|
A |
M |
P |
T |
G |
LS |
B |
F |
|
0 (A) |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
|
174 (A) |
∞ |
120 (A) |
∞ |
∞ |
∞ |
∞ |
|
|
174 (A) |
366 (T) |
|
288 (T) |
∞ |
∞ |
∞ |
|
|
|
300 (M) |
|
288 (T) |
∞ |
∞ |
∞ |
|
|
|
300 (M) |
|
|
396 (G) |
∞ |
∞ |
|
|
|
|
|
|
396 (G) |
398 (P) |
∞ |
|
|
|
|
|
|
|
398 (P) |
541 (LS) |
|
|
|
|
|
|
|
|
502 (B) |
Notez bien
Il existe d’autres trajets en 4 étapes d’Aoste à Florence, mais ils sont plus longs ; par exemple : Aoste – Turin – Gênes – La Spezia – Florence (541 km) ou Aoste – Turin
Le trajet le plus court d’Aoste à Florence est donc :
Aoste – Milan – Parme – Bologne – Florence.
Ce trajet comporte 4 étapes.
> 2. Calculer le prix de revient d’un déplacement
Si le chauffeur fait 4 voyages aller-retour Aoste-Florence (soit 8 trajets) par le chemin le plus court, il parcourt 8 fois 502 km, soit 4 016 km.
.
.
Partie B
> 1. Représenter une situation par un graphe probabiliste
La situation peut être représentée par le graphe probabiliste suivant :
> 2. Déterminer la matrice de transition d’un graphe probabiliste
La matrice de transition du graphe est :
> 3. a) Déterminer deux états probabilistes associés à un graphe
b) Déterminer une probabilité associée à un graphe probabiliste
D’après le calcul de la matrice P3, la probabilité p de l’événement « le chauffeur doit s’arrêter au troisième feu », c’est-à-dire
Les deux parties sont indépendantes.