Exercice 1
Des touristes sont logés dans un hôtel H. Un guide souhaite faire visiter la région à ces touristes en
empruntant les routes signalées comme d’intérêt touristique par l’office du tourisme. Les tronçons
de route qu’il souhaite emprunter sont représentés sur le graphe ci-contre. Le long de chaque arête
figure la distance en kilomètres des différents tronçons.
1.
1. a. Le guide peut-il emprunter tous les tronçons de route en passant une et une seule fois sur
chacun d’eux, en partant de l’hôtel et en y revenant ? Justifier la réponse.
1. b. Le guide peut-il emprunter tous les tronçons de route en passant une et une seule fois sur
chacun d’eux, en partant de l’hôtel mais sans forcément y revenir ? Justifier la réponse.
2. Un musée est situé en E. Déterminer le plus court chemin menant de l’hôtel H au musée E. Justifier
la réponse.
Exercice 2
On oriente et on pondère le graphe G ci-dessus pour qu’il représente un réseau d’irrigation
• Le sommet A correspond au départ d’eau, le sommet K au bassin d’infiltration et les autres
sommets représentent les stations de régulation.
• Les arêtes représentent les canaux d’irrigation et les flèches, le sens du ruissellement.
• La pondération donne, en km, les distances entre les différentes stations du réseau.
Déterminer un chemin de longueur minimale entre le départ d’eau en A et le bassin d’infiltration en
K et donner sa longueur.
Exercice 3
Une compagnie aérienne utilise huit aéroports que l’on nomme A, B, C, D, E, F, G et H. Entre certains
de ces aéroports, la compagnie propose des vols dans les deux sens. Cette situation est représentée
par le graphe Γ ci-contre, dans lequel :
• les sommets représentent les aéroports,
• les arêtes représentent les liaisons assurées dans les deux sens par la compagnie.
Les arêtes sont pondérées par le coût de chaque vol, exprimé en euros. Un voyageur partant de
l’aéroport A doit se rendre à l’aéroport G. En utilisant l’algorithme de Dijkstra, déterminer le trajet le
moins cher.
Exercice 4
Un réseau de navettes gratuites est mis en place entre des parkings situés aux abords de la ville et les
principaux sites de la ville. Le graphe ci-contre indique les voies et les temps des liaisons, en minutes,
entre ces différents sites.
1. Peut-on envisager un itinéraire qui relierait le parking P à la gare G en desservant une et une seule
fois tous les sites ?
2. Peut-on envisager un itinéraire qui emprunterait une et une seule fois toutes les voies ?
3. Déterminer un trajet de durée minimale pour se rendre du parking P à la gare G.
Exercice 5
Un club alpin souhaite proposer à ses membres des randonnées de plusieurs jours dans les Alpes. À
cet effet, huit refuges notés A, B, C, D, E, F, G et H ont été sélectionnés. Le graphe G de la partie A
permet de visualiser les différents itinéraires possibles, les sommets représentant les refuges et les
arêtes schématisant tous les sentiers de randonnée balisés les reliant. Le graphe G est complété ci-
dessous par la longueur en kilomètres de chacun des sentiers.
Le club alpin désire aussi proposer à ses membres l’itinéraire le plus court reliant A à H. Déterminer
cet itinéraire et en préciser la longueur en kilomètres.
La coopérative LAFRUITIERE collecte le lait de 7 exploitations de montagne. La situation
géographique est représentée par le graphe ci-dessous, noté GL. La coopérative est située au
sommet A, les autres sommets B, C, D, E, F, G et H représentent les différentes exploitations ; les
arêtes représentent le réseau routier reliant ces exploitations. Les arêtes sont pondérées par les
distances entre les exploitations, exprimées en kilomètres. La coopérative doit collecter du lait
provenant de l’exploitation D ; quel est le plus court parcours pour se rendre de A à D ? Justifier
