Le graphe ci-dessous modélise le réseau routier reliant différents lieux notés A, B, C, D, E, F, G, H et I . Les arêtes sont pondérés par les temps 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. Si oui donner une telle chaîne.
La chaîne H-B-G-A-F-E-D-I-C 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 | I |
| Degré | 4 | 4 | 3 | 4 | 4 | 2 | 2 | 3 | 2 |
Le graphe est connexe et il existe deux sommets de degré impair, il existe donc une chaîne eulérienne commençant par un des deux sommets de degré impair (C ou H) et finissant par le deuxième sommet de degré impair. Par exemple la chaîne : H - E - A - G - B - H - D - E - F - A - B - C - D - I - C.
En précisant la méthode utilisée, déterminer le trajet le plus court (en minutes) pour aller de C à H. Préciser la durée totale de ce trajet.
Pour déterminer le trajet le plus court pour aller de C à H, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | H | I | Sommet sélectionné |
| ∞ | ∞ | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | C (0) |
| ∞ | 8 (C) | 59 (C) | ∞ | ∞ | ∞ | ∞ | 18 (C) | B (8) | |
| 33 (B) | 59 (C) | ∞ | ∞ | 18 (B) | 64 (B) | 18 (C) | G (18) | ||
| 30 (G) | 59 (C) | ∞ | ∞ | 64 (B) | 18 (C) | I (18) | |||
| 30 (G) | 58 (I) | ∞ | ∞ | 64 (B) | A (30) | ||||
| 58 (I) | 45 (A) | 37 (A) | 64 (B) | F (37) | |||||
| 58 (I) | 42 (F) | 64 (B) | E (42) | ||||||
| 54 (E) | 64 (B) | D (54) | |||||||
| 63 (D) | H (63) |
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 possible pour aller de C à H est C - B - G - A - F - E - D - H. Le temps de parcours est de 63 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.