Une agence de voyages organise différentes excursions dans une région du monde et propose la visite de sites incontournables, nommés A, B, C, D, E et F.
Ces excursions sont résumées sur le graphe ci-dessous dont les sommets désignent les sites, les arêtes représentent les routes pouvant être empruntées pour relier deux sites et le poids des arêtes désigne le temps de transport (en heures) entre chaque site.
Justifier que ce graphe est connexe.
La chaîne ABCDEF contient tous les sommets de ce graphe ; donc deux sommets quelconques peuvent être reliés par une chaîne.
Ce graphe est connexe.
Un touriste désire aller du site A au site F en limitant au maximum les temps de transport
En utilisant un algorithme, déterminer la plus courte chaîne reliant le sommet A au sommet F.
Pour déterminer le parours du site A au site F en limitant au maximum les temps de transport on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 7 (A) | ∞ | 15(A) | ∞ | ∞ | B (7) | |
| 19 (B) | 15(A) | 11 (B) | 23(B) | E (11) | ||
| 19 (B) | 13 (E) | 23(B) | D (13) | |||
| 18 (D) | 23(B) | C (18) | ||||
| 21 (C) | F (21) |
Le sommet F étant marqué, pour lire la chaîne de poids minimal, on part de F et on "remonte" la chaîne en suivant les prédécesseurs. .
La plus courte chaîne reliant le sommet A au sommet F est A-B-E-D-C-F.
En déduire le temps de transport minimal pour aller du site A au site F.
Le poids de la plus courte chaîne A-B-E-D-C-F reliant le sommet A au sommet F est 21.
Le temps de transport minimal pour aller du site A au site F est de 21 heures.
Un touriste désirant apprécier un maximum de paysages souhaite suivre un parcours empruntant toutes les routes proposées une et une seule fois.
Si ce parcours existe, le décrire sans justifier ; dans le cas contraire justifier qu'un tel parcours n'existe pas.
Déterminer un parcours empruntant toutes les routes proposées une et une seule fois revient à chercher une chaîne eulérienne.
Or ce graphe contient quatre sommets de degré 3 ( C, D, E et F ), il n'existe pas de chaîne eulérienne.
Il n'existe pas de parcours empruntant toutes les routes proposées une et une seule fois.
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.