Théorie des graphes : Ds devoir surveille algorithme de dijkstra 45 min
Télécharger PDFTES 17 mars 2016
DS Devoir surveillé
Algorithme de Dijkstra - 45 min
Exercice110 points
Dans le graphe ci-dessous, .A BC DEF G
1.Tableau des sommets-degrés
SommetABCDEFG
Degrés2455442
2. (a) La matriceMassociée au graphe estM=
0 1 1 0 0 0 0
1 0 1 1 1 0 0
1 1 0 1 1 1 0
0 1 1 0 1 1 1
0 1 1 1 0 1 0
0 0 1 1 1 0 1
0 0 0 1 0 1 0
(b) On donne la matriceM3 =
2 7 8 5 5 5 3
7 8 12 13 12 8 5
8 12 12 15 13 13 5
5 13 15 12 13 12 8
5 12 13 13 10 12 5
5 8 13 12 12 8 7
3 5 5 8 5 7 2
Le nombre de chemins de longueur 3 reliantAetFet le coefficientM3 1,6
= 5. Il y a donc 5 chemins possibles
Liste des chemins : A-B-C-F A-B-E-F A-B-D-F A-C-D-F A-C-E-F
3. Le graphe correspondant aux voies d’accès principales estconnexeet possèdedeux seuls sommetsC et D
dedegré impair. Or d’aprèsle théorème d’Euler, ce graphe admet une chaîne eulérienne d’extrémités C et
D, donc le candidat pourra parcourir ce quartier sans emprunter plusieurs fois la même voie.
On pourra utiliser l’algorithme d’Euler pour proposer un trajet (une chaîne eulérienne) .
Par exemple : la chaîne C - B - E - D - F - G - D - B - A - C - E - F - C - D est une chaîne eulérienne et
représente un parcours possible pour le candidat.
Lycée Dumont d’UrvillePage 1/2Tournez, SVP !
4. Dans le graphe ci-dessous, les valeurs indiquent, en minutes, les durées moyennes des trajets entre les différents
lieux via les transports en commun.A BC DEF G8 128 420 1224 2016 412 48 a)L’algorithme de Dijkstrapour déterminer le chemin le plus court de A à G.
ABCDEFG0
0∞∞∞∞∞∞A(0)|8 A4 A
∞∞∞∞C(4)|8 A,612 C|20 C16 C24 C∞B(8) |||620C et12B 16C ,620B 24C ∞D(12)||||16 C,624 D24 C,636 D32 DE(16) |||||624C ,20E 32D F(20)
||||||632D ,28F G(28)
L’algorithme nous permet d’écrire :
A(0)⇐=C(4)⇐=E(16)⇐=F(20)⇐=G(28)
Donc le chemin de durée minimale que ce candidat devra emprunter pour arriver à son rendez-vous est :
A - C - E - F - G
b) Le temps pour effectuer ce trajet de durée minimale est de :28 minutes
Lycée Dumont d’UrvillePage 2/2Fin