Théorème des quatre couleurs -Four color theorem

Exemple de carte quadrichromie
Une carte en quatre couleurs des États des États-Unis (sans tenir compte des lacs et des océans)

En mathématiques , le théorème des quatre couleurs , ou le théorème de la carte des quatre couleurs , stipule qu'il ne faut pas plus de quatre couleurs pour colorer les régions d'une carte afin que deux régions adjacentes n'aient pas la même couleur. Adjacent signifie que deux régions partagent un segment de courbe frontière commun, pas simplement un coin où trois régions ou plus se rencontrent. C'était le premier théorème majeur à être prouvé à l'aide d'un ordinateur . Initialement, cette preuve n'était pas acceptée par tous les mathématiciens car la preuve assistée par ordinateur était infaisable pour un humain à vérifier à la main . La preuve a été largement acceptée depuis lors, bien que certains sceptiques subsistent.

Le théorème des quatre couleurs a été prouvé en 1976 par Kenneth Appel et Wolfgang Haken après de nombreuses fausses preuves et contre-exemples (contrairement au théorème des cinq couleurs , prouvé dans les années 1800, qui stipule que cinq couleurs suffisent pour colorer une carte). Pour dissiper tout doute restant sur la preuve Appel-Haken, une preuve plus simple utilisant les mêmes idées et reposant toujours sur des ordinateurs a été publiée en 1997 par Robertson, Sanders, Seymour et Thomas. En 2005, le théorème a également été prouvé par Georges Gonthier avec un logiciel de démonstration de théorème à usage général .

Formulation précise du théorème

En termes de théorie des graphes, le théorème stipule que pour un graphe planaire sans boucle , son nombre chromatique est .

L'énoncé intuitif du théorème des quatre couleurs - "étant donné toute séparation d'un plan en régions contiguës, les régions peuvent être colorées en utilisant au plus quatre couleurs afin qu'aucune région adjacente n'ait la même couleur" - doit être interprété de manière appropriée pour être correct .

Premièrement, les régions sont adjacentes si elles partagent un segment frontière ; deux régions qui ne partagent que des points frontières isolés ne sont pas considérées comme adjacentes. (Sinon, une carte sous la forme d'un graphique à secteurs rendrait un nombre arbitrairement grand de régions "adjacentes" les unes aux autres dans un coin commun, et nécessiterait en conséquence un nombre arbitrairement grand de couleurs.) Deuxièmement, des régions bizarres, telles que celles à aire finie mais à périmètre infiniment long, ne sont pas autorisées ; les cartes avec de telles régions peuvent nécessiter plus de quatre couleurs. (Pour plus de sécurité, nous pouvons nous limiter aux régions dont les frontières sont constituées d'un nombre fini de segments de droite. Il est permis qu'une région ait des enclaves , c'est-à-dire qu'elle entoure entièrement une ou plusieurs autres régions.) Notez que la notion de "région contiguë" (techniquement : sous-ensemble ouvert connecté de l'avion) ​​n'est pas le même que celui d'un « pays » sur des cartes régulières, car les pays n'ont pas besoin d'être contigus (ils peuvent avoir des enclaves , par exemple, la province de Cabinda faisant partie de l'Angola , le Nakhitchevan faisant partie de l'Azerbaïdjan , Kaliningrad faisant partie de la Russie, la France avec ses territoires d'outre-mer et l'Alaska faisant partie des États-Unis ne sont pas contigus). Si nous exigeons que tout le territoire d'un pays reçoive la même couleur, alors quatre couleurs ne suffisent pas toujours. Par exemple, considérons une carte simplifiée :

Exemple d'insuffisance 4CT.svg

Sur cette carte, les deux régions étiquetées A appartiennent au même pays. Si nous voulions que ces régions reçoivent la même couleur, alors cinq couleurs seraient nécessaires, puisque les deux régions A ensemble sont adjacentes à quatre autres régions, dont chacune est adjacente à toutes les autres. Forcer deux régions distinctes à avoir la même couleur peut être modélisé en ajoutant une "poignée" les joignant à l'extérieur du plan.

Explication de l'insuffisance 4CT.svg

Une telle construction rend le problème équivalent à la coloration d'une carte sur un tore (une surface de genre 1), ce qui nécessite jusqu'à 7 couleurs pour une carte arbitraire. Une construction similaire s'applique également si une seule couleur est utilisée pour plusieurs zones disjointes, comme pour les plans d'eau sur de vraies cartes, ou s'il y a plus de pays avec des territoires disjoints. Dans de tels cas, plus de couleurs peuvent être nécessaires avec un genre croissant d'une surface résultante. (Voir la section Généralisations ci-dessous.)

Une carte avec quatre régions et le graphe planaire correspondant avec quatre sommets.

Une déclaration plus simple du théorème utilise la théorie des graphes . L'ensemble des régions d'une carte peut être représenté de manière plus abstraite comme un graphe non orienté qui a un sommet pour chaque région et une arête pour chaque paire de régions qui partagent un segment frontière. Ce graphe est planaire : il peut être dessiné dans le plan sans croisements en plaçant chaque sommet à un emplacement choisi arbitrairement dans la région à laquelle il correspond, et en dessinant les arêtes comme des courbes sans croisements qui partent d'un sommet d'une région, à travers une région partagée. segment limite, au sommet d'une région adjacente. Inversement, tout graphe planaire peut être formé à partir d'une carte de cette manière. Dans la terminologie de la théorie des graphes, le théorème des quatre couleurs stipule que les sommets de chaque graphe planaire peuvent être colorés avec au plus quatre couleurs afin qu'aucun sommet adjacent ne reçoive la même couleur, ou pour faire court :

Chaque graphe planaire est quadricolorable .

Histoire

Premières tentatives de preuve

Lettre de De Morgan à Hamilton , 23 octobre 1852

Pour autant que l'on sache, la conjecture a été proposée pour la première fois le 23 octobre 1852, lorsque Francis Guthrie , tout en essayant de colorer la carte des comtés d'Angleterre, a remarqué que seules quatre couleurs différentes étaient nécessaires. À l'époque, le frère de Guthrie, Frederick , était étudiant d' Augustus De Morgan (l'ancien conseiller de Francis) à l' University College de Londres . Francis s'est renseigné auprès de Frederick à ce sujet, qui l'a ensuite apporté à De Morgan (Francis Guthrie a obtenu son diplôme plus tard en 1852, et est devenu plus tard professeur de mathématiques en Afrique du Sud). Selon DeMorgan :

"Un de mes étudiants [Guthrie] m'a demandé aujourd'hui de lui donner une raison pour un fait dont je ne savais pas qu'il s'agissait d'un fait - et je ne le sais pas encore. Il dit que si une figure est divisée et que les compartiments sont de couleurs différentes, que les figures avec n'importe quelle partie de la ligne de démarcation commune sont de couleurs différentes - quatre couleurs peuvent être souhaitées mais pas plus - le cas suivant est son cas dans lequel quatre couleurs sont souhaitées. La requête ne peut pas être inventée une nécessité pour cinq ou plus… " ( Wilson 2014 , p.18)

"FG", peut-être l'un des deux Guthries, a publié la question dans The Athenaeum en 1854, et De Morgan a de nouveau posé la question dans le même magazine en 1860. Une autre référence publiée au début par Arthur Cayley  ( 1879 ) attribue à son tour la conjecture à De Morgan.

Il y a eu plusieurs premières tentatives infructueuses pour prouver le théorème. De Morgan pensait que cela découlait d'un simple fait concernant quatre régions, bien qu'il ne croyait pas que ce fait puisse être dérivé de faits plus élémentaires.

Cela se produit de la manière suivante. Nous n'avons jamais besoin de quatre couleurs dans un quartier à moins qu'il n'y ait quatre comtés, dont chacun a des lignes de démarcation communes avec chacun des trois autres. Une telle chose ne peut se produire avec quatre zones à moins qu'une ou plusieurs d'entre elles ne soient englobées par les autres ; et la couleur utilisée pour le comté enclavé est ainsi libérée. Or ce principe, que quatre régions ne peuvent avoir chacune une frontière commune avec les trois autres sans clôture, n'est pas, nous le croyons pleinement, capable de démonstration sur quoi que ce soit de plus évident et de plus élémentaire ; il doit tenir lieu de postulat.

Une preuve proposée a été donnée par Alfred Kempe en 1879, qui a été largement acclamée; une autre a été donnée par Peter Guthrie Tait en 1880. Ce n'est qu'en 1890 que la preuve de Kempe a été montrée incorrecte par Percy Heawood , et en 1891, la preuve de Tait a été montrée incorrecte par Julius Petersen - chaque fausse preuve est restée incontestée pendant 11 ans.

En 1890, en plus d'exposer le défaut de la preuve de Kempe, Heawood prouva le théorème des cinq couleurs et généralisa la conjecture des quatre couleurs à des surfaces de genre arbitraire.

Tait, en 1880, a montré que le théorème des quatre couleurs équivaut à l'affirmation selon laquelle un certain type de graphe (appelé snark dans la terminologie moderne) doit être non planaire .

En 1943, Hugo Hadwiger a formulé la conjecture de Hadwiger , une généralisation de grande envergure du problème des quatre couleurs qui reste toujours non résolu.

Preuve par ordinateur

Au cours des années 1960 et 1970, le mathématicien allemand Heinrich Heesch a développé des méthodes d'utilisation des ordinateurs pour rechercher une preuve. Il a notamment été le premier à utiliser la décharge pour prouver le théorème, qui s'est avéré important dans la partie inévitable de la preuve d'Appel-Haken ultérieure. Il a également développé le concept de réductibilité et, avec Ken Durre, a développé un test informatique pour celui-ci. Malheureusement, à ce moment critique, il n'a pas été en mesure de se procurer le temps de supercalculateur nécessaire pour poursuivre son travail.

D'autres reprennent ses méthodes, dont son approche assistée par ordinateur. Alors que d'autres équipes de mathématiciens se précipitaient pour compléter les preuves, Kenneth Appel et Wolfgang Haken de l' Université de l'Illinois ont annoncé, le 21 juin 1976, qu'ils avaient prouvé le théorème. Ils ont été assistés dans certains travaux algorithmiques par John A. Koch .

Si la conjecture à quatre couleurs était fausse, il y aurait au moins une carte avec le plus petit nombre possible de régions nécessitant cinq couleurs. La preuve a montré qu'un tel contre-exemple minimal ne peut exister, grâce à l'utilisation de deux concepts techniques :

  1. Un ensemble inévitable est un ensemble de configurations tel que chaque carte qui satisfait certaines conditions nécessaires pour être une triangulation minimale non coloriable (comme avoir un degré minimum 5) doit avoir au moins une configuration de cet ensemble.
  2. Une configuration réductible est un arrangement de pays qui ne peut se produire dans un contre-exemple minimal. Si une carte contient une configuration réductible, la carte peut être réduite à une carte plus petite. Cette carte plus petite a la condition que si elle peut être colorée avec quatre couleurs, cela s'applique également à la carte d'origine. Cela implique que si la carte d'origine ne peut pas être colorée avec quatre couleurs, la plus petite carte ne le peut pas non plus et donc la carte d'origine n'est pas minimale.

En utilisant des règles mathématiques et des procédures basées sur les propriétés des configurations réductibles, Appel et Haken ont trouvé un ensemble inévitable de configurations réductibles, prouvant ainsi qu'un contre-exemple minimal à la conjecture à quatre couleurs ne pouvait pas exister. Leur preuve a réduit l'infinité des cartes possibles à 1 834 configurations réductibles (réduites plus tard à 1 482) qui ont dû être vérifiées une par une par ordinateur et ont pris plus de mille heures. Cette partie réductibilité du travail a été vérifiée indépendamment avec différents programmes et ordinateurs. Cependant, la partie inévitable de la preuve a été vérifiée dans plus de 400 pages de microfiches , qui ont dû être vérifiées à la main avec l'aide de la fille de Haken, Dorothea Blostein ( Appel & Haken 1989 ).

L'annonce d'Appel et Haken a été largement rapportée par les médias du monde entier, et le département de mathématiques de l' Université de l'Illinois a utilisé un cachet de la poste indiquant "Quatre couleurs suffisent". Dans le même temps, la nature inhabituelle de la preuve - c'était le premier théorème majeur à être prouvé avec une assistance informatique étendue - et la complexité de la partie vérifiable par l'homme ont suscité une controverse considérable ( Wilson 2014 ).

Au début des années 1980, des rumeurs se sont répandues sur une faille dans la preuve Appel-Haken. Ulrich Schmidt à RWTH Aachen avait examiné la preuve d'Appel et Haken pour sa thèse de maîtrise qui a été publiée en 1981 ( Wilson 2014 , 225). Il avait vérifié environ 40% de la partie inévitable et avait trouvé une erreur significative dans la procédure de décharge ( Appel & Haken 1989 ). En 1986, Appel et Haken ont été invités par le rédacteur en chef de Mathematical Intelligencer à écrire un article traitant des rumeurs de failles dans leur preuve. Ils ont répondu que les rumeurs étaient dues à une « interprétation erronée des résultats [de Schmidt] » et ont répondu avec un article détaillé ( Wilson 2014 , 225-226). Leur magnum opus , Every Planar Map is Four-Colorable , un livre revendiquant une preuve complète et détaillée (avec un supplément microfiche de plus de 400 pages), parut en 1989 ; il a expliqué et corrigé l'erreur découverte par Schmidt ainsi que plusieurs autres erreurs trouvées par d'autres ( Appel & Haken 1989 ).

Simplification et vérification

Depuis la démonstration du théorème, une nouvelle approche a conduit à la fois à une preuve plus courte et à un algorithme plus efficace pour les cartes à 4 couleurs. En 1996, Neil Robertson , Daniel P. Sanders , Paul Seymour et Robin Thomas ont créé un algorithme en temps quadratique (ne nécessitant qu'un temps O ( n 2 ), où n est le nombre de sommets), améliorant un algorithme en temps quartique basé sur sur la preuve d'Appel et Haken. La nouvelle preuve, basée sur les mêmes idées, est similaire à celle d'Appel et Haken mais plus efficace car elle réduit la complexité du problème et ne nécessite de vérifier que 633 configurations réductibles. Les parties d'inévitabilité et de réductibilité de cette nouvelle preuve doivent être exécutées par un ordinateur et ne sont pas pratiques à vérifier à la main. En 2001, les mêmes auteurs ont annoncé une preuve alternative, en prouvant la conjecture snark . Cette preuve reste cependant inédite.

En 2005, Benjamin Werner et Georges Gonthier ont formalisé une preuve du théorème à l'intérieur de l' assistant de preuve Coq . Cela a supprimé la nécessité de faire confiance aux divers programmes informatiques utilisés pour vérifier des cas particuliers; il suffit de faire confiance au noyau Coq.

Résumé des idées de preuve

La discussion suivante est un résumé basé sur l'introduction de Every Planar Map is Four Colorable ( Appel & Haken 1989 ). Bien que défectueuse, la prétendue preuve originale de Kempe du théorème des quatre couleurs a fourni certains des outils de base utilisés plus tard pour le prouver. L'explication ici est reformulée en termes de la formulation de la théorie des graphes moderne ci-dessus.

L'argument de Kempe est le suivant. Premièrement, si les régions planes séparées par le graphe ne sont pas triangulées , c'est-à-dire n'ont pas exactement trois arêtes dans leurs frontières, nous pouvons ajouter des arêtes sans introduire de nouveaux sommets afin de rendre chaque région triangulaire, y compris la région extérieure non bornée. Si ce graphique triangulé peut être colorié en utilisant quatre couleurs ou moins, le graphique d'origine l'est également puisque la même coloration est valable si les arêtes sont supprimées. Il suffit donc de prouver le théorème des quatre couleurs pour les graphes triangulés pour le prouver pour tous les graphes planaires, et sans perte de généralité nous supposons que le graphe est triangulé.

Supposons que v , e et f soient le nombre de sommets, d'arêtes et de régions (faces). Puisque chaque région est triangulaire et que chaque arête est partagée par deux régions, nous avons que 2 e = 3 f . Ceci, associé à la formule d'Euler , v - e + f = 2, peut être utilisé pour montrer que 6 v - 2 e = 12. Maintenant, le degré d'un sommet est le nombre d'arêtes qui le jouxtent. Si v n est le nombre de sommets de degré n et D est le degré maximum de tout sommet,

Mais puisque 12 > 0 et 6 − i ≤ 0 pour tout i ≥ 6, cela démontre qu'il existe au moins un sommet de degré 5 ou moins.

S'il existe un graphique nécessitant 5 couleurs, alors il existe un tel graphique minimal , où la suppression de tout sommet le rend quadricolorable. Appelons ce graphe G . Alors G ne peut pas avoir un sommet de degré 3 ou moins, car si d ( v ) ≤ 3, nous pouvons supprimer v de G , quadricolorer le plus petit graphe, puis rajouter v et lui étendre la quadrichromie en choisissant un couleur différente de ses voisins.

Un graphe contenant une chaîne de Kempe composée d'une alternance de sommets bleus et rouges

Kempe a également montré correctement que G ne peut avoir aucun sommet de degré 4. Comme précédemment, nous supprimons le sommet v et colorons les sommets restants. Si les quatre voisins de v sont de couleurs différentes, disons rouge, vert, bleu et jaune dans le sens des aiguilles d'une montre, nous recherchons un chemin alterné de sommets colorés en rouge et bleu joignant les voisins rouge et bleu. Un tel chemin s'appelle une chaîne de Kempe . Il peut y avoir une chaîne de Kempe joignant les voisins rouges et bleus, et il peut y avoir une chaîne de Kempe joignant les voisins verts et jaunes, mais pas les deux, car ces deux chemins se croiseraient nécessairement et le sommet où ils se croisent ne peut pas être coloré. Supposons que ce sont les voisins rouge et bleu qui ne sont pas enchaînés. Explorez tous les sommets attachés au voisin rouge par des chemins alternés rouge-bleu, puis inversez les couleurs rouge et bleu sur tous ces sommets. Le résultat est toujours une quadrichromie valide, et v peut maintenant être rajouté et coloré en rouge.

Cela ne laisse que le cas où G a un sommet de degré 5 ; mais l'argument de Kempe était défectueux pour ce cas. Heawood a remarqué l'erreur de Kempe et a également observé que si l'on se contentait de prouver que seules cinq couleurs sont nécessaires, on pouvait parcourir l'argument ci-dessus (en changeant seulement que le contre-exemple minimal nécessite 6 couleurs) et utiliser des chaînes de Kempe dans la situation de degré 5 pour prouver le théorème des cinq couleurs .

Dans tous les cas, traiter ce cas de sommet de degré 5 nécessite une notion plus compliquée que de supprimer un sommet. Au contraire, la forme de l'argument est généralisée pour considérer les configurations , qui sont des sous-graphes connectés de G avec le degré de chaque sommet (dans G) spécifié. Par exemple, le cas décrit dans la situation du sommet de degré 4 est la configuration constituée d'un seul sommet étiqueté comme ayant le degré 4 dans G . Comme ci-dessus, il suffit de démontrer que si la configuration est supprimée et que le graphe restant est quadricolore, alors la coloration peut être modifiée de telle sorte que lorsque la configuration est rajoutée, la quadrichromie peut lui être étendue comme Bien. Une configuration pour laquelle cela est possible est appelée configuration réductible . Si au moins une configuration d'un ensemble de configurations doit se produire quelque part dans G, cet ensemble est appelé unavoidable . L'argument ci-dessus a commencé par donner un ensemble inévitable de cinq configurations (un seul sommet de degré 1, un seul sommet de degré 2, ..., un seul sommet de degré 5) puis a montré que les 4 premières sont réductibles; exposer un ensemble inévitable de configurations où chaque configuration de l'ensemble est réductible prouverait le théorème.

Parce que G est triangulaire, le degré de chaque sommet dans une configuration est connu et toutes les arêtes internes à la configuration sont connues, le nombre de sommets dans G adjacents à une configuration donnée est fixe et ils sont joints dans un cycle. Ces sommets forment l' anneau de la configuration ; une configuration avec k sommets dans son anneau est une configuration k -anneau, et la configuration avec son anneau est appelée la configuration en anneau . Comme dans les cas simples ci-dessus, on peut énumérer toutes les quatre couleurs distinctes de l'anneau; toute coloration pouvant être étendue sans modification à une coloration de la configuration est dite d'abord bonne . Par exemple, la configuration à un seul sommet ci-dessus avec 3 voisins ou moins était initialement bonne. En général, le graphe environnant doit être systématiquement recoloré pour que la coloration de l'anneau soit bonne, comme cela a été fait dans le cas ci-dessus où il y avait 4 voisins ; pour une configuration générale avec un anneau plus grand, cela nécessite des techniques plus complexes. En raison du grand nombre de quadrichromies distinctes de l'anneau, il s'agit de la première étape nécessitant une assistance informatique.

Enfin, il reste à identifier un ensemble inévitable de configurations susceptibles d'être réduites par cette procédure. La principale méthode utilisée pour découvrir un tel ensemble est la méthode de décharge . L'idée intuitive sous-jacente à la décharge est de considérer le graphe planaire comme un réseau électrique. Initialement, une "charge électrique" positive et négative est répartie entre les sommets de sorte que le total soit positif.

Rappelons la formule ci-dessus :

Chaque sommet se voit attribuer une charge initiale de 6 degrés ( v ). Puis on « écoule » la charge en redistribuant systématiquement la charge d'un sommet à ses sommets voisins selon un ensemble de règles, la procédure de décharge . Puisque la charge est préservée, certains sommets ont encore une charge positive. Les règles restreignent les possibilités de configurations de sommets chargés positivement, donc l'énumération de toutes ces configurations possibles donne un ensemble inévitable.

Tant qu'un membre de l'ensemble inévitable n'est pas réductible, la procédure de décharge est modifiée pour l'éliminer (tout en introduisant d'autres configurations). La procédure de décharge finale d'Appel et Haken était extrêmement complexe et, avec une description de l'ensemble de configuration inévitable résultant, remplissait un volume de 400 pages, mais les configurations générées pouvaient être vérifiées mécaniquement pour être réductibles. La vérification du volume décrivant l'ensemble de configuration inévitable lui-même a été effectuée par un examen par les pairs sur une période de plusieurs années.

Un détail technique non abordé ici mais nécessaire pour compléter la preuve est la réductibilité par immersion .

Faux démentis

Le théorème des quatre couleurs est connu pour avoir attiré un grand nombre de fausses preuves et de réfutations au cours de sa longue histoire. Au début, le New York Times a refusé, par principe, de rendre compte de la preuve d'Appel-Haken, craignant que la preuve ne se révèle fausse comme les précédentes ( Wilson 2014 ). Certaines preuves alléguées, comme celles de Kempe et de Tait mentionnées ci-dessus, ont fait l'objet d'un examen public pendant plus d'une décennie avant d'être réfutées. Mais beaucoup d'autres, écrits par des amateurs, n'ont jamais été publiés du tout.

Dans la première carte, qui dépasse quatre couleurs, le remplacement des régions rouges par l'une des quatre autres couleurs ne fonctionnerait pas, et l'exemple peut initialement sembler violer le théorème. Cependant, les couleurs peuvent être réarrangées, comme on le voit sur la deuxième carte.

Généralement, les contre-exemples les plus simples, bien qu'invalides, tentent de créer une région qui touche toutes les autres régions. Cela force les régions restantes à être colorées avec seulement trois couleurs. Parce que le théorème des quatre couleurs est vrai, c'est toujours possible ; cependant, comme la personne qui dessine la carte se concentre sur une seule grande région, elle ne remarque pas que les régions restantes peuvent en fait être colorées avec trois couleurs.

Cette astuce peut être généralisée : il existe de nombreuses cartes où si les couleurs de certaines régions sont sélectionnées au préalable, il devient impossible de colorer les régions restantes sans dépasser quatre couleurs. Un vérificateur occasionnel du contre-exemple peut ne pas penser à changer les couleurs de ces régions, de sorte que le contre-exemple apparaîtra comme s'il était valide.

Peut-être qu'un effet sous-jacent à cette idée fausse commune est le fait que la restriction de couleur n'est pas transitive : une région doit seulement être colorée différemment des régions qu'elle touche directement, et non des régions touchant des régions qu'elle touche. Si telle était la restriction, les graphes planaires nécessiteraient un nombre arbitrairement grand de couleurs.

D'autres fausses réfutations violent les hypothèses du théorème, telles que l'utilisation d'une région composée de plusieurs parties déconnectées ou l'interdiction de régions de la même couleur de se toucher en un point.

Tricolore

Preuve sans mots qu'une carte des États américains a besoin d'au moins quatre couleurs, même en ignorant le quadripoint

Alors que chaque carte planaire peut être colorée avec quatre couleurs, il est NP-complet en complexité de décider si une carte planaire arbitraire peut être colorée avec seulement trois couleurs.

Une carte cubique peut être colorée avec seulement trois couleurs si et seulement si chaque région intérieure a un nombre pair de régions voisines. Dans l'exemple de la carte des États américains, le Missouri enclavé ( MO ) a huit voisins (un nombre pair) : il doit être de couleur différente de tous, mais les voisins peuvent alterner les couleurs, ainsi cette partie de la carte n'a besoin que de trois couleurs. Cependant, le Nevada enclavé ( NV ) a cinq voisins (un nombre impair) : l'un des voisins doit être de couleur différente de lui et de tous les autres, il faut donc quatre couleurs ici.

Généralisations

Graphiques infinis

En joignant les flèches simples entre elles et les flèches doubles entre elles, on obtient un tore à sept régions se touchant ; donc sept couleurs sont nécessaires.
Cette construction montre le tore divisé en un maximum de sept régions, dont chacune touche l'autre.

Le théorème des quatre couleurs s'applique non seulement aux graphes planaires finis, mais aussi aux graphes infinis qui peuvent être dessinés sans croisements dans le plan, et encore plus généralement aux graphes infinis (éventuellement avec un nombre indénombrable de sommets) pour lesquels tout sous-graphe fini est planaire . Pour prouver cela, on peut combiner une preuve du théorème pour les graphes planaires finis avec le théorème de De Bruijn – Erdős indiquant que, si chaque sous-graphe fini d'un graphe infini est k -colorable, alors le graphe entier est aussi k -colorable Nash- William (1967) . Cela peut également être vu comme une conséquence immédiate du théorème de compacité de Kurt Gödel pour la logique du premier ordre , simplement en exprimant la colorabilité d'un graphe infini avec un ensemble de formules logiques.

Surfaces supérieures

On peut aussi considérer le problème de coloration sur des surfaces autres que le plan. Le problème sur la sphère ou le cylindre est équivalent à celui sur le plan. Pour les surfaces fermées (orientables ou non orientables) de genre positif , le nombre maximum p de couleurs nécessaires dépend de la caractéristique d'Euler χ de la surface selon la formule

où les parenthèses les plus à l'extérieur indiquent la fonction de plancher .

Alternativement, pour une surface orientable , la formule peut être donnée en termes de genre d'une surface, g :

Cette formule, la conjecture de Heawood , a été proposée par PJ Heawood en 1890 et, après des contributions de plusieurs personnes, prouvée par Gerhard Ringel et JWT Youngs en 1968. La seule exception à la formule est la bouteille de Klein , qui a la caractéristique d'Euler 0 (d'où la formule donne p = 7) mais ne nécessite que 6 couleurs, comme l'a montré Philip Franklin en 1934.

Par exemple, le tore a la caractéristique d'Euler χ = 0 (et le genre g = 1) et donc p = 7, donc pas plus de 7 couleurs sont nécessaires pour colorer une carte sur un tore. Cette borne supérieure de 7 est nette : certains polyèdres toroïdaux comme le polyèdre de Szilassi nécessitent sept couleurs.

Une bande de Möbius nécessite six couleurs ( Tietze 1910 ) tout comme les graphes 1-planaires (graphes dessinés avec au plus un croisement simple par arête) ( Borodin 1984 ). Si les sommets et les faces d'un graphe planaire sont colorés, de telle sorte qu'aucun sommet, face ou paire sommet-face adjacent n'ait la même couleur, alors à nouveau au plus six couleurs sont nécessaires ( Borodin 1984 ) .

Pour les graphes dont les sommets sont représentés comme des paires de points sur deux surfaces distinctes, avec des arêtes dessinées comme des courbes non croisées sur l'une des deux surfaces, le nombre chromatique peut être au moins 9 et au plus 12, mais des bornes plus précises ne sont pas connu; c'est le problème Terre-Lune de Gerhard Ringel .

Régions solides

Il n'y a pas d'extension évidente du résultat de la coloration aux régions solides tridimensionnelles. En utilisant un ensemble de n tiges flexibles, on peut faire en sorte que chaque tige touche une autre tige. L'ensemble nécessiterait alors n couleurs, soit n +1 y compris l'espace vide qui touche aussi chaque tige. Le nombre n peut être considéré comme n'importe quel nombre entier, aussi grand que souhaité. De tels exemples étaient connus de Fredrick Guthrie en 1880 ( Wilson 2014 ). Même pour les cuboïdes parallèles à l'axe (considérés comme adjacents lorsque deux cuboïdes partagent une zone de frontière bidimensionnelle), un nombre illimité de couleurs peut être nécessaire ( Reed & Allwright 2008 ; Magnant & Martin (2011) ).

Relation avec d'autres domaines des mathématiques

Dror Bar-Natan a donné une déclaration concernant les algèbres de Lie et les invariants de Vassiliev qui est équivalente au théorème des quatre couleurs.

Utilisation en dehors des mathématiques

Malgré la motivation de colorier les cartes politiques des pays , le théorème n'est pas d'un intérêt particulier pour les cartographes . Selon un article de l'historien des mathématiques Kenneth May , "les cartes utilisant seulement quatre couleurs sont rares, et celles qui n'en nécessitent généralement que trois. Les livres sur la cartographie et l'histoire de la cartographie ne mentionnent pas la propriété des quatre couleurs" ( Wilson 2014 , 2). Il convient de noter cependant que la plupart des cartes nécessitent quatre couleurs car chaque fois qu'une région est enclavée par un nombre impair de régions, quatre couleurs sont nécessaires. Le théorème ne garantit pas non plus l'exigence cartographique habituelle selon laquelle les régions non contiguës d'un même pays (comme l'exclave de l' Alaska et le reste des États-Unis ) doivent être colorées de manière identique.

Voir également

Remarques

  1. ^ D'après Gonthier (2008) : "Définitions : une carte planaire est un ensemble de sous-ensembles disjoints par paires du plan, appelés régions. Une carte simple est celle dont les régions sont des ensembles ouverts connectés. Deux régions d'une carte sont adjacentes si leurs fermetures respectives ont un point commun qui n'est pas un coin de la carte. Un point est un coin d'une carte si et seulement s'il appartient aux fermetures d'au moins trois régions. Théorème : Les régions de toute carte plane simple peuvent être colorées avec seulement quatre couleurs, de telle manière que deux régions adjacentes aient des couleurs différentes."
  2. ^ Swart (1980) .
  3. ^ Wilson (2014) , 216-222.
  4. ^ Hudson (2003) .
  5. ^ Thomas (1998 , p. 849); Wilson (2014) ).
  6. Il existe un certain folklore mathématique selon lequel Möbius est à l'origine de la conjecture à quatre couleurs, mais cette notion semble erronée. Voir Biggs, Norman ; Lloyd, E. Keith; Wilson, Robin J. (1986), Théorie des graphes, 1736–1936 , Oxford University Press, p. 116 , ISBN 0-19-853916-9& Maddison, Isabel (1897), "Note sur l'histoire du problème de la coloration des cartes", Bull. Amer. Mathématiques. Soc. , 3 (7): 257, doi : 10.1090/S0002-9904-1897-00421-9
  7. ^ Donald MacKenzie, Preuve mécanisée: informatique, risque et confiance (MIT Press, 2004) p103
  8. ^ FG (1854) ; McKay (2012)
  9. ^ a b De Morgan (anonyme), Augustus (14 avril 1860), "La philosophie de la découverte, chapitres historiques et critiques. Par W. Whewell.", The Athenaeum : 501–503
  10. ^ WW Rouse Ball (1960) Le théorème des quatre couleurs , dans Mathematical Recreations and Essays, Macmillan, New York, pp 222–232.
  11. ^ Thomas (1998) , p. 848.
  12. ^ Heawood (1890) .
  13. ^ Tait (1880) .
  14. ^ Hadwiger (1943) .
  15. ^ un b Wilson (2014) .
  16. ^ Gary Chartrand et Linda Lesniak, Graphs & Digraphs (CRC Press, 2005) p.221
  17. ^ Wilson (2014) ; Appel & Haken (1989) ; Thomas (1998 , p. 852-853)
  18. ^ Thomas (1995) ; Robertson et al. (1996) ).
  19. ^ Thomas (1998) , pp. 852–853.
  20. ^ Thomas (1999) ; Pegg et al. (2002) ).
  21. ^ Gonthier (2008) .
  22. ^ Dailey, DP (1980), "L'unicité de la colorabilité et la colorabilité des graphes plans 4-réguliers sont NP-complets", Discrete Mathematics , 30 (3): 289–293, doi : 10.1016/0012-365X(80)90236- 8
  23. ^ Steinberg, Richard (1993), "L'état du problème des trois couleurs", dans Gimbel, John; Kennedy, John W.; Quintas, Louis V. (eds.), Quo Vadis, Théorie des graphes ? , Annals of Discrete Mathematics, vol. 55, Amsterdam: North-Holland, pp. 211–248, doi : 10.1016/S0167-5060(08)70391-1 , MR  1217995
  24. ^ Ringel (1974) .
  25. ^ Gethner, Ellen (2018), "Vers la Lune et au-delà", à Gera, Ralucca ; Haynes, Teresa W. ; Hedetniemi, Stephen T. (eds.), Théorie des graphes : conjectures favorites et problèmes ouverts, II , Problem Books in Mathematics, Springer International Publishing, pp. 115–133, doi : 10.1007/978-3-319-97686-0_11 , M.  3930641
  26. ^ Bar-Natan (1997) .

Les références

Liens externes