Exercice 4 (5 points)
Candidats ayant suivi l’enseignement de spécialité
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.
Corrigé
-
Trouver un trajet qui emprunte une fois et une seule chacune des liaisons \indiquées sur \le graphe revient à déterminer une chaî\ne eulérienne.
Le théorème d’Euler \indique qu’un graphe connexe contient une chaî\ne eulérienne si et seulement s’il \ne possède que 0 ou 2 sommets de degré impair.
Les degrés des sommets sont \indiqués dans \le tableau ci-après :
Sommet E L M N S T Degré 4 4 3 3 4 2 Le graphe comporte deux sommets de degré impair : M et N. Il est donc possible de relier M (Tour Montparnasse) à N (Cathédrale Notre-Dame de Paris) en empruntant une fois et une seule chacune des liaisons; par exemple : M-E-T-S-E-L-S-N-L-M-N.
-
-
En classant \les sommets par ordre \alphabétique, on obtient la matrice d’adjacence suivante :
$$M = \begin{pmatrix} 0 &1 &1 &0 &1 &1 \\ 1 &0 &1 &1 &1 &0 \\ 1 &1 &0 &1 &0 &0 \\ 0 &1 &1 &0 &1 &0 \\ 1 &1 &0 &1 &0 &1\\ 1 &0 &0 &0 &1 &0 \end{pmatrix}$$
-
Le coefficient situé sur la $4^{\text{e}}$ ligne (correspondant à la cathédrale Notre-Dame de Paris) et la $1^{\text{ère}}$ colonne (correspondant à la tour Eiffel) de la matrice $M$ est égal à 0.
Il n’y a donc aucun trajet reliant la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant une et une seule liaison.Le coefficient situé sur la $4^{\text{e}}$ ligne et la $1^{\text{ère}}$ colonne de la matrice $M^2$ est égal à 3.
Il y a donc 3 trajets reliant la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant exactement deux liaisons.Le coefficient situé sur la $4^{\text{e}}$ ligne et la $1^{\text{ère}}$ colonne de la matrice $M^3$ est égal à 5.
Il y a donc 5 trajets reliant la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant exactement trois liaisons.Au total, on trouve qu’il existe exactement huit trajets permettant de relier la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant au maximum trois liaisons.
-
-
On utilise l’algorithme de Dijkstra :
Reportez-vous à la page « méthode » : l’algorithme de Dijkstra étape par étape pour obtenir la méthode de construction détaillée de ce tableau.
Le trajet le plus rapide pour aller de la tour Montparnasse à la Basilique du Sacré-Cœur de Montmartre est le trajet M-N-L-S, c’est à dire Montparnasse – Notre-Dame de Paris – Louvre – Sacré-Cœur.
Sa durée est de 11 minutes.