Glossaire

Sélectionnez l'un des mots clés à gauche…

Graphes et réseauxColoration de la carte

Temps de lecture: ~15 min

Nous avons déjà utilisé la théorie des graphes avec certaines cartes. En faisant un zoom arrière, des routes et des ponts disparaissent et nous voyons les contours de pays entiers.

Lors de la coloration d'une carte - ou de tout autre dessin constitué de régions distinctes - les pays adjacents ne peuvent pas avoir la même couleur. Nous pourrions aussi vouloir utiliser le moins possible de couleurs différentes.

Certaines «cartes» simples, comme un échiquier, n'ont besoin que de deux couleurs (noir et blanc), mais la plupart des cartes complexes nécessitent davantage.

Lorsque vous colorez la carte des États américains, 50 couleurs suffisent évidemment, mais il en faut beaucoup moins. Essayez de colorier les cartes ci-dessous avec le moins de couleurs possible:

États Unis

Nombre de couleurs: 0

Amérique du sud

Nombre de couleurs: 0

Allemagne

Nombre de couleurs: 0

Angleterre

Nombre de couleurs: 0

Toutes ces cartes peuvent être colorées avec seulement quatre couleurs différentes, mais il n’est pas difficile d’imaginer que d’autres cartes très complexes pourraient nécessiter beaucoup plus de couleurs. En fait, certaines cartes nécessitent au moins couleurs, lorsqu'elles contiennent quatre pays connectés entre eux.

Comme auparavant, nous pouvons convertir une carte avec des pays et des frontières en un graphique planaire: chaque pays devient et les pays qui sont reliés par un bord:

Nous souhaitons maintenant colorer les sommets d'un graphique. Deux sommets doivent avoir une couleur différente s'ils sont connectés par une arête.

En 1852, l’étudiant en botanique Francis Guthrie doit colorier une carte des comtés d’Angleterre. Il a observé que quatre couleurs semblaient suffisantes pour toutes les cartes testées, mais il n’a pas été en mesure de trouver une preuve valable pour toutes les cartes. Cela s'est avéré être un problème extrêmement difficile et a été baptisé théorème des quatre couleurs.

Au cours des 100 années suivantes, de nombreux mathématiciens ont publié des «preuves» du théorème des quatre couleurs, uniquement pour que des erreurs soient trouvées ultérieurement. Certaines de ces preuves non valides étaient si convaincantes qu'il a fallu plus de 10 ans pour découvrir des erreurs.

Pendant longtemps, les mathématiciens ont été incapables de prouver que quatre couleurs suffisaient ou de trouver une carte nécessitant plus de quatre couleurs.

Le problème des quatre couleurs n’a guère progressé jusqu’en 1976, lorsque Wolfgang Haken et Kenneth Appel utilisaient enfin un ordinateur pour le résoudre. Ils ont réduit un nombre infini de cartes possibles à 1936 cas particuliers, qui ont été vérifiés par un ordinateur prenant plus de 1000 heures au total.

Le théorème des quatre couleurs est le premier théorème mathématique bien connu à avoir été prouvé à l'aide d'un ordinateur, ce qui est devenu beaucoup plus courant et moins controversé depuis. Des ordinateurs plus rapides et un algorithme plus efficace signifient qu'aujourd'hui, vous pouvez résoudre le théorème des quatre couleurs sur un ordinateur portable en seulement quelques heures.

Cachet postal du département de mathématiques de l'Université
de l'Illinois Urbana-Champaign, où travaillaient Haken et Appel.

Le théorème des quatre couleurs ne fonctionne que pour les cartes sur un plan plat ou une sphère et où tous les pays se composent d'une seule zone.

Cependant, les mathématiciens ont également examiné des cartes de empires, où les pays peuvent être constitués de plusieurs composants déconnectés, ainsi que des cartes de planètes de formes différentes, telles qu'un tore (forme de beignet). Dans ces cas, vous aurez peut-être besoin de plus de quatre couleurs et les épreuves deviennent encore plus difficiles.

Cette carte sur tore nécessite sept couleurs.

Archie