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.
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.
Algorithme de Dijkstra
En déduire le temps de transport minimal pour aller du site A au site F.
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.
Chaîne eulérienne
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.