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.
Effectuer un parcours empruntant une fois et une seule toutes les pistes cyclables revient à chercher une . chaîne eulérienneUn graphe connexe admet une chaîne eulérienne si et seulement si le nombre de ses sommets de degré impair est 0 ou 2..
La chaîne A-B-C-E-D-G-F 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éterminons le degré de chacun des sommets.
| Sommets | A | B | C | D | E | F | G |
| Degré | 3 | 4 | 4 | 3 | 4 | 4 | 2 |
Le graphe est connexe et il existe deux sommets de degré impair, il admet donc une chaîne eulérienne commençant par un des deux sommets de degré impair (A ou D) et finissant par le deuxième sommet de degré impair.
Il existe une chaîne eulérienne donc il est possible d'effectuer un parcours empruntant une fois et une seule toutes les pistes cyclables.
À la fin de ce parcours, pourra-t-il rendre sa bicyclette dans la station de départ ? Justifier la réponse.
Il y a deux sommets de degré impair donc il n'existe pas de cycle eulérien
Il n'existe pas de cycle eulérien donc il est impossible d'effectuer un parcours empruntant une fois et une seule toutes les pistes cyclables et de rendre sa bicyclette dans la station de départ.
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.
Les sommets étant classés dans l'odre alphabétique, M est la matrice associée à ce graphe donc les termes de la matrice donnent le nombre de chaînes de longueur 3 reliant deux sommets quelconques.
Il existe deux chaînes de longueur 3 qui relient les sommets E et G ( E-C-F-G et E-B-D-G) or les termes de la matrice T situés à l'intersection de la cinquième ligne et septième colonne ou à l'intersection de la septième ligne et cinquième colonne sont nuls Donc la matrice T ne convient pas.
La matrice N est égale à
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.
Un trajet commençant par le sommet F et finissant par le sommet E en passant par deux sommets exactement (distincts ou non) est une chaîne de longueur 3 commençant par F et finissant E.
Or le nombre de chaînes de longueur 3 reliant le sommet F au sommet E est le terme de la matrice situé à l'intersection de la cinquième ligne et sixième colonne. Dans N, le terme situé à l'intersection de la cinquième ligne et sixième colonne est 11 .
Philippe peut suivre 11 trajets différents.
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.
Pour déterminer le plus court chemin possible pour aller de A à G, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 7 (A) | 11(A) | ∞ | ∞ | 13(A) | ∞ | B (7) | |
| 11 (A) | 22(B) | 21(B) | 13(A) | ∞ | C (11) | ||
| 22(B) | 20(C) | 13(A) | ∞ | F (13) | |||
| 22(B) | 20(C) | 31(F) | E (20) | ||||
| 22(B) | 31(F) | D (22) | |||||
| 27 (D) | G (27) |
Le sommet G étant marqué, pour lire la chaîne de poids minimal, on part de G et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet le plus rapide pour aller de A à G est A-B-D-G. Il faudra prévoir environ 27 minutes pour effectuer ce trajet.
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.