Graphes : Algorithme de Dijkstra
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é
Un trajet empruntant une fois et une seule chacune des liaisons d'un graphe correspond à une chaîne eulérienne.
Un graphe admet une telle chaîne si et seulement s'il est connexe et possède exactement 0 ou 2 sommets de degré impair.Le graphe est connexe car il existe toujours un chemin entre deux monuments quelconques.
D'après le graphe, les degrés des sommets sont :- E (Tour Eiffel) : 4
- L (Musée du Louvre) : 4
- M (Tour Montparnasse) : 3
- N (Notre-Dame) : 3
- S (Sacré-Cœur) : 4
- T (Arc de triomphe) : 2
Seuls les sommets M (Tour Montparnasse) et N (Notre-Dame) ont un degré impair.
Le souhait d'emprunter chaque liaison une seule fois est donc réalisable.Un exemple de trajet possible est : M - L - E - T - S - E - M - N - L - S - N.
La matrice d'adjacence $ M $ associée au graphe, avec les sommets classés par ordre alphabétique (E, L, M, N, S, T), est :
$ 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 nombre de trajets de longueur $ k $ reliant deux sommets est donné par le coefficient correspondant dans la matrice $ M^k $.
Ici, on cherche le nombre de trajets entre la cathédrale Notre-Dame (N) et la tour Eiffel (E) en utilisant au maximum trois liaisons (donc des trajets de longueur 1, 2 ou 3).
Le sommet N correspond à la 4ème ligne et le sommet E à la 1ère colonne.- Nombre de trajets de longueur 1 : $ M_{4,1} = 0 $
- Nombre de trajets de longueur 2 : $ (M^2)_{4,1} = 3 $
- Nombre de trajets de longueur 3 : $ (M^3)_{4,1} = 5 $
Le nombre total de trajets est donc : $ 0 + 3 + 5 = 8 $.
Il y a 8 trajets reliant ces deux monuments en trois liaisons maximum.
Pour déterminer le trajet le plus rapide entre la tour Montparnasse (M) et la Basilique du Sacré-Cœur (S), on utilise l'algorithme de Dijkstra.
Sommets E L M N S T Choix Initialisation $ \infty $ $ \infty $ $ 0 $ $ \infty $ $ \infty $ $ \infty $ M (0) Étape 1 $ 10_M $ $ 7_M $ $ 4_M $ $ \infty $ $ \infty $ N (4) Étape 2 $ 10_M $ $ 6_N $ $ 12_N $ $ \infty $ L (6) Étape 3 $ 10_M $ $ 11_L $ $ \infty $ E (10) Étape 4 $ 11_L $ $ 14_E $ S (11) En remontant l'algorithme à partir du sommet S :
- S vient de L (distance 11)
- L vient de N (distance 6)
- N vient de M (distance 4)
Le trajet le plus rapide est M - N - L - S :
Tour Montparnasse $ \rightarrow $ Cathédrale Notre-Dame $ \rightarrow $ Musée du Louvre $ \rightarrow $ Basilique du Sacré-Cœur.La durée de ce trajet est de 11 minutes.