Suite à des intempéries, un chasse-neige doit déblayer toutes les routes reliant les stations de son secteur. On modélise ce secteur par le graphe ci-dessous dont les sommets représentent les différentes stations désignées par des lettres. Les poids des arêtes sont les durées moyennes de parcours, en minute, du chasse-neige entre deux stations.
Le chasse-neige part de la station G. Peut-il partir de cette station et y revenir en parcourant une et une seule fois chacune des routes, matérialisées par les arêtes de ce graphe ?
Les sommets A et F sont de degré 5 donc, il n'existe pas de cycle eulérien. Par conséquent, le chasse-neige ne peut pas partir de la station G et y revenir en parcourant une et une seule fois chacune des routes.
Une saleuse doit de même parcourir l'ensemble des routes du secteur après déblaiement de la neige. Elle est garée à la station A et, après son travail, peut se garer dans n'importe quelle station.
Peut-elle parcourir une et une seule fois chacune des routes pour traiter l'ensemble du secteur ?
Le cycle G - A - F - D - E - C - B - G contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets, il existe une chaîne les reliant. Donc le graphe est connexe.
Le graphe est connexe et il n'y a que deux sommets de degré impair A et F par conséquent, il existe des chaînes eulériennes d'extrémités A et F.
Le technicien peut parcourir l'ensemble du réseau en empruntant chaque route une et une seule fois.
On appelle M la matrice d'adjacence associée au graphe, les sommets étant rangés dans l'ordre alphabétique et on donne : .
Interpréter dans le contexte de l'exercice le nombre 10 figurant en caractère gras dans la matrice.
Le nombre de chaînes de longueur 4 joignant le sommet i au sommet j est donné par le terme d'indice i , j de la matrice .
Il existe 10 trajets joignant la station G à la station D en 4 étapes.
Déterminer, pour le chasse-neige, le chemin le plus rapide pour aller de la station G à la station D. On donnera le parcours trouvé ainsi que sa durée totale.
Déterminons le chemin le plus rapide pour aller de la station G à la station D à l'aide de l'algorithme de Dijkstra.
| G | A | B | C | D | E | F | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | G (0) |
| 14 (G) | 38 (G) | ∞ | ∞ | ∞ | ∞ | A (14) | |
| 38 (G) | 78 (A) | ∞ | 49 (A) | 106 (A) | B (38) | ||
| 78 (A) | ∞ | 49 (A) | 106 (A) | E (49) | |||
| 78 (A) | 111 (E) | 72 (E) | F (72) | ||||
| 78 (A) | 89 (F) | C (78) | |||||
| 89 (F) | D (89) |
Le sommet D étant marqué, pour lire la chaîne de poids minimal, on part de D et on "remonte" la chaîne en suivant les prédécesseurs : .
Le chemin le plus rapide pour aller de la station G à la station D est G - A - E - F - D pour une durée de 89 minutes.
Le conducteur du chasse-neige part de la station G et va directement à la station A. Il apprend alors que la route allant de la station E à la station F est barrée.
Commentpeut-il terminer son parcours au plus vite jusqu'à la station D ? Préciser le temps qu'il mettrait alors pour finir son parcours. Aucune justification n'est attendue ici.
D'après les différentes étapes de l'algorithme de Dijkstra effectué dans la question précédente :
Le chemin le plus rapide pour aller de la station G à la station D sans passer par la route allant de la station E à la station F est G - A - E - D pour une durée de 111 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.