Un guide de randonnée en montagne décrit les itinéraires possibles autour d&rsquo 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

&gt  1. Donner un itinéraire allant de D à A passant par tous les sommets du graphe une seule fois, mais n&rsquo empruntant pas forcément tous les sentiers. (1 point)

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

&gt  3. On note  la matrice d&rsquo adjacence associée à ce graphe, les sommets étant pris dans l&rsquo 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&rsquo itinéraires allant de D à A empruntant 5 sentiers. Citer un tel itinéraire passant par le Pic Rouge. (1 point)

&gt  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&rsquo 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)