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) :
-
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. -
-
Donner la matrice d’adjacence $M$ associée à ce graphe en classant les sommets par ordre alphabétique.
-
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.
-
-
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.