On a schématisé ci-dessous 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.
Légende
|
Déterminer en justifiant si le graphe Γ est connexe.
La chaîne B - O - K - H - P - E - W - G contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe Γ est connexe.
Déterminer en justifiant si le graphe Γ est complet.
Les sommets B et K ne sont pas adjacents donc le graphe Γ n'est pas complet.
Déterminer, en justifiant, si le graphe Γ admet une chaîne eulérienne. Si oui, donner une telle chaîne.
Légende
|
Le graphe étant connexe, déterminons le degré de chacun des sommets :
Sommets | B | E | G | H | K | O | P | W |
Degré | 2 | 2 | 4 | 3 | 2 | 5 | 4 | 2 |
Le graphe est connexe et il n'y a que deux sommets H et O de degré impair, il existe donc une chaîne eulérienne d'extrémités H et O. Par exemple la chaîne O - H - K - O - P - G - O - B - G - W - E - P - H.
Donner la matrice d'adjacence M du graphe Γ (les sommets seront rangés dans l'ordre alphabétique).
La matrice d'adjacence M du graphe Γ est :
Pour la suite de l'exercice, on donne la matrice .
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.
Sans utiliser le graphe, donner le nombre de trajets possibles et justifier la réponse.
Les termes de la matrice donnent le nombre de chaînes de longueur 3 entre deux sommets du graphe.
Le terme de la matrice situé à l'intersection de la quatrième ligne et de la troisième colonne est égal à 4. En partant de la station Holborn, il existe quatre trajets utilisant exactement trois lignes de métro pour se rendre à la station Green Park.
Donner les trajets possibles .
Les quatre trajets possibles sont : H - K - O - G ; H - O - B - G ; H - O - P - G et H - P - O - G.
Légende
|
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 Γ ).
À 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.
Légende
|
B | E | G | H | K | O | P | W | Sommet sélectionné |
∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | W (0) |
∞ | 2 (W) | 3 (W) | ∞ | ∞ | ∞ | ∞ | E (2) | |
∞ | 3 (W) | ∞ | ∞ | ∞ | 6 (E) | G (3) | ||
4 (G) | ∞ | ∞ | 5 (G) | 5 (G) | B (4) | |||
∞ | ∞ | 5 (G) | 5 (G) | O (5) | ||||
6 (O) | 10 (O) | 5 (G) | P (5) | |||||
6 (O) | 10 (O) | H (6) | ||||||
9 (H) | K (9) |
Le sommet K étant marqué, pour lire la chaîne de poids minimal, on part de K et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet permettant de relier la station Westminster à la station King's Cross St Pancras en une durée minimale est W - G - O - H - K. La durée dece trajet est de 9 minutes.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.