Pays
Frontières
Couleurs utilisées
Conflits

En savoir plus sur le théorème des quatre couleurs

Coloriage de carte du théorème des quatre couleurs

Aussi compliquée que soit une carte, quatre couleurs suffisent toujours pour la colorier de sorte que des pays qui partagent une frontière n'aient jamais la même couleur. L'énoncé est assez simple pour qu'un enfant le teste avec des crayons de couleur, et pourtant il a fallu plus d'un siècle et un ordinateur pour le démontrer. Coloriez vous-même une carte aléatoire, voyez quelles frontières sont en conflit, puis regardez trois méthodes s'en charger, d'une règle gloutonne rapide qui a parfois besoin d'une cinquième couleur à une recherche par retour sur trace qui s'en sort toujours avec quatre. Choisissez une couleur et cliquez sur des pays pour les colorier ; une frontière devient rouge quand deux voisins ont la même couleur. Des pays qui ne se touchent qu'en un coin peuvent avoir la même. Ou laissez faire l'ordinateur : choisissez une méthode et appuyez sur Résoudre pour la regarder travailler, ou sur Étape pour suivre un coup à la fois. Minimum de couleurs vérifie si cette carte pourrait se contenter de trois couleurs, voire de deux. Nouvelle carte dessine une autre carte, et Afficher les voisins dessine le réseau des pays qui partagent une frontière.

Comment ça marche

  1. Choisissez le nombre de pays et appuyez sur Nouvelle carte, ou commencez avec la carte affichée.
  2. Choisissez une couleur et cliquez sur des pays pour les colorier, en surveillant les frontières rouges là où des voisins sont en conflit.
  3. Choisissez une méthode et appuyez sur Résoudre ou Étape pour la regarder colorier la carte, puis appuyez sur Minimum de couleurs pour voir de combien de couleurs cette carte a besoin.

Des cartes aux graphes

Placez un point dans chaque pays et reliez deux points lorsque leurs pays partagent une frontière. La carte devient un graphe, et colorier la carte revient à colorier les points de sorte que des points reliés soient différents. Comme les cartes sont dessinées sur une feuille plane, ces graphes sont planaires : on peut les dessiner sans que les lignes se croisent. Des pays qui se rencontrent en un seul point, comme quatre carrés à un coin, ne sont pas voisins. Le théorème des quatre couleurs affirme que tout graphe planaire peut être colorié avec quatre couleurs. Activez Afficher les voisins pour voir le graphe de la carte actuelle.

Trois façons de colorier

La coloration gloutonne prend les pays un par un, ceux qui ont le plus de voisins d'abord, et donne à chacun la première couleur que ses voisins n'ont pas utilisée. Elle est rapide mais myope, et sur certaines cartes elle doit recourir à une cinquième, voire une sixième couleur. DSATUR, inventé par Daniel Brélaz en 1979, choisit toujours ensuite le pays dont les voisins affichent déjà le plus de couleurs différentes, ce qui évite généralement ce piège. Le retour sur trace essaie les couleurs à tour de rôle et, lorsqu'il ne reste plus aucune couleur pour un pays, annule ses choix les plus récents et réessaie ; il trouve toujours une coloration avec quatre couleurs, parfois après de nombreux retours en arrière.

Questions fréquemment posées

Pourquoi quatre couleurs suffisent-elles toujours ?

Personne n'en a trouvé de raison courte. La démonstration de Kenneth Appel et Wolfgang Haken en 1976 a montré que toute carte doit contenir l'une de 1 936 petites configurations, et que chacune d'elles peut être retirée puis la coloration rétablie ensuite ; les vérifier toutes a demandé plus de mille heures de calcul informatique. Une démonstration informatique plus simple de Neil Robertson, Daniel Sanders, Paul Seymour et Robin Thomas en 1996 n'a besoin que de 633 configurations, et en 2005 Georges Gonthier a entièrement vérifié une démonstration avec l'assistant de preuve Coq.

Certaines cartes ont-elles besoin des quatre couleurs ?

Oui. Quatre pays qui touchent chacun les trois autres, comme un pays entouré d'un anneau de trois autres, en nécessitent quatre. Beaucoup de cartes, cependant, se contentent de trois, et Minimum de couleurs le détermine pour la carte à l'écran. Décider en général si une carte peut être coloriée avec trois couleurs est un problème difficile, NP-complet, alors même que quatre couleurs suffisent toujours.

Pourquoi la méthode gloutonne utilise-t-elle parfois cinq couleurs ?

Elle colorie chaque pays une seule fois et ne revient jamais sur sa décision. Un choix précoce peut laisser un pays ultérieur entouré des quatre couleurs, et la seule issue est alors une cinquième. Le retour sur trace, lui, reviendrait en arrière et modifierait les choix antérieurs.

Le théorème est-il vrai sur d'autres surfaces ?

Sur une sphère, oui : c'est la même chose que le plan. Sur un tore, la surface d'un beignet, certaines cartes nécessitent sept couleurs, et sept suffisent toujours, comme l'a montré Percy Heawood. Si des pays peuvent se composer de plusieurs morceaux séparés, comme une nation avec des colonies, quatre couleurs ne suffisent plus.

Des données sont-elles envoyées à un serveur ?

Non. La carte, les méthodes de coloration et la vérification s'exécutent dans votre navigateur. Vos réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur