Un guide de randonnée en montagne décrit les itinéraires possibles autour d'un pic rocheux.
La description des itinéraires est donnée par le graphe ci-contre. Les sommets de ce graphe correspondent aux lieux remarquables. Les arêtes de ce graphe représentent les sentiers possibles entre ces lieux.
Légende :
① | Départ | ② | Passerelle |
③ | Roche percée | ④ | Col des 3 vents |
⑤ | Pic rouge | ⑥ | Refuge |
⑦ | Col vert | ⑧ | Pont Napoléon |
⑨ | Cascade des anglais | ⑩ | Arrivée |
Donner un itinéraire allant de D à A passant par tous les sommets du graphe une seule fois mais n'empruntant pas forcément tous les sentiers.
Existe-t-il un itinéraire allant de D à A utilisant tous les sentiers une seule fois ? Justifier votre réponse.
On note M la matrice d'adjacence associée à ce graphe, les sommets étant pris dans l'ordre. On donne .
Que représente le nombre 89 situé sur la deuxième ligne et la quatrième colonne ?
Déterminer le nombre d'itinéraires allant de D à A empruntant 5 sentiers. Citer un tel itinéraire passant par le pic rouge.
On a complété ci-dessous, le graphe décrivant les itinéraires avec les temps de parcours en minutes pour chacun des sentiers.
Déterminer l'itinéraire allant de D à A le plus court en temps. On fera apparaître la démarche en utilisant un algorithme.
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.