L'énoncé
Un groupe d'amis décide de partir en vacances. Pour choisir leur destination, il décident de représenter les villes dans lesquelles ils veulent absolument passer sur un graphe. En partant de Paris en voiture, ils veulent visiter Marseille, Bordeaux, Lyon, Nantes et Lille, mais pour éviter de passer trop de temps en voiture d'un coup, ils refusent de faire plus de 650 km en une fois. Quelques recherches sur internet plus trad, ils obtiennent les informations suivantes :
Distances
Paris-Nantes : 384 km
Paris-Lille : 225 km
Paris-Lyon : 465 km
Paris-Marseille : 776 km
Paris-Bordeaux : 584 km
Lille-Nantes : 600 km
Lille-Lyon : 691 km
Lille-Marseille : 1000 km
Lille Bordeaux : 800 km
Nantes-Lyon : 685 km
Nantes-Marseille : 986 km
Nantes-Bordeaux : 346 km
Lyon-Bordeaux : 552 km
Lyon-Marseille : 315 km
Marseille-Bordeaux : 645 km
Question 1
Dessiner au brouillon un graphe en représentant Lille, Paris, Nantes, Lyon, Marseille et Bordeaux. Les arêtes correspondent aux routes reliant les différentes villes que les voyageurs sont prêts à prendre, et indiquer sur chaque arête la distance séparant les villes.
Question 2
De Lille, quel est le moyen le plus rapide d'aller à Marseille ?
Ici, le trajet le plus direct est celui passant par Paris, puis Lyon et enfin Bordeaux : cela correspond à 1 005 km.
Question 3
Quel chemin permet de rallier toutes le villes en parcourant le moins de km ?
On remarque que le chemin le plus court correspond à une boucle : Paris - Lille - Nantes - Bordeaux - Marseille - Lyon (2 131 km)
.png?1566251366422)
En effet, le même chemin mais en sens inverse est plus long car la distance Paris-Lyon est plus grande que Paris-Lille, et toute autre solution nécessite de repasser par une ville, ce qui rallongera forcément le trajet.
Il est possible de passer plusieurs fois par la même ville.
Question 4
Donner le centre, le rayon et le diamètre du graphe.
Lille et Marseille sont éloignés d'une distance de 3.
La distance séparant Lyon, Nantes et Paris des autres sommets est toujours inférieure ou égale à deux. Ils sont donc tous trois centre du graphe.
Le rayon est donc de 2, le diamètre est de 3.
Question 5
Le trajet optimal est-il nécessairement celui qui part d'un centre du graphe ? Justifier.
Le trajet optimal n'est pas forcément celui qui part d'un centre du graphe. En effet, nous avons vu que le trajet optimal correspond à réaliser un cercle. Cependant, pour optimiser le trajet, il faut supprimer la plus grande distance : Bordeaux-Marseille.
Ainsi, le trajet optimal serait Bordeaux - Nantes - Lille - Paris - Lyon - Marseille.
Ou dans l'autre sens : Marseille - Lyon - Paris - Lille - Nantes - Bordeaux.