L'histoire de la coloration de graphe débute en 1852, lorsqu'un jeune diplômé, Francis Guthrie, tente de colorier la carte des comtés d'Angleterre. Il remarque qu'il n'a besoin que de quatre couleurs au maximum pour s'assurer que deux comtés frontaliers n'aient jamais la même couleur. Il demande à son frère, étudiant d'Augustus De Morgan, s'il existe une preuve mathématique que 4 couleurs suffisent pour n'importe quelle carte plane.
C'est la naissance du célèbre Théorème des quatre couleurs. En 1879, Alfred Kempe publie une preuve qui sera acceptée pendant 11 ans, avant que Percy Heawood ne découvre une faille irréparable dans son raisonnement en 1890.
Il faudra attendre 1976 pour que Kenneth Appel et Wolfgang Haken en fournissent la démonstration finale. Cette preuve a bouleversé la communauté mathématique car elle est la toute première démonstration majeure nécessitant l'assistance d'un ordinateur (pour analyser 1482 configurations complexes inaccessibles à la main).
En théorie des graphes, on généralise ce problème : peut-on colorier les sommets d'un graphe avec $k$ couleurs sans que deux sommets adjacents partagent la même couleur ? Si $k=2$ est facile (graphes bipartis), le cas $k=3$ est un problème majeur de l'optimisation combinatoire.
Pour n sommets, le nombre de colorations possibles avec 3 couleurs est de $3^n$.
| n sommets | Colorations possibles | Temps (1ns/coloration) |
|---|---|---|
| 15 | 14 348 907 | < 15 ms |
| 25 | 8,47 × 1011 | 14 minutes |
| 40 | 1,21 × 1019 | 385 ans |
| 60 | 4,23 × 1028 | 1,3 milliard d'années |
La force brute naïve est $\mathcal{O}(3^n)$ — inexploitable à grande échelle.
NP : Si la réponse est OUI, on peut le vérifier rapidement.
Ce vérificateur s'exécute en temps $\mathcal{O}(|E|)$. La 3-Coloration appartient donc à NP. Elle fait d'ailleurs partie des 21 problèmes NP-complets originaux de Karp (1972).
Cliquez sur les sommets pour modifier leur couleur (Gris $\to$ Rouge $\to$ Vert $\to$ Bleu $\to$ Gris). L'interface agit comme le vérificateur : si vous reliez deux sommets de la même couleur, l'arête s'illuminera en rouge signalant un conflit.
L'algorithme de retour sur trace (backtracking) parcourt l'arbre des combinaisons possibles.
S'il trouve un certificat valide, il l'affiche.
S'il échoue, rien ne s'affiche, cela constitue une preuve mathématique exhaustive (puisqu'il a testé toutes les branches valides) qu'aucune solution n'existe pour 3 couleurs.