Le graphe ci-dessous modélise le réseau routier reliant différents lieux notés A, B, C, D, E, F, G et H. Les arêtes sont pondérées par les temps moyens de parcours, en minutes, en tenant compte des difficultés de la circulation.
Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse.
La chaîne A-B-F-E-D-C-G-H contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe est connexe.
Déterminons le degré de chacun des sommets.
Sommets | A | B | C | D | E | F | G | H | |
Degré | 3 | 4 | 4 | 4 | 2 | 4 | 2 | 3 | 2 |
Le graphe est connexe et il existe deux sommets de degré impair, il existe donc une chaîne eulérienne d'extrémités A et H.
En précisant la méthode utilisée, déterminer le trajet le plus court (en minutes) pour aller de A à H. Préciser la durée totale de ce trajet.
Pour déterminer le trajet le plus court pour aller de A à H, on utilise l'algorithme de Dijkstra.
A | B | C | D | E | F | G | H | Sommet sélectionné |
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
7 (A) | ∞ | 24 (A) | ∞ | 15 (A) | ∞ | ∞ | B (7) | |
33 (B) | 24 (A) | ∞ | 13 (B) | ∞ | 44 (B) | F (13) | ||
33 (B) | 21 (F) | 19 (F) | ∞ | 44 (B) | E (19) | |||
33 (B) | 21 (F) | ∞ | 44 (B) | D (21) | ||||
30 (D) | ∞ | 44 (B) | C (30) | |||||
35 (C) | 43 (C) | G (35) | ||||||
42 (G) | H (42) |
Le sommet H étant marqué, pour lire la chaîne de poids minimal, on part de H et on remonte la chaîne en suivant les prédécesseurs. .
Le trajet le plus court pour aller de A à H est A - B - F - D - C - G - H. Le temps de parcours est de 42 minutes.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.