Vérifié contenu

Théorème des quatre couleurs

Sujets connexes: Mathématiques

Saviez-vous ...

SOS Enfants a fait cette sélection Wikipedia aux côtés d'autres écoles des ressources . parrainage SOS enfant est cool!

Exemple d'une carte à quatre couleurs

Le théorème des quatre couleurs (aussi connu comme la carte théorème des quatre couleurs) indique que, compte tenu tout plan séparé en régions, comme une carte politique des Etats d'un pays, les régions peuvent être colorés en utilisant pas plus de quatre couleurs de manière que deux régions adjacentes reçoivent la même couleur. Deux régions sont appelées à côté que se ils partagent un segment de la frontière, et pas seulement un point. Chaque région doit être contigu: autrement dit, il peut ne pas être enclaves comme certains pays réels tels que l'Angola , l'Azerbaïdjan , l' États-Unis ou la Russie .

Ce est souvent le cas que l'utilisation de seulement trois couleurs est insuffisante. Cela se applique déjà à la carte avec une région entourée par trois autres régions (mais avec un nombre pair de pays environnants trois couleurs sont assez) et il ne est pas du tout difficile de prouver que cinq couleurs suffisent pour colorier une carte.

Le théorème des quatre couleurs était le premier grand théorème à démontrer l'utilisation d'un ordinateur, et la preuve ne est pas acceptée par tous les mathématiciens, car il serait impossible pour un humain de vérifier à la main (voir la preuve assistée par ordinateur). En fin de compte, pour croire la preuve, il faut avoir la foi en la justesse de la compilateur et l'exécution du programme matériel utilisé pour l'épreuve.

Le manque d'élégance mathématique par la communauté mathématique générale était un autre facteur, et pour paraphraser les commentaires de l'époque, "une bonne preuve mathématique est comme un poème-ce est un répertoire téléphonique! "

Histoire

Le conjecture a été proposée pour la première en 1852 lorsque Francis Guthrie, tout en essayant de colorer la carte de comtés de l'Angleterre , a remarqué que seulement quatre couleurs différentes ont été nécessaires. À l'époque, le frère de Guthrie, Fredrick, était un étudiant de Auguste De Morgan au University College. Francis demanda avec Fredrick son sujet, qui a ensuite pris à De Morgan. (Fredrick Guthrie a obtenu plus tard en 1852, et plus tard est devenu un professeur de mathématiques en Afrique du Sud ). Selon De Morgan:

Un de mes étudiants [Guthrie] m'a demandé aujourd'hui de lui donner une raison à un fait que je ne savais pas, ce est un fait - et ne avez pas encore. Il dit que si un chiffre est en tout cas divisé et les compartiments de couleurs différentes de sorte que les chiffres avec une partie de la ligne de frontière commune sont de couleurs différentes - quatre couleurs peuvent être voulu, mais pas plus-qui suit est le cas dans lequel quatre couleurs sont recherchés. Requête ne peut pas une nécessité pour cinq ou plus être inventé ...

La première référence est publié par Arthur Cayley, qui crédite ensuite la conjecture de De Morgan.

Il ya eu plusieurs tentatives infructueuses de début prouver le théorème . Une preuve du théorème a été donnée par Alfred Kempe en 1879, qui a été largement acclamé; une autre preuve a été donnée par Peter Guthrie Tait en 1880. Ce ne est qu'en 1890 que la preuve de Kempe a été montré par incorrecte Percy Heawood et 1891 que la preuve de Tait a été montré par incorrecte Julius Petersen-chaque fausse preuve ne était pas contestée pendant 11 ans.

En 1890, en plus d'exposer la faille dans la preuve de Kempe, Heawood prouvé que tous les graphes planaires sont cinq coloriable; voir cinq théorème de couleur.

Des résultats significatifs ont été réalisés par la Croatie mathématicien Danilo Blanusa dans les années 1940 en trouvant un original snark.

Pendant les années 1960 et 1970 en allemand mathématicien Heinrich Heesch a développé des méthodes d'application de la ordinateur à la recherche de la preuve.

Ce ne est qu'en 1976 que la conjecture quatre couleurs a finalement été prouvé par Kenneth Appel et Wolfgang Haken au Université de l'Illinois. Ils étaient assistés dans certains travaux par algorithmique John Koch.

Si la conjecture de quatre couleurs étaient fausses, il y aurait au moins une carte avec le plus petit nombre possible de régions qui nécessite cinq couleurs. La preuve a montré qu'une telle contre-exemple minimal ne peut exister par l'utilisation de deux concepts techniques:

  • Un jeu incontournable contient des régions telles que chaque carte doit avoir au moins une région de cette collection.
  • Une configuration réductible est un arrangement de pays qui ne peuvent pas se produire dans un contre-minime. Si une carte contient une configuration réductible, et le reste de la carte peut être coloré avec quatre couleurs, la carte entière peut être coloré avec quatre couleurs et ainsi de cette carte ne est pas minime.

Utilisation des règles et des procédures mathématiques basés sur les propriétés des configurations réductibles (par exemple, le méthode de décharge, bagues, chaînes Kempe, etc.), Appel et Haken trouvé un ensemble inévitable de configurations réductibles, prouvant ainsi que un contre minimal pour la conjecture quatre couleurs ne pourrait pas exister. Leur démonstration réduit l'infinité de cartes possibles pour 1936 configurations réductibles (plus tard réduite à 1476) qui devait être vérifié un par un par ordinateur. Cette partie de réductibilité du travail a été indépendamment une double vérification avec différents programmes et les ordinateurs. Cependant, la partie inévitabilité de la preuve était plus de 500 pages manuscrites de contre-contre-exemples, dont une grande partie était fils adolescent de Haken Lippold vérifier colorations de graphes. Le programme informatique a couru pour des centaines d'heures.

Depuis le proving du théorème, des algorithmes efficaces ont été trouvés pour les cartes 4-colorants nécessitant seulement O (n 2) fois, où n est le nombre de sommets. En 1996 , Neil Robertson, Daniel P. Sanders, Paul Seymour, Thomas et Robin créé un algorithme quadratique du temps, en utilisant Le travail d'Edward Belaga pour améliorer un algorithme quartique sur la base de la preuve de Appel et Haken. Cette nouvelle preuve est similaire à Appel et Haken de mais plus efficace car il réduit la complexité du problème et doit vérifier seulement 633 configurations réductibles. Les deux parties inéluctable et réductibilité de cette nouvelle preuve doivent être exécutées par ordinateur et ne sont pas pratiques pour vérifier à la main.

En 1980, George Spencer-Brown a déposé sa preuve supposée de la carte théorème des quatre couleurs à la Royal Society. La validité de cette preuve, qui constitue l'annexe 5 de la traduction allemande de son livre " Lois du formulaire "(Lübeck 1997), est généralement mis en doute.

En 2004 Benjamin Werner et Georges Gonthier a formalisé une preuve du théorème à l'intérieur du Assistant de preuves Coq (Gonthier, sd). Cela supprime la nécessité de faire confiance aux divers programmes informatiques utilisés pour vérifier des cas particuliers; il est seulement nécessaire de faire confiance au noyau Coq.

Il ya aussi des algorithmes efficaces pour déterminer si une ou deux couleurs suffisent pour colorier une carte. Déterminer si trois couleurs suffisent est, cependant, NP-complet, et donc un algorithme rapide est peu probable. Déterminer si un général (éventuellement non plane) graphique peut être quatre-couleur est également NP-complet.

Pas pour les cartographes

Bien que le théorème des quatre couleurs a été découvert dans le processus de coloration d'une vraie carte, il est rarement utilisé en pratique cartographie. Selon Kenneth mai, un historien mathématique qui a étudié un échantillon d'atlas à la Bibliothèque du Congrès, il n'y a pas tendance à minimiser le nombre de couleurs utilisées. Beaucoup de cartes utilisent la couleur pour des choses autres que les régions politiques. La plupart des cartes utilisent plus de quatre couleurs, et quand seulement quatre couleurs sont utilisées, généralement le nombre minimum de couleurs effectivement nécessaires est inférieur à quatre.

Sur la plupart des cartes réelles il ya des lacs, qui doivent tous être de la même couleur. Ce est alors supplémentaire pour les couleurs qui sont obligatoires pour les régions politiques. Si les lacs sont comptés comme une seule région, le théorème ne se applique pas. Il peut être appliqué aux zones terrestres du carte seule en considérant les lacs que ne appartenant pas à la carte des régions, mais sur des cartes réelles de plusieurs non- régions de carte contigus peuvent en outre appartenir à une seule non- connecté région politique et exigent la même couleur (voir ci-dessous ), alors là encore le théorème ne se applique pas.

Manuels sur la cartographie et de la histoire de la cartographie ne mentionnent pas le théorème des quatre couleurs, même si coloration de la carte est un sujet de discussion. Généralement, les cartographes disent qu'ils sont plus préoccupés par la coloration cartes politiques de façon équilibrée, de sorte qu'aucune couleur unique domine. Qu'ils utilisent quatre, cinq ou plus de couleurs ne est pas une préoccupation majeure.

Déclaration officielle en théorie des graphes

Pour indiquer formellement le théorème, il est plus facile de reformuler dans la théorie des graphes. Il déclare ensuite que le sommets de chaque graphe planaire peut être coloré avec au plus quatre couleurs de sorte que deux sommets adjacents reçoivent la même couleur. Ou "tout graphe planaire est quatre coloriable" pour faire court. Ici, chaque région de la carte est remplacé par un sommet du graphe, et deux sommets sont reliés par une bord si et seulement si les deux régions partagent un segment de bordure (pas seulement un coin).

Quatre Couleur Planar graph.svg

Faux réfutations

Comme beaucoup de célèbres problèmes ouverts de mathématiques, le théorème des quatre couleurs a attiré un grand nombre de fausses preuves et réfutations de sa longue histoire. Certains, comme Kempe et de Tait mentionné ci-dessus, se tenait à l'examen public pendant plus d'une décennie avant ils ont été exposés. Mais beaucoup d'autres, rédigé par des amateurs, ne ont jamais été publiés du tout.

4CT non Contre 1.svg
4CT non Contre 2.svg
Cette carte a été coloré avec cinq couleurs ... ... Mais il est nécessaire de modifier au moins quatre des dix régions pour obtenir une coloration avec seulement quatre couleurs.

Généralement, la tentative la plus simple "des contre-» pour créer une région qui touche toutes les autres régions. Cela force les autres régions à colorer avec seulement trois couleurs. Parce que le théorème des quatre couleurs est vrai, ce est toujours possible; Cependant, parce que la personne dessiner la carte est axée sur une vaste région, ils ne ont pas remarqué que les autres régions peuvent en effet être colorés avec trois couleurs.

Cette astuce peut être généralisée: il ya beaucoup de cartes où, si les couleurs de certaines régions sont sélectionnés à l'avance, il devient impossible de colorier les régions restantes sans dépasser quatre couleurs. Un vérificateur occasionnel de la contre-ne peut pas penser à changer les couleurs de ces régions, de sorte que le contre apparaît comme si elle est valide.

Peut-être un effet de base de cette idée fausse commune est le fait que la restriction de couleur ne est pas transitive: une région ne doit être colorée différemment régions, il touche directement, et non les régions touchant les régions qu'il touche. Si ce était la restriction, graphes planaires exigeraient arbitrairement un grand nombre de couleurs.

Autres fausses réfutations violent les hypothèses du théorème de manière inattendue, comme l'utilisation d'une région qui se compose de plusieurs parties déconnectées, ou en interdisant les régions de la même couleur de toucher à un point.

Généralisations

En rejoignant les flèches simples ensemble et les doubles flèches ensemble, on obtient un tore avec sept régions mutuellement touchantes; donc sept couleurs sont nécessaires
Cette construction montre les tore divisé par le maximum de sept régions, dont chacune touche tous les autres.

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 cylindre est équivalente à celle de l'avion. Pour fermée (orientable ou non orientable) surfaces avec positif genre, le nombre maximum de p couleurs nécessaires dépend de la surface caractéristique d'Euler χ selon la formule

p = \ left \ lfloor \ frac {7 + \ sqrt {49-24 \ chi}} {2} \ right \ rfloor ,

où les parenthèses indiquent le plus à l'extérieur fonction de-chaussée. La seule exception à la formule est la bouteille de Klein , qui a caractéristique d'Euler 0 et nécessite 6 couleurs. Ce était initialement connu sous le nom Conjecture Heawood et prouvé que La Carte Couleur théorème par Gerhard Ringel et JTW Youngs en 1968.

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

p = \ left \ lfloor \ frac {7 + \ sqrt {1 + 48g}} {2} \ right \ rfloor.

Par exemple, le tore possède Euler caractéristique χ = 0 (et genre g = 1), et donc p = 7, de sorte que pas plus de sept couleurs sont nécessaires pour colorer ne importe quelle carte sur un tore.

Un Ruban de Möbius exige également six couleurs.

Il n'y a pas d'extension utile du problème de coloration des régions solides tridimensionnels. Il est trivial de construire un ensemble de n tiges flexibles, par exemple, de telle sorte que chaque tige touche chaque autre tige. L'ensemble nécessiterait alors n couleurs ou n + 1 si vous considérez l'espace vide qui touche également tous les tige. n peut être considéré comme un nombre entier quelconque, aussi grande que souhaitée.

Les régions non-contiguës

Exemple d'une carte avec des régions non-contiguës

Dans le monde réel, tous les pays ne sont contigus (par exemple, Alaska dans le cadre de la Etats-Unis , Nakhitchevan dans le cadre de l'Azerbaïdjan , et Kaliningrad dans le cadre de la Russie ). Si le schéma de couleurs choisie exige que le territoire d'un pays donné doit être de la même couleur, quatre couleurs peuvent ne pas être suffisant. Par exemple, considérons une carte simplifiée:

4CT Insuffisance example.svg

Dans cette carte, les deux régions étiquetées A appartiennent au même pays, et doit être de la même couleur. Cette carte nécessite alors cinq couleurs, étant donné que les deux régions sont contiguës A, conjointement avec quatre autres régions, dont chacun est contigu à toutes les autres. Si A est composée de trois régions, six couleurs ou plus pourrait être nécessaire; on peut construire des cartes qui nécessitent un nombre arbitrairement élevé de couleurs.

Récupéré à partir de " http://en.wikipedia.org/w/index.php?title=Four_color_theorem&oldid=196560585 "