Graphes – Trajet minimal – Bac ES Polynésie française 2008
Exercice 2
5 points - Candidats ayant suivi l'enseignement de spécialité
Une grande ville a mis en place un système de location de bicyclettes en libre service.
Un abonné peut ainsi louer une bicyclette dans une station puis la déposer dans n'importe quelle station de son choix.
La ville compte sept stations de location nommées A, B, C, D, E, F et G.
Les stations sont reliées entre elles par une piste cyclable et les temps de parcours en minutes sont indiqués sur le graphe ci-dessous.
Philippe, cycliste très prudent, décide de visiter cette ville en n'empruntant que des pistes cyclables.
- A-t-il la possibilité d'effectuer un parcours empruntant une fois et une seule toutes les pistes cyclables ? Justifier la réponse.
- A la fin de ce parcours, pourra-t-il rendre sa bicyclette dans la station de départ ? Justifier la réponse.
On appelle M la matrice associée à ce graphe. On donne deux matrices N et T :
$ N=\begin{pmatrix}4 & 9 & 8 & 5 & 5 & 9 & 2 \\ 9 & 6 & 10 & 7 & 10 & 6 & 4 \\ 8 & 10 & 8 & 5 & 10 & 9 & 4 \\ 5 & 7 & 5 & 2 & 8 & 4 & 5 \\ 5 & 10 & 10 & 8 & 6 & 11 & 2 \\ 9 & 6 & 9 & 4 & 11 & 4 & 6 \\ 2 & 4 & 4 & 5 & 2 & 6 & 0 \end{pmatrix} $$ T=\begin{pmatrix} 4 & 9 & 8 & 4 & 5 & 9 & 1 \\ 9 & 6 & 10 & 6 & 10 & 6 & 4 \\ 8 & 10 & 8 & 4 & 10 & 9 & 4 \\ 5 & 7 & 5 & 2 & 8 & 4 & 5 \\ 5 & 8 & 10 & 8 & 6 & 11 & 0 \\ 9 & 6 & 9 & 4 & 11 & 4 & 6 \\ 1 & 4 & 4 & 5 & 0 & 6 & 0 \end{pmatrix} $- Une des deux matrices N ou T est la matrice M³. Sans calculs, indiquer quelle est la matrice M³ en justifiant la réponse.
- Philippe a loué une bicyclette à la station F et l'a rendue à la station E. Au cours de son déplacement, il est passé exactement deux fois devant une station. Combien de trajets différents a-t-il pu suivre ? Expliquer.
- Le lendemain, il envisage de rejoindre le plus rapidement possible la station $ G $ en partant de la station A.
À l'aide d'un algorithme, déterminer un tel parcours et donner alors le temps nécessaire pour l'effectuer.
Corrigé
Pour déterminer s'il est possible d'effectuer un tel parcours (chaîne eulérienne), on calcule le degré de chaque sommet :
- A : 3 (relié à B, C, F)
- B : 4 (relié à A, C, D, E)
- C : 4 (relié à A, B, E, F)
- D : 3 (relié à B, E, G)
- E : 4 (relié à B, C, D, F)
- F : 4 (relié à A, C, E, G)
- G : 2 (relié à D, F)
Le graphe possède exactement 2 sommets de degré impair (A et D).
Or, d'après le théorème d'Euler, un graphe admet une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est égal à 0 ou 2.
Philippe a donc la possibilité d'effectuer un tel parcours (en commençant par A et en finissant par D, ou inversement).- Un parcours revenant à la station de départ en empruntant chaque piste une seule fois correspond à un cycle eulérien.
L'existence d'un cycle eulérien nécessite que tous les sommets soient de degré pair.
Comme A et D sont de degré impair, il ne pourra pas revenir à son point de départ par un tel parcours.
La matrice $ M^3 $ donne le nombre de chemins de longueur 3 entre deux sommets.
Considérons le nombre de chemins de longueur 3 reliant le sommet G (7ème ligne/colonne) à lui-même.
Un chemin de longueur 3 de G à G est un cycle de longueur 3 passant par G. Or G n'est relié qu'à D et F, et il n'y a pas d'arête directe entre D et F. Il n'existe donc aucun triangle (cycle de longueur 3) passant par G.
On doit donc avoir $ (M^3)_{7,7} = 0 $.
C'est le cas pour les deux matrices N et T.Regardons alors le nombre de chemins de longueur 3 entre A (sommet 1) et G (sommet 7).
Les chemins de longueur 3 sont de la forme A-X-Y-G.
Comme G est relié à D et F, Y doit être D ou F.- Si Y = D : les voisins de D sont B, E, G. Donc X peut être B ou E. Or A est relié à B ($ A-B-D-G $) mais A n'est pas relié à E.
- Si Y = F : les voisins de F sont A, C, E, G. Donc X peut être A, C ou E. Or A est relié à C ($ A-C-F-G $) mais A n'est pas relié à E.
Il y a donc 2 chemins de longueur 3 entre A et G. La matrice $ M^3 $ doit avoir le coefficient 2 à la ligne 1, colonne 7.
Il s'agit donc de la matrice N.- Philippe est passé exactement deux fois devant une station entre F et E. Son trajet est donc composé de 3 liaisons (longueur 3).
Le nombre de tels trajets est donné par le coefficient de la 6ème ligne (F) et 5ème colonne (E) de la matrice $ M^3 $, soit $ N_{6,5} $.
D'après la matrice N, il y a 11 trajets différents.
Pour trouver le trajet le plus rapide de A vers G, on utilise l'algorithme de Dijkstra.
Sommets A B C D E F G Choix Initialisation 0 $ \infty $ $ \infty $ $ \infty $ $ \infty $ $ \infty $ $ \infty $ A (0) Étape 1 $ 7_A $ $ 11_A $ $ \infty $ $ \infty $ $ 13_A $ $ \infty $ B (7) Étape 2 $ 11_A $ $ 23_B $ $ 21_B $ $ 13_A $ $ \infty $ C (11) Étape 3 $ 23_B $ $ 20_C $ $ 13_A $ $ \infty $ F (13) Étape 4 $ 23_B $ $ 20_C $ $ 31_F $ E (20) Étape 5 $ 23_B $ $ 31_F $ D (23) Étape 6 $ 28_D $ G (28) Le trajet le plus court est donc A - B - D - G.
Le temps nécessaire pour l'effectuer est de 28 minutes.