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-dessous.

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

> 1. 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. (1 point)

> 2. Existe-t-il un itinéraire allant de D à A utilisant tous les sentiers une seule fois ? Justifier votre réponse. (1 point)

> 3. On note  la matrice d’adjacence associée à ce graphe, les sommets étant pris dans l’ordre. On donne ci-dessous  :

a) Que représente le nombre 89 situé sur la deuxième ligne et la quatrième colonne ? (0,5 point)

b) Déterminer le nombre d’itinéraires allant de D à A empruntant 5 sentiers. Citer un tel itinéraire passant par le Pic Rouge. (1 point)

> 4. On a complété ci-après 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. (1,5 point)