Théorème des quatre couleurs

La source: http://people.math.gatech.edu/~thomas/FC/fourcolor.html

Cette page donne un bref résumé d’une nouvelle preuve des théorème des quatre couleurs et un algorithme de quatre-Coloriage trouvé par Neil Robertson, Daniel P. Sanders, Paul Seymour et Robin Thomas.


USA


Table des matières :

  1. Histoire.
  2. Pourquoi une nouvelle preuve ?
  3. Plan de la preuve.
  4. Principales caractéristiques de notre preuve.
  5. Configurations.
  6. Décharge règles.
  7. Pointeurs.
  8. Un algorithme quadratique.
  9. Discussion.
  10. Références.

Histoire.

La remonte de quatre problèmes de couleur en 1852 lorsque Francis Guthrie, alors qu’il tentait de colorier la carte des comtés d’Angleterre a remarqué que quatre couleurs a suffi. Il a demandé à son frère Frederick si c’était vrai que toute carte peut être colorée en utilisant quatre couleurs de telle sorte que les régions adjacentes (c’est-à-dire un segment de frontière commune, pas seulement d’un point de partage) reçoivent des couleurs différentes. Frederick Guthrie a ensuite communiqué la conjecture à DeMorgan. La première référence écrite est due à Cayley en 1878.

Un an plus tard, la première « preuve » de Kempe est apparu ; son inexactitude a été souligné par Heawood 11 ans plus tard. Une autre preuve ayant échouée doit avoir Tait en 1880 ; une lacune dans l’argument a été soulignée par Petersen en 1891. Les deux épreuves ayant échouées ai eu quelque valeur, cependant. Kempe a découvert ce qui est devenu connu comme chaînes de Kempe et Tait trouvé une formulation équivalente du théorème des quatre couleurs en termes de 3-bord-coloriage.

La prochaine contribution majeure provenait de Birkhoff dont le travail a permis de Franklin en 1922 pour prouver que la conjecture des quatre couleurs est vraie pour les cartes avec plus de 25 régions. Il était également utilisé par autres mathématiciens de faire différentes formes de progrès sur le problème des quatre couleurs. Il faut mentionner spécifiquement Heesch qui a développé les deux principaux ingrédients nécessaires à la preuve ultime – reducibility et la décharge. Alors que le concept de reducibility a été étudié par d’autres chercheurs aussi bien, il semble que l’idée d’avoir déchargé, crucial pour la partie du caractère inéluctable de la preuve, est due à Heesch, et que c’est lui qui conjecturé qu’un développement adapté de cette méthode serait résoudre le problème de couleur quatre.

Ceci a été confirmé par Appel et Haken en 1976, quand ils ont publié leur preuve du théorème de couleurs quatre [1,2].

Pourquoi une nouvelle preuve ?

Il y a deux raisons pourquoi la preuve de l’Appel-Haken n’est pas tout à fait satisfaisante.

  • Partie de la preuve de l’Appel-Haken utilise un ordinateur et ne peut être vérifiée à la main, et
  • même la partie qui est censé être main-contrôlable est extraordinairement compliquée et fastidieuse, et qu’autant que nous sachions, personne n’a vérifié il dans son intégralité.

Nous ont en fait tenté de vérifier la preuve de l’Appel-Haken, mais bientôt abandonné. Vérification de la part de l’ordinateur n’exigerait pas seulement beaucoup de programmation, mais aussi inputing les descriptions des graphes de 1476, et qui n’était même pas la partie la plus controversée de la preuve.

Nous avons décidé qu’il serait plus rentable de travailler à notre propre preuve. Donc, nous avons fait et est venu avec une preuve et un algorithme qui sont décrits ci-dessous.

Présentation de la preuve.

L’idée de base de la preuve est le même que l’Appel et de Haken. Nous présentent un ensemble de 633 « configurations » et de prouver à chacun d’eux est « reducible ». Il s’agit d’un concept technique qui implique qu’aucune configuration avec cette propriété ne peut apparaître dans un contre-exemple minime pour le théorème des quatre couleurs. Il peut également être utilisé dans un algorithme, car si une configuration réductible apparaît dans un graphe planaire G, alors on peut construire en temps constant un plus petit graphe planaire G’ telle que tous les quatre-coloriage de G’ peut être converti en un quatre-coloriage de G en temps linéaire.

On sait depuis 1913 que chaque minime contre-exemple au théorème des quatre de couleurs est une triangulation 6-reliée en interne. Dans la deuxième partie de la preuve, nous démontrons qu’au moins une de nos 633 configurations apparaît dans chaque triangulation plane 6-reliée en interne (pas nécessairement un contre-exemple minime à la CT 4). Ceci s’appelle prouvant le caractère inéluctable et utilise le « discharging method », première fois suggérée par Heesch. Ici, notre méthode diffère de celle de l’Appel et Haken.

Principales caractéristiques de notre preuve.

Nous confirmons une conjecture de Heesch qu’à prouver le caractère inéluctable, une configuration réductible peut être trouvée dans le second quartier d’un « overcharged » vertex ; C’est comment éviter « immersion » les problèmes qui ont été une importante source de complication pour l’Appel et Haken. L’ensemble de nos inévitable a taille 633 par opposition à l’ensemble de 1476 membres de Appel et Haken, et notre méthode de décharge utilise seulement 32 en déchargeant les règles, au lieu des 300 + d’Appel et Haken. Enfin, on obtient un algorithme quadratique à quatre couleurs graphes planaires (décrit plus loin), une amélioration par rapport à l’algorithme quartique d’Appel et Haken.

Configurations.

Une proximité par triangulation est un graphe de plan loopless connectés non nulle telle que chaque région finie est un triangle. Une configuration K se compose d’un proche par triangulation et un g carte de v (g) pour les entiers avec les propriétés suivantes :

  1. pour chaque sommet v, Gv a au plus deux composantes, et s’il y en a deux, alors le degré de v est g (v) -2,
  2. pour chaque sommet v, si v n’est pas incidente avec la région infinie, alors g (v) est égale à la mesure de v, et sinon g (v) est supérieure à la mesure de v ; et dans des cas non plus g > 4,
  3. K a anneau-taille au moins 2, où la taille de l’anneau de K est défini comme étant la somme de g (v)-deg (v) -1, a résumé sur tout incident v de sommets avec la région infinie, telle que Gv est connecté.

Lorsque vous dessinez des images des configurations nous utilisons une convention introduite par Heesch. Les formes des sommets d’indiquent la valeur de g (v) comme suit : un cercle noir solid signifie g (v) = 5, un point (ou ce qui n’apparaît dans l’image comme aucun symbole du tout) signifie g (v) = 6, un cercle creux signifie g (v) = 7, un creux carrés moyens g (v) = 8 , un triangle signifie g (v) = 9 et un pentagone moyen g (v) = 10. (Nous ne devons pas les sommets v avec g > 11 et qu’un seul sommet avec g (v) = 11, pour laquelle nous n’utilisons pas n’importe quel symbole spécial.) Dans l’image ci-dessous 17 de nos configurations réductibles 633 sont affichés à l’aide de la convention indiquée. (Nous nous référons à (3.2) de notre papier [7] pour la signification des « thick edges » et « half-edges » dans ces images.)


Confs


N’importe quelle configuration isomorphe à une des 633 configurations exposées dans [7] est appelée une bonne configuration. Soit T une triangulation. Une configuration K=(G,g) apparaît dans T si G est un sous-graphe induit de T, chaque région finie de G est une région de T et g est égal au degré de v en T pour chaque vertex de v de G. Nous démontrons les deux instructions suivantes.

Théorème 1. Si T est un contre-exemple minime pour le théorème des quatre couleurs, aucune bonne configuration n’apparaît ensuite dans T.

Théorème 2. Pour chaque connecté en interne 6 triangulation T, une bonne configuration apparaît dans T.

Depuis les deux théorèmes ci-dessus, il s’ensuit qu’aucun contre-exemple minime n’existe, et donc le 4CT est vrai. La première preuve a besoin d’un ordinateur. Le second peut être vérifié à la main dans quelques mois, ou, à l’aide d’un ordinateur, il peut être vérifié en environ 20 minutes.

Evacuation des règles.

Soit T une triangulation 6-reliée en interne. Au départ, chaque vertex v est assignée à une accusation de 10(6-deg(v)). Il résulte de la formule d’Euler que la somme des charges de tous les sommets est de 120 ; en particulier, il est positif. Nous redistribuons maintenant les frais selon les règles suivantes, comme suit. Chaque fois que T a un sous-graphe isomorphe à l’un des graphiques dans la figure ci-dessous répondant aux spécifications de degré (pour un v vertex d’une règle avec un signe moins à côté de v, cela signifie que le degré du sommet correspondant de T est au maximum la valeur spécifiée par la forme o f v et par analogie pour les sommets avec un signe plus à côté d’eux ; l’égalité est requise pour les sommets sans signe à côté d’eux) une charge d’un (deux dans le cas de la première règle) doit être envoyé le long du bord avec une flèche.


Rules


Cette procédure définit un nouvel ensemble de charges avec la même somme totale. Étant donné que la somme totale est positive, il y a un sommet v en T dont nouvelle accusation est positive. Nous montrons qu’une bonne configuration apparaît dans le deuxième quartier de v.

Si le degré de v est au plus 6 ou au moins de 12, puis le voit assez facilement par un argument direct. Dans les autres cas, cependant, les preuves sont beaucoup plus compliquées. Par conséquent, nous avons écrit les épreuves dans un langage formel afin qu’ils peuvent être vérifiées par un ordinateur. Chaque étape individuelle de ces épreuves est vérifiable à l’homme, mais les preuves elles-mêmes ne sont pas vraiment contrôlable à la main, à cause de leur longueur.

Pointeurs.

La partie théorique de notre preuve est décrite dans [7]. Une étude de 10 pages est disponible en ligne. Les programmes et les données de l’ordinateur utilisé pour être situé sur un serveur ftp anonyme, mais ce serveur a été éliminé. Les mêmes fichiers sont maintenant disponibles à http://www.math.gatech.edu/~thomas/OLDFTP/four/. Un ensemble indépendant de programmes a été écrit par George Fijavz< under=" the=" guidance=" of=" bojan=" mohar.=">

Un algorithme quadratique.

L’entrée de l’algorithme sera une triangulation plan G avec n sommets. (C’est sans perte de généralité, que tout graphe planaire peut être triangulé en temps linéaire). La sortie sera une coloration des sommets du G avec quatre couleurs.

Si G a au plus quatre sommets couleur une couleur différente à chaque sommet. Sinon si G possède un sommet x de degré k < 5, puis le circuit C qui l’entoure est un anneau « k ». Accédez à l’analyse des anneaux k ci-dessous. Sinon G a degré minimum cinq. Pour chaque sommet, nous calculons sa charge comme expliqué ci-dessus et trouver un v vertex de charge positive. Il découle de notre preuve du théorème 2 qui soit une bonne configuration apparaît dans le deuxième quartier de v (il auquel cas il peut être trouvé dans le temps linéaire), ou un anneau k violer que la définition de 6-connexion interne se trouvent en temps linéaire. Dans ce dernier cas, nous allons à l’analyse de k-bague ci-dessous, dans le premier cas nous appliquons la récursivité pour certain un graphique plus petit. Une quatre-coloration de G puis peut être construite à partir du quatre-coloriage de ce petit graphique en temps linéaire.

Étant donné un anneau k R violant la définition de 6-connexion interne une procédure développée par Birkhoff peut être utilisé. Nous appliquons la récursivité à deux sous-graphes soigneusement sélectionnés de G. Un quatre-coloriage de G peut alors être construit à partir les quatre-Coloriages des deux plus petits graphiques en temps linéaire.

Discussion.

Il faut souligner que tant nos programmes utilisent seulement arithmétique sur les entiers et donc nous ne devons pas être concernés par les erreurs d’arrondi et dangers similaires de floating point arithmetic. Cependant, un argument peut faire que notre « preuve » n’est pas une preuve au sens traditionnel du terme, car il contient des étapes qui ne peuvent jamais être vérifiées par les humains. En particulier, nous n’avons pas prouvé le bien-fondé du compilateur sur que nous avons compilé nos programmes, ni si nous avons prouvé l’infaillibilité du matériel sur que nous avons manqué nos programmes. Celles-ci doivent être prises sur la foi et sont en théorie une source d’erreur. Cependant, d’un point de vue pratique, la possibilité d’une erreur informatique qui apparaît constamment en exactement de la même façon sur toutes les courses de nos programmes sur tous les compilateurs sous tous les systèmes d’exploitation fonctionnant sur nos programmes est infiniment petite par rapport à la probabilité d’une erreur humaine au cours de la même quantité de cas-contrôle. En dehors de cette possibilité hypothétique d’un ordinateur constamment ce qui donne une réponse incorrecte, le reste de notre preuve peut être vérifié de la même manière comme des preuves mathématiques traditionnelles. Nous admettons, cependant, que la vérification d’un programme d’ordinateur est beaucoup plus difficile que la vérification d’une démonstration mathématique de la même longueur.

Accusés de réception.

Nous sommes redevables à Thomas Fowler, les Christopher Carl Heckman et les murs de Barrett pour leur aide à la préparation de cette page. Notre travail a été partiellement soutenu par la National Science Foundation.

Références.

  1. Appel de K. et W. Haken, chaque carte plane est quatre colorable. Partie I. déchargement, Illinois J. Math. 21 (1977), 429-490.
  2. K. appel de w. Haken et J. Koch, chaque carte plane est quatre colorable. Partie II. Reducibility, Illinois J. Math. 21 (1977), 491–567.
  3. Appel de K. et W. Haken, chaque carte plane est quatre colorable, mathématiques contemporaines. 98 (1989).
  4. G. D. Birkhoff, le reducibility de cartes, Amer. J. Math. 35 (1913), 114-128.
  5. H. Heesch, Untersuchungen zum Vierfarbenproblem, Hochschulskriptum 810/a/b, Bibliographisches Institut, Mannheim, 1969.
  6. A. B. Kempe, sur le problème géographique des quatre couleurs, amer. J. Math., 2 (1879), 193-200.
  7. N. Robertson, D. P. Sanders, P. d. Seymour et r. Thomas, le théorème des quatre couleurs, J. Combin. La théorie SER. B. 70 (1997), 2-44.
  8. N. Robertson, D. P. Sanders, P. d. Seymour et R. Thomas, une nouvelle preuve des quatre couleurs théorème, électron. M res. Amer. Math. SOC 2 (1996), 17-25 (électronique).
  9. T.L. Saaty, treize variations colorées sur des conjectures de quatre couleurs de Guthrie, amer. Math. Mensuel 79 (1972), 2-43.
  10. T.L. Saaty et P. C. Kainen, le problème des quatre couleurs. Agressions et conquête, Dover Publications, New York, 1986.
  11. P. G. Tait, Note sur un théorème de géométrie de position, trad. Roy. SOC., Edinburgh 29 (1880), 657-660.
  12. H. Whitney et W. T. Tutte, chaînes de Kempe et le problème des quatre couleurs », dans études en théorie des graphes, partie II (dir. D. R. Fulkerson), Math. Assoc. de l’Amérique, 1975, 378-413.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *