Graphes - Bac blanc ES Sujet 2 - Maths-cours 2018 (spé)
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 associée à ce graphe en classant les sommets par ordre alphabétique.
On donne :
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 :
Le coefficient situé sur la ligne (correspondant à la cathédrale Notre-Dame de Paris) et la colonne (correspondant à la tour Eiffel) de la matrice 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 ligne et la colonne de la matrice 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 ligne et la colonne de la matrice 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.