Cours Stage - Les graphes

Exercice - Graphe et road trip entre amis

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)

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.