Une association organise un rallye sportif en VTT : six zones de regroupement sont déterminées et sont reliées par des chemins.
Ce parcours est modélisé par le graphe ci-dessous, où les sommets de A à F représentent les zones de regroupement, et les arêtes les chemins.
Les arêtes sont pondérées par les distances, exprimées en kilomètres, nécessaires pour parcourir ces chemins.
Les candidats sont positionnés initialement sur la zone A et doivent, après avoir parcouru tous les chemins, revenir à la zone initiale.
Chaque fois qu'un candidat emprunte pour la première fois un chemin il doit déposer, à un endroit précis, un jeton personnalisé, attestant son passage.
Quel nombre minimal de jetons est-il nécessaire de donner à chaque candidat ?
Un candidat souhaite faire le parcours, en empruntant tous les chemins une fois et une seule. Est-ce possible ? Justifier la réponse.
Existe-t-il un cycle eulérien ?
Soit M la matrice associée au graphe G ( on ordonne les sommets dans l'ordre alphabétique).
Écrire la matrice M.
On donne les matrices et
Un candidat est actuellement au point de rendez-vous D et on lui signale qu'il a oublié son dossard au point B. Devant le récupérer, il souhaite emprunter au maximum trois chemins.
Combien a-t-il de possibilités ?
Donner, le trajet correspondant à la distance la plus courte lui permettant d'aller récupérer son dossard.
Pour déterminer le trajet le plus court pour aller de A à H, on utilise l'algorithme de Dijkstra.
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.