Le théorème des quatre couleurs

Sujet proposé par Georges Gonthier

`Georges.Gonthier@inria.fr`

Le théorème de quatre couleurs est l'un des résultats les plus célèbres de mathématiques combinatoires. Malgré un énoncé simple, le théorème est resté une conjecture pendant plus d'un siècle, durant lequel il fut abordé par les plus grands mathématiciens, parfois avec des résultats faux. En outre, sa résolution en 1976 comportait un long calcul sur ordinateur, et était donc de ce fait très controversée, la plupart des mathématiciens n'étant pas capables de vérifier l'exactitude des programmes utilisés. Dans ce projet informatique, on vous propose de revérifier cette preuve avec des moyens modernes, en partant d'une preuve simplifiée plus récente.

Un peu d'histoire

En 1852 Francis Guthrie, cartographe anglais, remarque qu'il lui suffit de quatre couleurs pour colorer la carte (pourtant fort complexe) des cantons d'Angleterre, sans donner la même couleur à deux cantons adjacents (ayant une frontière commune). Il demande donc à son frère Frederick, mathématicien, si cette propriété ne serait pas vraie en général pour toute carte plane; celui-ci communique la conjecture à De Morgan, et en 1878 Cayley la publie.

Presqu'aussitôt, en 1879, Kempe trouve une prmière ``preuve'' de la conjecture, mais onze ans plus tard Heawood y trouvera une faille majeure; il parviendra toutefois à en sauver un théorème des cinq couleurs. Une seconde ``preuve'' par Tait en 1880 sera de même réfutée par Petersen en 1891.

En 1913, le père de l'algèbre moderne, G. D. Birkhoff, formule la notion de configuration réductible et démontre la conjecture pour toutes les cartes comportant moins de 26 régions à colorier. Cette borne est améliorée au cours du XX^e siècle; en 1969 Heesch trouve des conditions ``presque'' nécessaires et suffisantes pour qu'une configuration soit réductible, et une méthode générale pour trouver un ensemble inévitable de configurations.

Finalement, en 1976, Appel et Haken réalisent le programme de Heesch, et montrent, dizaines de milliers de figures à l'appui, que toute carte non 4-coloriable doit contenir l'une de 1478 configurations, et, avec 1200 heures de calcul, que chacune de ces configurations sont réductibles.

Enfin, en 1995, Robertson, Sanders, Seymour et Thomas mettent à profit la formidable accélération des ordinateurs pour trouver une réalisation nettement plus simple du programme de Heesch, avec seulement 633 configurations; de plus ils automatisent également la preuve d'inévitabilité. L'objet de ce projet est de vérifier la réductibilité de ces 633 configurations.

1 L'argument de Kempe

Assez ironiquement, le premier jet de Kempe contient toutes les idées maîtresses de la vraie preuve, même s'il aura fallu près d'un siècle pour le mettre au propre. Il est donc utile de dérouler l'argument faux de Kempe, à la fois pour comprendre la difficulté du problème et parce qu'il sert de trame à l'argument juste.

1.1 Des cartes aux graphes

Pour commencer, on note que tout problème de coloriage de carte est trivialement équivalent à un problème de coloriage de graphe: il suffit de choisir une capitale dans chaque région, et de relier par une route les capitales de chaque paire de régions ayant un segment (pas un point) de frontière en commun. Ainsi, colorier la carte équivaut à colorier les capitales en donnant des couleurs différentes à deux capitales directement reliées par une route.

Parce qu'elle permet de faire des figures plus claires, la formulation en graphes est celle qui est généralement utilisée par les mathématiciens qui ont abordé le problème, et c'est celle que nous utiliserons dans la suite de cette section.

La transformation carte-graphe est en fait une dualité. En effet les ``routes'' d'un graphe planaire délimitent aussi des régions du plan, appelées faces du graphe, et le graphe de la carte des faces n'est autre que... le graphe des fontières de la carte d'origine !

On remarque que l'on peut se limiter au coloriage des graphes connexes triangulés, dont chaque face est délimitée par exactement trois routes (y compris la face infinie qui entoure le graphe tout entier). En effet, on peut obtenir un graphe triangulé G_T à partir d'un graphe G quelconque en supprimant les routes parallèles, et en ajoutant n-3 routes diagonales en travers de chaque région n-gonale (n³ 4); alors, tout 4-coloriage de G_T sera aussi un 4-coloriage de G.

1.2 La formule d'Euler

Le nombre f de faces d'un graphe planaire connexe G peut en fait se calculer à partir du nombre n de sommets (capitales) et m d'arêtes (routes) de G, au moyen de la formule d'Euler:

n - m + f = 2

qui se démontre aisément par récurrence sur m.

Kempe utilisa cette formule de la manière suivante : chaque arête ayant deux extrémités, le degré (nombre d'arêtes incidentes) moyen d'un sommet est d = 2m/n. Dans un graphe triangulé, chaque arête a deux ``côtés'', et chaque face est entouré de trois de ces côtés, donc 3f=2m, et donc

d = 6 -

< 6

Il existe donc un sommet x de degré d au plus 5 dans G. L'idée de Kempe est de supposer par récurrence que G-x est 4-coloriable, et de tenter d'étendre un 4-coloriage de G-x en un coloriage de G.

1.3 Les chaînes de Kempe

Si le coloriage dans G-x des voisins de x n'utilise pas les quatre couleurs, il suffit d'attribuer à x l'une des couleurs inutilisées; c'est forcément le cas si d=3. Sinon, il est nécessaire de modifier le coloriage de G-x; Kempe étudia les conditions dans lesquelles ceci pouvait être fait.

Considérons un graphe (planaire) H 4-coloré en bleu, jaune, rouge, blanc. Si y est un sommet coloré en bleu, on appelle chaîne de Kempe bleu-jaune de y à z un chemin dans H de y à z qui alterne les couleurs bleu, jaune, bleu, jaune, ..., et composante bleu-jaune de y l'ensemble H' de tous les de tous les sommets z de H tels qu'il y ait une chaîne de Kempe bleu-jaune de y à z.

L'intérêt de ces définitions est le suivant: on peut intervertir les couleurs bleu et jaune dans une composante bleu-jaune quelconque de H, pour obtenir un nouveau coloriage de H. Kempe eut l'intuition correcte que cette transformation (que l'on appellera inversion) était suffisante pour démontrer le théorème des quatre couleurs.

En effet, la planarité de G implique qu'on peut toujours trouver une transformation qui change de façon non-triviale les couleurs des voisins d'un sommet x. Par exemple, supposons que x a quatre voisins x₀, x₁, x₂, x₃, qui sont respectivement bleu, rouge, jaune et blanc dans un 4-coloriage de H=G-x. Considérons la composante bleu-jaune de x₀; elle ne contenir ni x₁ ni x₃. Si elle ne contient pas non plus x₂, alors en l'inversant on met x₀ en jaune, sans toucher à x₁, x₂, x₃, donc on libère le bleu pour x. Sinon, il y a une chaîne de Kempe bleu-jaune de x₀ à x₂. S'il y avait aussi une chaîne blanc-rouge de x₃ à x₁, elle couperait celle de x₀ à x₂ puisque H est planaire, ce qui est impossible. Donc inversant la composante blanc-rouge de x₃, on met x₃ en rouge sans changer x₀, x₁, x₂, ce qui libère le blanc pour x.

1.4 L'argument et sa réfutation

L'argument de Kempe se résume donc ainsi :

Un graphe à quatre sommets est trivialement 4-coloriable.
Un graphe G triangulaire plus grand contient forcément un sommet x de degré d £ 5.
On peut supposer sinon que H=G-x est 4-colorié par récurrence
Si le coloriage des d voisins n'utilise pas une couleur, on l'attribue à x.
Sinon, on étudie les chaînes de Kempe dans H, et on trouve des inversions qui dégagent une couleur pour x.

Pour tomber dans ce dernier cas, il faut avoir d=4 ou 5. On a vu le cas d=4 ci-dessus. Pour d=5, Kempe proposa le raisonnement suivant:

Soient x₀, x₁, x₂, x₃, x₄ les voisins de x. Modulo symétrie, on peut supposer que x₁ et x₃ sont blancs, et que x₀, x₂, x₄ sont respectivement bleu, jaune, rouge. S'il n'y a pas de chaîne jaune-bleu de x₂ à x₀, alors on inverse la composante jaune-bleu de x₂, ce qui libère le bleu pour x. On procède de même s'il n'y a pas de chaîne jaune-rouge de x₂ à x₄. Sinon, x₁ et x₃ sont seuls dans leurs composantes blanc-rouge et blanc-bleu, qu'il suffit d'inverser pour libérer le blanc pour x.

L'erreur ici est que les chaînes x₂--x₀ et x₂--x₄ peuvent se croiser, donc que les composantes de x₁ et x₃ ne sont pas forcément disjointes, et donc pas forcément inversibles simultanément. En fait, Heawood exhiba un graphe à 25 sommets, pour lequel aucune suite d'inversions de composantes des voisins de x ne libère de couleur pour x.

2 Les configurations réductibles

La vraie preuve du théorème des quatre couleurs suit exactement le plan de l'argument (faux) de Kempe, avec une différence importante: on autorise une forme arbitraire pour le ``morceau'' de G qu'on enlève pour la récurrence, au lieu de se limiter à un unique sommet x, de degré 3, 4, ou 5. Un tel morceau de graphe s'appellera une configuration.

Le plan de preuve consiste donc à trouver un ensemble fini K de configurations qui soit inévitable, c'est-à-dire tel que tout graphe non 4-coloriable contienne une copie conforme de l'une des KÎ K; l'inévitabilité se démontre encore avec la formule d'Euler, en répartissant finement (en 1/10!) les 12 degrés manquants, au moyen de règles de ``décharge'' (Appel et Haken en avaient 300, Robertson, Sanders, Seymour et Thomas seulement 32).

Ensuite, il suffit de montrer que chaque KÎ K est réductible, c'est-à-dire qu'on peut toujours déduire le coloriage d'un graphe G contenant une copie conforme de K du coloriage d'un graphe G' plus petit.

L'objet de ce projet est de vérifier cette seconde partie de la preuve, avec les 633 configurations de Robertson, Sanders, Seymour et Thomas.

2.1 Coloriage de frontières

Les calculs de réductibilité sont plus faciles à expliquer et à réaliser en travaillant directement sur les cartes, plutot que sur leurs graphes duaux. Les cartes duales des graphes triangulés sont dites cubiques: il y a exactement trois segments de frontière qui se rencontrent à chaque jonction de frontières, et la frontière de chaque région est constituée d'au moins deux segments (on exclut donc les enclaves).

Il est également plus simple de colorier les segments de frontières plutôt que les régions. Un tricoloriage des segments d'une carte associe à chaque segment l'une de trois couleurs, de façon à ce que les trois couleurs apparaissent à chaque jonction. On a:

Théorème 1 [Tait 1880] Les régions d'une carte cubique sont 4-coloriables si et seulement si ses segments de frontières sont tricoloriables.

En effet, si l'on a 4-colorié une carte cubique avec les trois couleurs primaires (rouge, jaune, bleu), et un blanc ``magique'', on peut en colorier chaque segment avec le mélange des couleurs des régions qu'il sépare. Si le mélange d'une primaire avec le blanc magique donne sa complémentaire (p.ex., rouge+magique=vert), que les mélanges primaire-primaire suivent les règles usuelles (p.ex., jaune+bleu=vert), on constate que l'on obtient bien un tricoloriage de la carte avec les les trois couleurs secondaires (vert, orange, violet). Réciproquement, dès que l'on fixe la couleur de la région infinie, un tel tricoloriage des segments induit de proche en proche un unique 4-coloriage des régions.

Les inversions de Kempe sont particulièrement simples dans un tricoloriage. Par exemple tous les segments de frontière à l'intérieur d'une composante bleu-jaune ou rouge-blanc sont verts, et donc que les segments qui délimitent cette composante sont alternativement oranges et violets. Inverser la composante échange alors tout simplement l'orange et le violet sur cette frontière.

2.2 Les configurations

Puisque nous travaillons avec des cartes, les configurations seront des fragments de carte. Formellement un fragment de carte H est l'intersection d'une carte C avec un domaine D, qui est une région connexe dont la frontière ne passe par aucune jonction de C. Un fragment comporte donc des régions partielles qui sont en partie délimitées par la frontière du domaine; de même il peut comporter des demi-segments qui relient une jonction à un point de la frontière du domaine, et/ou des cordes qui relient directement deux points de la frontière du domaine. Les points de la frontière de D qui sont les extrémités de cordes ou de demi-segments forment l'interface H de H. Le nombre de points de H s'appelle le périmètre de H.

Une configuration K est tout simplement un fragment de carte cubique sans corde, tel qu'il y ait au plus un demi-segment à chaque jonction. Le noyau de K est la carte de ses régions entières. Robertson, Sanders, Seymour et Thomas imposent quelques propriétés supplémentaires à leurs configurations, pour pouvoir les représenter par le graphe dual de leur noyau; ces propriétés ne sont pas nécessaires pour effectuer les vérifications de réductibilité.

On dit qu'une carte C contient une copie conforme d'une configuration K s'il existe un domaine D tel que le fragment CÇ D soit homéomorphe à K. Dans la suite on identifiera simplement CÇ D et K. Ce découpage définit aussi un fragment complémentaire C-K = C Ç (R² - D), qui a la même interface que CÇ D=K.

Les définitions du 4-coloriage et du tricoloriage s'étendent aux fragments de graphes cubiques, en coloriant aussi les régions partielles, demi-segments ou cordes. Un tricoloriage g d'un fragment H induit un 3-coloriage g de son interface H, attribuant à chaque point d'interface la couleur du semi-segment ou de la corde dont il est l'extrémité. g est pair: la parité du nombre de sommets colorés dans chacune des trois couleurs (vert, orange, violet) par g doit être égale à la parité du périmètre de H.

2.3 Les chromogrammes

Etant donné une configuration K, et une carte C contenant K, on obtient une carte C' plus petite en remplaçant K par un fragment K' de même interface mais plus petit (par exemple, en effaçant un segment de K); la restriction d à C'-K' = C-K d'un tricoloriage de C' induit un tricoloriage d de C-K. Clairement, K sera réductible si pour tout coloriage pair d il existe un tricoloriage g de K qui induit g = d sur K=C-K: il suffit alors de recoller g et d pour obtenir un tricoloriage de C.

Malheureusement, ceci n'est vrai que pour les configurations de périmètre 3. Il est donc nécessaire de modifier d à l'aide d'une ou plusieurs inversions de Kempe, et donc de systématiser le raisonnement que nous avons fait pour un sommet de degré 4 en 1.3. On évite l'erreur de Kempe en n'inversant simultanément que des composantes par nature disjointes, par exemple bleu-jaune et/ou rouge-blanc; on parlera d'inversion verte dans ce cas. L'ensemble l'ensemble des coloriages que l'on peut obtenir par inversion verte (ou orange ou violette), qui dépend la topologie de C-D et de d, peut se résumer de manière remarquablement simple par un chromogramme.

Un chromogramme X est simplement un fragment de carte qui ne comporte que des cordes, lesquelles sont coloriées avec deux couleurs, ``paire'' et ``impaire''. Si aÎ{vert,orange,violet} est une couleur secondaire, on dira que d et X sont a-compatibles si et seulement si

X est l'ensemble des points de K que d ne colorie pas en a,
si c une corde de X, d'extrémités x,y, alors d(x) = d(y) si et seulement si c est impaire.

Ces définitions sont motivées par le résultat suivant :

Théorème 2 Soit H un fragment de carte cubique, d un tricoloriage de H, a une couleur secondaire. Il existe un un chromogramme X tel que tout 3-coloriage g de H est a-compatible avec X si et seulement si il peut être induit par un coloriage d' obtenu de d par a-inversion.

Prenons par exemple a=vert. Soit H' le fragment obtenu en supprimant dans H tous les segments et demi-segments verts. On obtient X en effaçant de H' de toutes les jonctions binaires et régions isolées. Chaque corde c de X est donc la concaténation de k segments, demi-segments, ou cordes de H'; la ``couleur'' de c est la parité de n. Comme H est cubique et qu'on supprime un segment vert de chaque jonction, H' est une union disjointe de lignes pointillées orange-violet, et donc X est bien un chromogramme compatible avec d. X ne dépend que des segments verts de d, et est donc invariant par inversion verte.

Réciproquement, un g vert-compatible avec X colorie les mêmes points en vert que d. Si c est une corde de X d'extrémités x,y, alors g(x) = d(x) ssi g(y) = d(y). Soit X' le fragment obtenu en supprimant de X tous les c tels que g(x) = d(x) et g(y) = d(y). On obtient d' en faisant une inversion verte dans une région partielle sur deux de X'.

2.4 La réductibilité

Armés de cette analyse, nous pouvons maintenant énoncer des conditions de réductibilité suffisantes pour démontrer le théorème des quatre couleurs.

Soit K une configuration; l'ensemble, noté K^*, des coloriages compatibles avec K est le plus petit ensemble de 3-coloriages de K tel que

si g est un tricoloriage de K, alors gÎ K^*,
si il existe une couleur secondaire a, telle que pour tout chromodendron X a-compatible avec d, il existe un d'Î K^* a-compatible avec X, alors dÎ K^*.

K^* contient donc les coloriages qu'il est toujours possible de ramener à un coloriage de K par une suite d'inversions de Kempe, et ce quelque soit la topologie de C contenant K.

Si K^* contient tous les 3-coloriages possibles de K, alors on dit que K est D-réductible, car on peut alors adapter tout tricoloriage G-K à un coloriage de K avec des inversions, et recoller.

La plupart des configurations réductibles intéressantes ne sont hélas pas D-réductibles; heureusement, on peut s'en tirer en forçant le choix du K' remplaçant K dans la récurrence. On se donne contrat k, qui est un petit ensemble de 1 à 4 segments entiers de K tel que¹ il n'y ait pas plus d'un segment de k à chaque jonction de K. C sera dit C-réductible si tout tricoloriage de K' induit un coloriage de K^*. En effet un tricoloriage de la carte C' obtenue en supprimant les segments de k dans C est le recollage d'un tricoloriage d de C-K et d'un tricoloriage e de K', donc d=eÎ K^*, et on peut trouver un d' et un g comme pour la D-réductibilité.

3 Travail demandé

Vous devez donc faire un programme qui vérifie la partie réductibilité du théorème des quatre couleurs:

Les 633 configurations vous seront fournies dans un fichier au format simple, que votre programme devra pouvoir lire.
La vérification de réductibilité demande de programmer trois algorithmes pour effectuer les calculs décrits dans 2.4: le calcul de l'ensemble des g pour g tricoloriage de K, le même pour K' s'il y a un contrat, et enfin le calcul de K^* ou de son complémentaire.
Il faut faire attention au choix des structures de données et algorithmes que vous utiliserez pour ces algorithmes, surtout pour le calcul de K^*. En particulier, l'utilisation de la symétrie des couleurs permet de diviser la taille des ensembles par 6! Avec de bons algorithmes, un programme en C bien écrit peut traiter chaque configuration en moins d'une minute.
Le fichier contiendra les coordonnées d'une ``jolie'' disposition des configurations. Vous êtes encouragés à les utiliser pour afficher certains calculs intermédiares de votre programme. Pensez aussi à tester votre programme sur des configurations non C-réductibles (l'examinateur le fera).

4 Extensions

Deux grands types d'extensions sont envisageables :

On peut déduire de la preuve du théorème un algorithme de 4-coloriage de carte planaire en temps quadratique. Vous pouvez le construire (en partie) à partir du test de réductibilité.
Vous pouvez compléter votre travail en réalisant l'autre moitié de la preuve: l'inévitabilité.

References

[RSST97]: N. Robertson, D. Sanders, P. Seymour, R. Thomas. The Four-Colour Theorem. Journal of Combinatorial Theory, Series B, 70 (1997), pp. 2--44.
[AH89]: K. Appel, W. Haken. Every planar map is four colourable. Contemporary Mathematics 98 (1989).
[SK77]: T. Saaty, P. Kainen. The Four-Color Problem, assaults and conquest. McGraw-Hill (1977).

1: Si |k|=4 on exige aussi qu'une région t de K soit adjacente à au moins trois régions bordées par un segment de k, et que si t est un pentagone dont quatre des sommets sont des extrémités de segments de k, alors un de ses côtés est dans k. Cette condition curieuse permet de s'assurer que C-KÈ K' est bien une carte cubique (sans boucle), dès lors que C n'est pas la réunion de deux configurations disjointes de périmètre inférieur ou égal à 5, et différentes du pentagone de Kempe (Birkhoff a montré que ces configurations sont toutes réductibles).

This document was translated from L^AT_EX by H^EV^EA.