Exercice 4 — Les diagonalistes — Olympiades 2009 Nantes

Sujet

Un diagonaliste est un cycliste qui relie deux des six sommets de l'hexagone Brest, Dunkerque, Strasbourg, Menton, Perpignan, Hendaye, en ne parcourant que des diagonales (pas les côtés de l'hexagone). Les 9 diagonales et leurs distances (km) :

Diagonale	Distance
Dunkerque–Menton	1190
Hendaye–Menton	940
Hendaye–Strasbourg	1170
Brest–Strasbourg	1080
Brest–Menton	1400
Brest–Perpignan	1065
Dunkerque–Hendaye	1050
Dunkerque–Perpignan	1190
Strasbourg–Perpignan	940

Peut-on parcourir une fois et une seule chaque diagonale, sans lever le crayon ?
Relier Dunkerque à Strasbourg : possible directement ? Avec 2, 3, 4, 5, 6 diagonales (chacune utilisée au plus une fois) ? Donner un trajet et sa distance à chaque fois que c'est possible.
Boucle au départ de Dunkerque, première étape à Menton, avec 5 diagonales distinctes : lister tous les trajets possibles et trouver le plus court.
Colorier les 6 villes de sorte que deux villes reliées par une diagonale n'aient jamais la même couleur : nombre minimal de couleurs ?

Question 1 : c'est une question de parcours eulérien (théorème d'Euler, vu en Terminale spécialité) — un graphe admet un tel parcours si et seulement si il a 0 ou 2 sommets de degré impair. Compter le nombre de diagonales partant de chaque ville. Question 4 : c'est un problème de coloration de graphe — le nombre minimal de couleurs est au moins la taille de la plus grande « clique » (ensemble de villes toutes reliées deux à deux).

1. En partant par exemple de Dunkerque (D), la symétrie de la figure ne laisse que deux choix de villes suivantes (Perpignan ou Menton). En explorant systématiquement, on ne peut jamais parcourir les 9 diagonales une fois et une seule — plusieurs trajets de 4, 6 ou 7 diagonales sont trouvés, mais aucun n'atteint 9. (Ce résultat se justifie rigoureusement par le théorème d'Euler, vu en Terminale spécialité : un parcours empruntant chaque arête une fois n'existe que si au plus 2 sommets ont un degré impair.)

2. Dunkerque n'est pas relié directement à Strasbourg (pas de trajet à 1 diagonale). Trajets trouvés :

Trajet	D–P–S	D–M–B–S	D–M–B–P–S	D–P–B–M–H–S	D–M–H–D–P–B–S
Diagonales	2	3	4	5	6
Distance	2130 km	3670 km	4595 km	5765 km	6515 km

⚠️ Le corrigé source indique 2360 km pour le trajet D–P–S (2 diagonales). Or Dunkerque–Perpignan = 1190 km et Perpignan–Strasbourg = 940 km, donc D–P–S = 1190+940 = 2130 km (et non 2360). Les 4 autres distances du corrigé (3670, 4595, 5765, 6515) ont, elles, été recalculées et confirmées exactes.

3. Deux trajets possibles en boucle (Dunkerque → Menton → ⋯ → Dunkerque, 5 diagonales) : D–M–B–S–P–D (5800 km) et D–M–H–S–P–D (5430 km). Le second est le plus court.

4. Les villes D, M et H sont mutuellement reliées (elles nécessitent donc 3 couleurs au minimum). P ne peut pas partager la couleur de D, mais peut avoir celle de M. Un coloriage possible : D et S en rouge, M et P en bleu, H et B en jaune (3 couleurs suffisent).