Devoir Surveillé n°2
Terminale ES Spé
Graphes et Dijkstra
Durée 1 heure - Coeff. 3
Noté sur 20 points
Exercice 1. La campagne électorale 15 points
Lors d’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 G ci-dessous, représente les différentes villes de la tournée et les tronçons
d’autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d’autoroute par une arête) :
B
C
A
E F
D
H
Partie A
1. Déterminer, en justifiant, si le graphe G est :
1. a. complet ;
1. b. connexe.
2. Une organisation.
2. a. Justifier qu’il est possible d’organiser la tournée en passant au moins une fois par chaque ville, tout en emprun-
tant une fois et une seule chaque tronçon d’autoroute.
2. b. Citer un trajet de ce type.
3. On appelle M la matrice d’adjacence associée au graphe G (les sommets étant pris dans l’ordre alphabétique).
3. a. Déterminer la matrice M.
3. b. On donne la matrice
0 5 3 5 1 1 4 1
5 2 7 2 8 3 3 5
3 7 6 4 9 3 9 10
5 2 4 0 9 2 3 8
M3 =
1
8 9 9 4 4 10 4
1 3 3 2 4 2 6 6
4 3 9 3 10 6 6 9
1 5 10 8 4 6 9 4
Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant E à H.
Préciser ces chemins.
DS n°2 - Terminale ES Spé - Février 2017
Partie B
Des contraintes d’organisation obligent cet homme politique à se rendre dans la ville F après la ville A. Le graphe G
est complété ci-dessous par les longueurs en kilomètre de chaque tronçon d’autoroute.
B
600
400 C
A 550
400 G
350
600 200
600 450
E F
300
300
400
D
900
H
Déterminer, en utilisant l’algorithme de Dijkstra, le trajet autoroutier le plus court pour aller de A à F.
Préciser la longueur en kilomètre de ce trajet.
[ Fin du devoir \
2/2
