Graphes, « plus court chemin »
matT_1405_02_09C
Ens. de spécialité
33
CORRIGE
Amérique du Nord &bull Mai 2014
Exercice 4 &bull 5 points
Lors d&rsquo une campagne électorale, un homme politique doit effectuer une tournée dans les villes A, B, C, D, E, F, G et H, en utilisant le réseau autoroutier. Le graphe ci-dessous représente les différentes villes de la tournée et les tronçons d&rsquo autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d&rsquo autoroute par une arête) :

partie a
la matrice d&rsquo adjacence associée au graphe
(les sommets étant pris dans l&rsquo ordre alphabétique).
. (0,5 point)
Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant E à H.
Préciser ces chemins. (1 point)
partie b
Des contraintes d&rsquo organisation obligent cet homme politique à se rendre dans la ville F après la ville A.
Le graphe est complété ci-dessous par les longueurs en kilomètre de chaque tronçon d&rsquo autoroute.

Déterminer, en utilisant l&rsquo algorithme de Dijkstra, le trajet autoroutier le plus court pour aller de A à F. Préciser la longueur en kilomètre de ce trajet. (1,25 point)
Les thèmes en jeu
Matrice &bull Graphe pondéré &bull Chaîne de longueur donnée &bull Chaîne eulérienne &bull Plus court chemin.
Les conseils du correcteur
Partie A
est égal au nombre de chemins de longueur 3 entre deux sommets donnés.