Le théorème des quatre couleurs expliqué
En 1852, un jeune mathématicien qui coloriait une carte des comtés d'Angleterre remarqua que quatre couleurs semblaient suffire pour distinguer les comtés voisins. Cela pouvait-il être vrai pour toutes les cartes possibles ? La question devint l'un des problèmes les plus célèbres des mathématiques, suscita une fausse démonstration restée célèbre qui tint onze ans, et fut finalement tranchée en 1976 d'une manière qui changea ce que les mathématiciens acceptent comme preuve.
La question
Francis Guthrie, ancien étudiant d'Augustus De Morgan, demanda si toute carte peut être coloriée avec quatre couleurs de sorte que des pays partageant une frontière reçoivent des couleurs différentes. Deux règles rendent la question précise. Les pays doivent être connexes, chacun d'un seul tenant, et des pays qui ne se rencontrent qu'en un seul point ne comptent pas comme voisins. Trois couleurs ne suffisent manifestement pas toujours, puisqu'un pays entouré d'un anneau de trois autres qui se touchent tous en nécessite une quatrième. La question est de savoir si une cinquième est jamais nécessaire.
Les cartes comme graphes
Marquez un point dans chaque pays et tracez une ligne entre deux points chaque fois que leurs pays partagent une frontière. On obtient un graphe, et comme la carte repose sur une feuille plane, les lignes peuvent être tracées sans se croiser : le graphe est planaire. Colorier la carte, c'est colorier les sommets de ce graphe de sorte que les extrémités de chaque arête soient différentes. Le plus petit nombre de couleurs qui convient est le nombre chromatique, et le théorème des quatre couleurs énonce qu'aucun graphe planaire n'a un nombre chromatique supérieur à quatre.
La preuve de Kempe qui a échoué
En 1879, l'avocat et mathématicien Alfred Kempe publia une démonstration. Son idée astucieuse, appelée aujourd'hui chaînes de Kempe, consiste à échanger deux couleurs le long d'une chaîne connexe de pays pour libérer une couleur là où on en a besoin. La démonstration fut acceptée pendant onze ans, jusqu'à ce que Percy Heawood y trouve une faille en 1890. La réparation de Heawood démontra un résultat plus faible : cinq couleurs suffisent toujours. Les chaînes de Kempe survécurent et devinrent un outil de la démonstration finale.
Pourquoi cinq, c'est facile
Tout graphe planaire possède un sommet ayant au plus cinq voisins ; cela découle de la formule d'Euler, qui limite un graphe planaire à n sommets à au plus 3n − 6 arêtes. Retirez un tel sommet, coloriez le reste de la carte par le même raisonnement, puis remettez le sommet. Si ses voisins utilisent moins de cinq couleurs, l'une est libre. S'ils utilisent les cinq, un échange le long d'une chaîne de Kempe en libère toujours une. Avec quatre couleurs, le même échange peut échouer, et c'est exactement la faille que Kempe n'avait pas vue.
La preuve par ordinateur
En 1976, Kenneth Appel et Wolfgang Haken, de l'université de l'Illinois, démontrèrent le théorème. Ils montrèrent que toute carte contient au moins l'une des 1 936 configurations d'un ensemble inévitable, et que chaque configuration est réductible : une plus petite carte nécessitant cinq couleurs ne pourrait pas la contenir. Vérifier la réductibilité demanda plus de mille heures de calcul sur ordinateur, bien trop pour une vérification à la main. Beaucoup de mathématiciens étaient mal à l'aise face à une démonstration que personne ne pouvait lire en entier, et le débat sur les preuves assistées par ordinateur commença.
Des preuves plus simples et une vérification complète
En 1996, Neil Robertson, Daniel Sanders, Paul Seymour et Robin Thomas publièrent une démonstration plus systématique avec 633 configurations, toujours vérifiée par ordinateur mais plus facile à contrôler. En 2005, Georges Gonthier et Benjamin Werner formalisèrent la démonstration entière dans l'assistant de preuve Coq, de sorte qu'un petit programme de confiance vérifie chaque étape logique. Aujourd'hui, le théorème des quatre couleurs est l'un des résultats les plus minutieusement vérifiés des mathématiques.
Algorithmes de coloration
Trouver une coloration en quatre couleurs d'une carte donnée est rapide en pratique, mais trouver le plus petit nombre de couleurs pour un graphe quelconque est difficile : décider si trois couleurs suffisent est NP-complet. Parmi les méthodes pratiques figurent la coloration gloutonne par ordre de degré décroissant, DSATUR, qui colorie ensuite le sommet le plus contraint, et la recherche par retour sur trace, qui explore les choix et les annule lorsqu'elle est bloquée. La coloration de graphes permet de planifier des examens sans chevauchement, d'attribuer des fréquences radio pour que des émetteurs voisins ne se brouillent pas, et d'allouer les registres dans les compilateurs.
À vous d'explorer
Ouvrez le coloriage de carte des quatre couleurs pour générer des cartes de 4 à 120 pays, les colorier à la main avec quatre couleurs et voir les conflits apparaître en rouge. Laissez la coloration gloutonne, DSATUR ou le retour sur trace résoudre la carte pas à pas, affichez le graphe des pays voisins et vérifiez le nombre minimal de couleurs dont la carte a réellement besoin.
Questions fréquemment posées
Le théorème aide-t-il les cartographes ?
Guère. Les vraies cartes sont généralement coloriées avec davantage de couleurs pour plus de clarté, et elles comportent des océans, des lacs et des pays en plusieurs morceaux, que le théorème ne couvre pas. Son importance est mathématique : il a stimulé le développement de la théorie des graphes et soulevé la question de ce qui compte comme une preuve.
Qu'est-ce qu'une chaîne de Kempe ?
Prenez deux couleurs, disons le rouge et le bleu, et un pays colorié en rouge. Sa chaîne de Kempe est l'ensemble de tous les pays rouges et bleus que l'on peut atteindre à partir de lui en passant uniquement par des voisins rouges et bleus. Échanger le rouge et le bleu dans toute la chaîne conserve une coloration valide et peut libérer une couleur pour un pays voisin de la chaîne.
Pourquoi des pays en plusieurs morceaux mettent-ils le théorème en défaut ?
Si un pays peut se composer de régions séparées qui doivent toutes avoir la même couleur, le graphe des voisins n'est plus planaire, et l'on peut construire des cartes qui nécessitent n'importe quel nombre de couleurs jusqu'à 12 avec deux morceaux par pays, comme l'a étudié Heawood dans son problème des empires.
Pourquoi l'outil crée-t-il des cartes à partir de points ?
Chaque pays est la région du carré plus proche d'un point aléatoire que de tout autre, un diagramme de Voronoï. Cela donne des cartes d'aspect réaliste formées de pays convexes, et deux pays sont voisins exactement lorsque leurs régions partagent un tronçon de frontière, ce que l'application calcule avec précision.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Ouvrir le coloriage de carte des quatre couleurs