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 :
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 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.