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.
Existe-til une chaîne eulérienne ?
À la fin de ce parcours, pourra-t-il rendre sa bicyclette dans la station de départ ? Justifier la réponse.
Existe-til un cycle eulérien ?
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 . Sans calculs, indiquer quelle est la matrice en justifiant la réponse.
Existe-t-il une chaîne de longueur 3 pour aller de E à G ?
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-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.
Algorithme de Dijkstra.
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.