Une agence de tourisme propose la visite de certains monuments parisiens.

Chacun de ces monuments est désigné par une lettre comme suit :

• E : Tour Eiffel

• L : Musée du Louvre

• M : Tour Montparnasse

• N : Cathédrale Notre-Dame de Paris

• S : Basilique du Sacré-Cœur de Montmartre

• T : Arc de triomphe

Cette agence fait appel à une société de transport par autocar qui propose les liaisons suivantes (chacune de ces liaisons pouvant s'effectuer dans les deux sens de circulation) :

1. Expliquer pourquoi il est possible de trouver un trajet empruntant une fois et une seule chacune des dix liaisons indiquées sur le graphe.
   Donner un exemple d'un tel trajet.

2. 1. Donner la matrice d'adjacence $M$ associée à ce graphe en classant les sommets par ordre alphabétique.

   2. On donne :

      $M^2 = \begin{pmatrix} 4 &2 &1 &3 &2 &1 \\ 2 &4 &2 &2 &2 &2 \\ 1 &2 &3 &1 &3 &1 \\ 3 &2 &1 &3 &1 &1 \\ 2 &2 &3 &1 &4 &1\\ 1 &2 &1 &1 &1 &2 \end{pmatrix}$

      $M^3 = \begin{pmatrix} 6 &10 &9 &5 &10 &6 \\ 10 &8 &8 &8 &10 &4 \\ 9 &8 &4 &8 &5 &4 \\ 5 &8 &8 &4 &9 &4 \\ 10 &10 &5 &9 &6 &6\\ 6 &4 &4 &4 &6 &2 \end{pmatrix}$

      Combien y a-t-il de trajets permettant de relier la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant au maximum trois liaisons.
      Justifier votre réponse.

3. On complète le graphe précédent en indiquant, sur chacune des branches, la durée du trajet, en minutes, entre deux monuments.

   

   On souhaite aller de la tour Montparnasse à la Basilique du Sacré-Cœur de Montmartre.

   En utilisant un algorithme, déterminer le trajet le plus rapide ainsi que la durée de ce trajet.