Trajet minimal et feux tricolores

Unit 1 - | Corpus Sujets - 1 Sujet

Matrices et graphes • Graphes probabilistes

Corrigé

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.

Les deux parties sont indépendantes.

Partie A

Étude du trajet

> 1. Déterminer le trajet le plus court entre Aoste et Florence. (On indiquera les villes parcourues et l’ordre de parcours). (1,25 point)

> 2. Déterminer le budget carburant nécessaire aux quatre voyages aller-retour du mois (le résultat sera arrondi à l’euro près).

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.

> 1. Représenter la situation par un graphe probabiliste. (0,75 point)

> 2. Indiquer la matrice de transition du graphe, en considérant les sommets dans l’ordre (V, R) en ligne comme en colonne. (0,5 point)

> 3. Le premier feu rencontré est vert. La matrice donnant l’état initial est donc (1 0).

a) Déterminer les matrices et . (Le détail des calculs n’est pas demandé.) (1 point)

b) Conclure quant à la probabilité  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

> 1. Le trajet le plus court ne comporte pas nécessairement un nombre minimal d’arêtes. Utilisez l’algorithme de Dijkstra.

Partie B

> 2. Les coefficients de la matrice de transition associée à un graphe probabiliste sont les probabilités portées par les arêtes de ce graphe  la somme des coefficients d’une ligne est égale à 1.

> 3. b) La probabilité  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 .