Collection cartographique

4 avril 2022

 
Titre : Les États-Unis en quatre couleurs
Mots-clés : #Algorithmes #Coloriage #Contraintes
Auteur : Philippe Rivière
Date : Avril 2021

Un théorème de mathématiques démontre que quatre couleurs suffisent à colorier n’importe quelle carte (sans que deux régions contiguës ne partagent la même couleur, bien entendu).

PNG - 64.4 kio

Dans la pratique, le coloriage peut se faire à la main en s’armant de patience, ou bien par des techniques algorithmiques dites de « programmation logique » ou de « programmation par contraintes ». Pour calculer cette carte, nous avons utilisé le résolveur Clingo, développé par l’université de Potsdam et compilé par Dominik Moritz. Notez que certaines îles restent en gris : puisqu’elles ne touchent aucune autre région, on peut leur affecter n’importe quelle couleur.

PNG - 267.1 kio

Toutes les versions de cet article : [English] [français]