Exercice

On a schématisé ci-dessus une partie du plan du métro londonien par un graphe Γ dont les sommets sont les stations et les arêtes sont les lignes desservant ces stations.

Chaque station de métro est désignée par son initiale comme indiqué dans la légende.

1 a. Déterminer en justifiant si le graphe Γ est connexe. 0,5 pt

b. Déterminer en justifiant si le graphe Γ est complet. 0,5 pt

2 Déterminer, en justifiant, si le graphe Γ admet une chaîne eulérienne. Si oui, donner une telle chaîne. 0,75 pt

3 Donner la matrice d’adjacence M du graphe Γ (les sommets seront rangés dans l’ordre alphabétique). 0,75 pt

Pour la suite de l’exercice, on donne la matrice :

M 3 =( 2 3 6 4 2 7 3 1 3 0 1 1 2 3 6 4 6 1 4 4 4 9 10 6 4 1 4 4 5 8 8 3 2 2 4 5 2 7 3 1 7 3 9 8 7 8 10 3 3 6 10 8 3 10 4 1 1 4 6 3 1 3 1 0 ).

4 Un touriste se trouve à la station Holborn. Il prévoit de se rendre à la station Green Park en utilisant exactement trois lignes de métro sur son trajet.

a. Sans utiliser le graphe, donner le nombre de trajets possibles et justifier la réponse. 0,75 pt

b. Donner les trajets possibles. 0,75 pt

Sur le graphe pondéré ci-dessus, on a indiqué la durée, exprimée en minutes, des trajets entre chaque station (la durée est indiquée sur chaque arête du graphe Γ).

5 À partir de la station Westminster, ce touriste doit rejoindre la station King’s Cross St Pancras le plus rapidement possible pour prendre un train.

En utilisant l’algorithme de Dijkstra, déterminer le trajet permettant de relier la station Westminster à la station King’s Cross St Pancras en une durée minimale. On précisera cette durée. 1 pt