In der Mathematik, dem vier Farbenlehrsatz oder dem vier Farbenkarte-Lehrsatz stellt fest, dass, in Anbetracht jeder Trennung eines Flugzeugs in aneinander grenzende Gebiete, eine Zahl erzeugend, eine Karte genannt hat, nicht mehr als sind vier Farben erforderlich, die Gebiete der Karte zu färben, so dass keine zwei angrenzenden Gebiete dieselbe Farbe haben. Zwei Gebiete werden angrenzend genannt, wenn sie eine allgemeine Grenze teilen, die nicht eine Ecke ist, wo Ecken die durch drei oder mehr Gebiete geteilten Punkte sind. Zum Beispiel, in der Karte der Vereinigten Staaten von Amerika, sind Utah und Arizona angrenzend, aber Utah und New Mexico, die nur einen Punkt teilen, der auch nach Arizona und Colorado gehört, sind nicht.

Trotz der Motivation davon, politische Karten von Ländern zu färben, ist der Lehrsatz nicht vom besonderen Interesse Kartographen. Gemäß einem Artikel vom Mathehistoriker Kenneth May, "Sind Karten, die nur vier Farben verwerten, und diejenigen selten, die wirklich gewöhnlich nur drei verlangen. Bücher auf dem Kartenzeichnen und der Geschichte der Kartografie erwähnen das vierfarbige Eigentum nicht."

Drei Farben sind für einfachere Karten entsprechend, aber eine zusätzliche vierte Farbe ist für einige Karten wie eine Karte erforderlich, in der ein Gebiet durch eine ungerade Zahl anderer Gebiete umgeben wird, die einander in einem Zyklus berühren. Der fünf Farbenlehrsatz, der einen kurzen elementaren Beweis hat, stellt fest, dass fünf Farben genügen, um eine Karte zu färben, und gegen Ende des 19. Jahrhunderts bewiesen wurde; jedoch hat sich Beweis, dass vier Farben genügen, erwiesen, bedeutsam härter zu sein. Mehrere falsche Beweise und falsche Gegenbeispiele sind seit der ersten Behauptung des vier Farbenlehrsatzes 1852 erschienen.

Der vier Farbenlehrsatz wurde 1976 von Kenneth Appel und Wolfgang Haken bewiesen. Es war der erste Hauptlehrsatz, der verwendend eines Computers zu beweisen ist. Appel und die angefangene Annäherung von Haken durch die Vertretung, dass es einen besonderen Satz von 1,936 Karten gibt, von denen jede ein Teil eines am meisten klein-großen Gegenbeispiels zum vier Farbenlehrsatz nicht sein kann. Appel und Haken haben ein Computerprogramm des speziellen Zwecks verwendet, um zu bestätigen, dass jede dieser Karten dieses Eigentum hatte. Zusätzlich muss jede Karte (unabhängig davon, ob es ein Gegenbeispiel oder nicht ist) einen Teil haben, der wie eine dieser 1,936 Karten aussieht. Die Vertretung davon hat Hunderte von Seiten der Handanalyse verlangt. Appel und Haken haben beschlossen, dass keine kleinsten Gegenbeispiele bestanden haben, weil irgendwelcher enthalten, noch, eine dieser 1,936 Karten nicht enthalten muss. Dieser Widerspruch bedeutet, dass es keine Gegenbeispiele überhaupt gibt, und dass der Lehrsatz deshalb wahr ist. Am Anfang wurde ihr Beweis von allen Mathematikern nicht akzeptiert, weil der computergestützte Beweis für einen Menschen unausführbar war, mit der Hand zu überprüfen. Seitdem hat der Beweis breitere Annahme gewonnen, obwohl Zweifel bleiben.

Um restliche Zweifel über den Appel-Haken Beweis zu zerstreuen wurde ein einfacherer Beweis mit denselben Ideen und noch sich auf Computer verlassend, 1997 von Robertson, Sanders, Seymour und Thomas veröffentlicht. Zusätzlich 2005 wurde der Lehrsatz von Georges Gonthier mit der allgemeinen Zweck-Lehrsatz-Beweis-Software bewiesen.

Genaue Formulierung des Lehrsatzes

Die intuitive Behauptung des vier Farbenlehrsatzes, d. h. 'dass gegeben jede Trennung eines Flugzeugs in aneinander grenzende Gebiete, genannt eine Karte, können die Gebiete mit höchstens vier Farben gefärbt werden, so dass keine zwei angrenzenden Gebiete dieselbe Farbe haben' muss passend interpretiert werden, um richtig zu sein. Erstens, alle Ecken, Punkte, die dem gehören (technisch, sind im Verschluss) drei oder mehr Länder, muss ignoriert werden. Ohne diese Beschränkung können bizarre Karten (Gebiete des begrenzten Gebiets, aber unendlichen Umfangs verwendend), mehr als vier Farben verlangen.

Zweitens zum Zweck des Lehrsatzes muss jedes "Land" ein einfach verbundenes Gebiet, oder aneinander grenzend sein.

In der echten Welt ist das nicht wahr (z.B, Alaska als ein Teil der Vereinigten Staaten, Nakhchivan als ein Teil Aserbaidschans und Kaliningrad, weil ein Teil Russlands nicht aneinander grenzend ist). Weil das Territorium eines besonderen Landes dieselbe Farbe sein muss, können vier Farben nicht genügend sein. Denken Sie zum Beispiel eine vereinfachte Karte:

In dieser Karte haben die zwei Gebiete A etikettiert gehören demselben Land, und muss dieselbe Farbe sein. Diese Karte verlangt dann fünf Farben, seit den zwei Gebiete sind zusammen mit vier anderen Gebieten aneinander grenzend, von denen jedes mit ganz andere aneinander grenzend ist. Wenn Ein bestandene von drei Gebieten, sechs oder mehr Farben erforderlich sein könnten; man kann Karten bauen, die eine willkürlich hohe Zahl von Farben verlangen.

Ein leichterer, um Version des Lehrsatzes festzusetzen, verwendet Graph-Theorie. Der Satz von Gebieten einer Karte kann abstrakter als ein ungeleiteter Graph vertreten werden, der einen Scheitelpunkt für jedes Gebiet und einen Rand für jedes Paar von Gebieten hat, die ein Grenzsegment teilen. Dieser Graph ist planar (es ist wichtig zu bemerken, dass wir über die Graphen sprechen, die einige Beschränkungen gemäß der Karte haben, von der sie umgestaltet werden nur): Es kann im Flugzeug ohne Überfahrten durch das Stellen jedes Scheitelpunkts an einer willkürlich gewählten Position innerhalb des Gebiets gezogen werden, zu dem es, und durch die Zeichnung der Ränder als Kurven entspricht, die führen, ohne sich innerhalb jedes Gebiets von der Scheitelpunkt-Position bis jeden geteilten Grenzpunkt des Gebiets zu treffen. Umgekehrt kann jeder planare Graph aus einer Karte auf diese Weise gebildet werden. In der mit dem Graphen theoretischen Fachsprache stellt der vierfarbige Lehrsatz fest, dass die Scheitelpunkte jedes planaren Graphen mit höchstens vier Farben gefärbt werden können, so dass keine zwei angrenzenden Scheitelpunkte dieselbe Farbe, oder für den kurzen erhalten, "ist jeder planare Graph vierangeblich" .

Geschichte

Frühe Probeversuche

Die Vermutung wurde zuerst 1852 vorgeschlagen, als Francis Guthrie, während er versucht hat, die Karte von Grafschaften Englands zu färben, bemerkt hat, dass nur vier verschiedene Farben erforderlich waren. Zurzeit war der Bruder von Guthrie, Frederick, ein Student von Augustus De Morgan in der Universitätsuniversität. Francis hat mit Frederick bezüglich seiner gefragt, der es dann De Morgan gebracht hat (Francis Guthrie hat später 1852 graduiert, und ist später ein Professor der Mathematik in Südafrika geworden). Gemäß De Morgan:

"F.G"., vielleicht einer von den zwei Guthries, hat die Frage im Athenaeum 1854 veröffentlicht, und De Morgan hat die Frage wieder in derselben Zeitschrift 1860 gestellt. Eine andere frühe veröffentlichte Verweisung durch der Reihe nach Kredite die Vermutung De Morgan.

Es gab mehrere frühe erfolglose Versuche des Beweises des Lehrsatzes. Ein Beweis wurde von Alfred Kempe 1879 gegeben, der weit mit Jubel begrüßt wurde; einem anderen wurde von Peter Guthrie Tait 1880 gegeben. Erst als 1890, dass der Beweis von Kempe falsch von Percy Heawood, und 1891 dem Beweis von Tait gezeigt wurde, falsch von Julius Petersen gezeigt wurde — hat jeder falsche Beweis unbestritten seit 11 Jahren gestanden.

1890, zusätzlich zum Herausstellen des Fehlers im Beweis von Kempe, hat Heawood den fünf Farbenlehrsatz bewiesen und hat verallgemeinert die vier Farbenvermutung zu Oberflächen der willkürlichen Klasse — sieh unten.

Bedeutende Ergebnisse wurden vom kroatischen Mathematiker Danilo Blanuša erzeugt, wer zwei snarks in den 1940er Jahren, jetzt bekannt als Blanuša snarks entdeckt hat; vor der Blanuša's Entdeckung war der einzige bekannte snark der Graph von Petersen (Weisstein).

1943 hat Hugo Hadwiger die Vermutung von Hadwiger, eine weit reichende Generalisation des vierfarbigen Problems formuliert, das noch ungelöst bleibt.

Beweis durch den Computer

Während der 1960er Jahre und des Deutschen der 1970er Jahre hat Mathematiker Heinrich Heesch Methoden entwickelt, Computer zu verwenden, um nach einem Beweis zu suchen. Namentlich er war erst, um Entladung zu verwenden, für den Lehrsatz zu beweisen, der sich erwiesen hat, im unavoidability Teil des nachfolgenden Appel-Haken Beweises wichtig zu sein. Er hat sich auch auf dem Konzept von reducibility und zusammen mit Ken Durre ausgebreitet, hat einen Computertest darauf entwickelt. Leider, an diesem kritischen Zeitpunkt, war er unfähig, die notwendige Supercomputerzeit zu beschaffen, um seine Arbeit fortzusetzen.

Andere haben seine Methoden und seine computergestützte Annäherung aufgenommen. 1976, während andere Mannschaften von Mathematikern liefen, um Beweise zu vollenden, haben Kenneth Appel und Wolfgang Haken an der Universität Illinois bekannt gegeben, dass sie den Lehrsatz bewiesen hatten. Ihnen wurde bei etwas algorithmischer Arbeit von John A. Koch geholfen.

Wenn die vierfarbige Vermutung falsch wäre, würde es mindestens eine Karte mit der kleinstmöglichen Zahl von Gebieten geben, die fünf Farben verlangt. Der Beweis hat gezeigt, dass solch ein minimales Gegenbeispiel durch den Gebrauch von zwei technischen Konzepten nicht bestehen kann :

• Ein unvermeidlicher Satz enthält solche Gebiete, dass jede Karte mindestens ein Gebiet von dieser Sammlung haben muss.
• Eine reduzierbare Konfiguration ist eine Einordnung von Ländern, die in einem minimalen Gegenbeispiel nicht vorkommen können. Wenn eine Karte eine reduzierbare Konfiguration enthält, dann kann die Karte auf eine kleinere Karte reduziert werden. Diese kleinere Karte hat die Bedingung, dass, wenn es mit vier Farben dann gefärbt werden kann, die ursprüngliche Karte auch kann. Das deutet an, dass, wenn die ursprüngliche Karte mit vier Farben nicht gefärbt werden kann, die kleinere Karte nicht irgendein kann, und so ist die ursprüngliche Karte nicht minimal.

Mit mathematischen Regeln und auf Eigenschaften von reduzierbaren Konfigurationen gestützten Verfahren haben Appel und Haken einen unvermeidlichen Satz von reduzierbaren Konfigurationen gefunden, so beweisend, dass ein minimales Gegenbeispiel zur vierfarbigen Vermutung nicht bestehen konnte. Ihr Beweis hat die Unendlichkeit von möglichen Karten zu 1,936 reduzierbaren Konfigurationen reduziert (später reduziert auf 1,476), der eins nach dem anderen durch den Computer überprüft werden musste und eintausend Stunden übernommen hat. Dieser reducibility Teil der Arbeit wurde mit verschiedenen Programmen und Computern unabhängig nochmals geprüft. Jedoch wurde der unavoidability Teil des Beweises in mehr als 400 Seiten des Mikrofiches nachgeprüft, der mit der Hand überprüft werden musste.

Appels Ansage und Hakens wurde von den Nachrichtenmedien um die Welt weit berichtet, und die Matheabteilung an der Universität Illinois hat einen Poststempel verwendet feststellend, dass "Vier Farben genügen." Zur gleichen Zeit die ungewöhnliche Natur des Beweises — es war der erste Hauptlehrsatz, der mit der umfassenden Computerhilfe — und die Kompliziertheit des menschlichen nachprüfbaren Teils zu beweisen ist, hat beträchtliche Meinungsverschiedenheit aufgeweckt.

Am Anfang der 1980er Jahre, Gerücht-Ausbreitung eines Fehlers im Appel-Haken Beweis. Ulrich Schmidt am RWTH Aachen hat Appels Beweis und Hakens für die These seines Masters untersucht. Er hatte ungefähr 40 % des unavoidability Teils überprüft und einen bedeutenden Fehler im sich entladenden Verfahren gefunden. 1986 wurden Appel und Haken vom Redakteur von Mathematischem Intelligencer gebeten, einen Artikel zu schreiben, die Gerüchte von Fehlern in ihrem Beweis richtend. Sie haben geantwortet, dass die Gerüchte wegen einer "Missdeutung der Ergebnisse [von Schmidt]" waren und einem ausführlichen Artikel vorgetragen haben. Ihr Anderthalbliterflasche-Opus, ein Buch, einen ganzen und ausführlichen Beweis (mit einer Mikrofiche-Ergänzung von mehr als 400 Seiten) fordernd, ist 1989 erschienen und hat die Entdeckung von Schmidt und mehrere weitere durch andere gefundene Fehler erklärt.

Vereinfachung und Überprüfung

Seit dem Beweis des Lehrsatzes sind effiziente Algorithmen für 4-Färben-Karten gefunden worden, die nur O (n) Zeit verlangen, wo n die Zahl von Scheitelpunkten ist. 1996 haben Neil Robertson, Daniel P. Sanders, Paul Seymour und Robin Thomas einen quadratischen Zeitalgorithmus geschaffen, einen quartic auf Appels Beweis und Hakens gestützten Algorithmus übertreffend . Dieser neue Beweis ist Appel und Haken ähnlich, aber effizienter, weil er die Kompliziertheit des Problems reduziert hat und Überprüfung nur 633 reduzierbarer Konfigurationen verlangt hat. Sowohl der unavoidability als auch die reducibility Teile dieses neuen Beweises müssen durch den Computer durchgeführt werden und sind unpraktisch, um mit der Hand zu überprüfen. 2001 haben dieselben Autoren einen alternativen Beweis bekannt gegeben, indem sie den snark Lehrsatz bewiesen haben .

2005 haben Benjamin Werner und Georges Gonthier einen Beweis des Lehrsatzes innerhalb des Probehelfers von Coq formalisiert. Das hat das Bedürfnis entfernt zu glauben, dass die verschiedenen Computerprogramme gepflegt haben, besondere Fälle nachzuprüfen; es ist nur notwendig, dem Kern von Coq zu vertrauen.

Zusammenfassung von Probeideen

Die folgende Diskussion ist eine Zusammenfassung, die auf der Einführung in Appels Buch und Hakens gestützt ist, Jede Planare Karte ist Vier Angeblich. Obwohl rissig gemacht, hat der ursprüngliche behauptete Beweis von Kempe des vier Farbenlehrsatzes einige der grundlegenden Werkzeuge zur Verfügung gestellt später hat gepflegt, es zu beweisen. Die Erklärung hier wird in Bezug auf die moderne Graph-Theorie-Formulierung oben umformuliert.

Das Argument von Kempe geht wie folgt. Erstens, wenn planare durch den Graphen getrennte Gebiete nicht trianguliert werden, d. h. genau drei Ränder in ihren Grenzen nicht haben, können wir Ränder hinzufügen, ohne neue Scheitelpunkte einzuführen, um jedes Gebiet dreieckig einschließlich des unbegrenzten Außengebiets zu machen. Wenn dieser triangulierte Graph das angebliche Verwenden von vier Farben oder weniger ist, auch der ursprüngliche Graph ist, da dasselbe Färben gültig ist, wenn Ränder entfernt werden. So genügt es, um den vier Farbenlehrsatz für triangulierte Graphen zu beweisen, um es für alle planaren Graphen zu beweisen, und ohne Verlust der Allgemeinheit wir annehmen, dass der Graph trianguliert wird.

Nehmen Sie v, e an, und f sind die Zahl von Scheitelpunkten, Rändern und Gebieten. Da jedes Gebiet dreieckig ist und jeder Rand durch zwei Gebiete geteilt wird, haben wir das 2e = 3f. Das zusammen mit der Formel v von Euler  e + f = 2 kann verwendet werden, um dass 6v  2e = 12 zu zeigen. Jetzt ist der Grad eines Scheitelpunkts die Zahl von Rändern, die es angrenzen. Wenn v die Zahl von Scheitelpunkten des Grads n ist und D der maximale Grad jedes Scheitelpunkts, ist

Aber seitdem 12> 0 und 6  i  0 für alles ich  6, das demonstriert, dass es mindestens einen Scheitelpunkt des Grads 5 oder weniger gibt.

Wenn es einen Graphen gibt, der 5 Farben verlangt, dann gibt es einen minimalen solcher Graph, wo das Entfernen jedes Scheitelpunkts ihn vierangeblich macht. Nennen Sie diesen Graphen G. G kann keinen Scheitelpunkt des Grads 3 oder weniger haben, weil, wenn d (v)  3, wir v von G, vierfarbig der kleinere Graph dann entfernen können, zurück v beitragen und den vier-Färben-dazu durch die Auswahl einer von seinen Nachbarn verschiedenen Farbe erweitern.

Kempe hat auch richtig gezeigt, dass G keinen Scheitelpunkt des Grads 4 haben kann. Wie zuvor entfernen wir den Scheitelpunkt v und vierfarbig die restlichen Scheitelpunkte. Wenn alle vier Nachbarn von v verschiedene Farben sind, rot, grün, blau, und gelb in im Uhrzeigersinn der Ordnung sagen, suchen wir nach einem Wechselpfad vom gefärbten roten und blauen Verbinden von Scheitelpunkten den roten und blauen Nachbarn. Solch ein Pfad wird eine Kette von Kempe genannt. Es kann eine Kette von Kempe geben, die sich den roten und blauen Nachbarn anschließt, und es kann eine Kette von Kempe geben, die sich den grünen und gelben Nachbarn, aber nicht beiden anschließt, da sich diese zwei Pfade notwendigerweise schneiden würden, und der Scheitelpunkt, wo sie sich schneiden, nicht gefärbt werden kann. Nehmen Sie an, dass es die roten und blauen Nachbarn sind, die zusammen nicht gekettet werden. Erforschen Sie alle Scheitelpunkte, die dem roten Nachbar durch rot-blaue Wechselpfade beigefügt sind, und dann kehren Sie die Farben um, die rot und auf allen diesen Scheitelpunkten blau sind. Das Ergebnis ist noch ein gültiger vier-Färben-, und v kann jetzt zurück hinzugefügt und rot gefärbt werden.

Das verlässt nur den Fall, wo G einen Scheitelpunkt des Grads 5 hat; aber das Argument von Kempe wurde für diesen Fall rissig gemacht. Heawood hat den Fehler von Kempe bemerkt und hat auch bemerkt, dass, wenn man mit dem Beweis von nur fünf Farben zufrieden war, erforderlich sind, konnte man das obengenannte Argument durchbohren (sich nur ändernd, dass das minimale Gegenbeispiel 6 Farben verlangt) und verwenden Sie Ketten von Kempe im Grad 5 Situation, um den fünf Farbenlehrsatz zu beweisen.

Jedenfalls, um sich mit diesem Grad zu befassen, verlangt 5 Scheitelpunkt-Fall einen mehr komplizierten Begriff als das Entfernen eines Scheitelpunkts. Eher wird die Form des Arguments zum Betrachten von Konfigurationen verallgemeinert, die verbundene Subgraphen von G mit dem Grad jedes Scheitelpunkts (in G) angegeben sind. Zum Beispiel ist der Fall, der im Grad 4 Scheitelpunkt-Situation beschrieben ist, die Konfiguration, die aus einem einzelnen Scheitelpunkt etikettiert besteht als, Grad 4 in G zu haben. Als oben genügt es, um dass zu demonstrieren, wenn die Konfiguration entfernt wird und der restliche vierfarbige Graph, dann kann das Färben auf solche Art und Weise modifiziert werden, dass, wenn die Konfiguration wiederhinzugefügt wird, der vier-Färben-dazu ebenso erweitert werden kann. Eine Konfiguration, für die das möglich ist, wird eine reduzierbare Konfiguration genannt. Wenn mindestens eine von einer Reihe von Konfigurationen irgendwo in G vorkommen müssen, die untergehen, wird unvermeidlich genannt. Das Argument hat oben durch das Geben eines unvermeidlichen Satzes von fünf Konfigurationen (ein einzelner Scheitelpunkt mit dem Grad 1, ein einzelner Scheitelpunkt mit dem Grad 2..., ein einzelner Scheitelpunkt mit dem Grad 5) begonnen und ist dann fortgefahren zu zeigen, dass die ersten 4 reduzierbar sind; einen unvermeidlichen Satz von Konfigurationen auszustellen, wo jede Konfiguration im Satz reduzierbar ist, würde den Lehrsatz beweisen.

Weil G dreieckig ist, ist der Grad jedes Scheitelpunkts in einer Konfiguration bekannt, und alle zur Konfiguration inneren Ränder sind bekannt, die Zahl von Scheitelpunkten in G neben einer gegebenen Konfiguration wird befestigt, und ihnen wird bei einem Zyklus angeschlossen. Diese Scheitelpunkte bilden den Ring der Konfiguration; eine Konfiguration mit k Scheitelpunkten in seinem Ring ist eine K-Ringkonfiguration, und die Konfiguration zusammen mit seinem Ring wird die beringte Konfiguration genannt. Als in den einfachen Fällen oben kann man alle verschieden vier-colorings des Rings aufzählen; jedes Färben, das modifikationsfrei zu einem Färben der Konfiguration erweitert werden kann, wird am Anfang gut genannt. Zum Beispiel war die Konfiguration des einzelnen Scheitelpunkts oben mit 3 oder weniger Nachbarn am Anfang gut. Im Allgemeinen muss der Umgebungsgraph systematisch wiedergefärbt werden, um das Färben des Rings in ein gutes zu verwandeln, wie im Fall getan wurde, oben wo es 4 Nachbarn gab; für eine allgemeine Konfiguration mit einem größeren Ring verlangt das kompliziertere Techniken. Wegen der Vielzahl von des Rings vier-colorings verschiedenen ist das der primäre Schritt, der Computerhilfe verlangt.

Schließlich muss es, einen unvermeidlichen Satz von Konfigurationen zu identifizieren, die der Verminderung durch dieses Verfahren zugänglich sind. Die primäre Methode, die verwendet ist, um solch einen Satz zu entdecken, ist die Methode sich zu entladen. Die intuitive Idee-Unterliegen-Entladung soll den planaren Graphen als ein elektrisches Netz betrachten. Am Anfang positive und negative "elektrische Anklage" wird unter den Scheitelpunkten verteilt, so dass die Summe positiv ist.

Rufen Sie die Formel oben zurück:

Jeder Scheitelpunkt wird eine anfängliche Anklage von 6-deg (v) zugeteilt. Dann "überflutet" man die Anklage, indem man die Anklage von einem Scheitelpunkt bis seine benachbarten Scheitelpunkte gemäß einer Reihe von Regeln, dem sich entladenden Verfahren systematisch neu verteilt. Da Anklage bewahrt wird, haben einige Scheitelpunkte noch positive Anklage. Die Regeln schränken die Möglichkeiten für Konfigurationen von positiv beladenen Scheitelpunkten ein, so das Aufzählen aller dieser möglichen Konfigurationen gibt einen unvermeidlichen Satz.

Nicht weniger als ist ein Mitglied des unvermeidlichen Satzes nicht reduzierbar, das sich entladende Verfahren wird modifiziert, um ihn zu beseitigen (während man andere Konfigurationen einführt). Appels sich entladendes Endverfahren und Hakens war äußerst kompliziert und zusammen mit einer Beschreibung des resultierenden unvermeidlichen Konfigurationssatzes, hat ein 400-seitiges Volumen gefüllt, aber die Konfigurationen, die es erzeugt hat, konnten mechanisch überprüft werden, um reduzierbar zu sein. Das Überprüfen des Volumens, das die unvermeidliche Konfiguration beschreibt, hat gesetzt wurde durch die gleichrangige Rezension über eine Zeitdauer von mehreren Jahren getan.

Ein technisches Detail nicht besprochen hier, aber erforderlich, den Beweis zu vollenden, ist Immersion reducibility.

Falsche Widerlegungen

Der vier Farbenlehrsatz ist notorisch gewesen, für eine Vielzahl von falschen Beweisen und Widerlegungen in seiner langen Geschichte anzuziehen. Zuerst hat Die New York Times als Angelegenheit für die Politik abgelehnt, über den Appel-Haken Beweis zu berichten, fürchtend, dass der Beweis falsch wie diejenigen davor gezeigt würde. Einige angebliche Beweise, wie Kempe und Tait haben oben erwähnt, unter der öffentlichen genauen Untersuchung seit mehr als einem Jahrzehnt gestanden, bevor sie ausgestellt wurden. Aber noch viele wurden, authored durch Dilettanten, überhaupt nie veröffentlicht.

Allgemein, das einfachste, obwohl ungültig, versuchen Gegenbeispiele, ein Gebiet zu schaffen, das alle anderen Gebiete berührt. Das zwingt die restlichen Gebiete, mit nur drei Farben gefärbt zu werden. Weil der vier Farbenlehrsatz wahr ist, ist das immer möglich; jedoch, weil die Person, die die Karte zieht, auf ein großes Gebiet eingestellt wird, scheitert er zu bemerken, dass die restlichen Gebiete tatsächlich mit drei Farben gefärbt werden können.

Dieser Trick kann verallgemeinert werden: Es gibt viele Karten, wo, wenn die Farben von einigen Gebieten im Voraus ausgewählt werden, es unmöglich wird, die restlichen Gebiete zu färben, ohne vier Farben zu überschreiten. Ein zufälliger verifier des Gegenbeispiels kann nicht denken, um die Farben dieser Gebiete zu ändern, so dass das Gegenbeispiel erscheinen wird, als ob es gültig ist.

Vielleicht ist eine Wirkung, die diesem häufigen Irrtum unterliegt, die Tatsache, dass die Farbenbeschränkung nicht transitiv ist: Ein Gebiet muss nur verschieden von Gebieten gefärbt werden, die es direkt, nicht Gebiete rührende Gebiete berührt, die es berührt. Wenn das die Beschränkung wäre, würden planare Graphen willkürlich große Anzahl von Farben verlangen.

Andere falsche Widerlegungen verletzen die Annahmen des Lehrsatzes auf unerwartete Weisen, wie das Verwenden eines Gebiets, das aus vielfachen getrennten Teilen oder zurückweisenden Gebieten derselben Farbe davon besteht, in einem Punkt anzulegen.

Generalisationen

Der vierfarbige Lehrsatz gilt nicht nur für begrenzte planare Graphen, sondern auch für unendliche Graphen, die ohne Überfahrten im Flugzeug, und noch mehr allgemein zu unendlichen Graphen gezogen werden können (vielleicht mit einer unzählbaren Zahl von Scheitelpunkten), für den jeder begrenzte Subgraph planar ist. Um das zu beweisen, kann man einen Beweis des Lehrsatzes für begrenzte planare Graphen mit dem Lehrsatz von De Bruijn-Erdős verbinden feststellend, dass, wenn jeder begrenzte Subgraph eines unendlichen Graphen k-colorable ist, dann ist der ganze Graph auch k-colorable.

Man kann auch das sich färbende Problem auf Oberflächen außer dem Flugzeug (Weisstein) denken. Das Problem auf dem Bereich oder Zylinder ist dazu auf dem Flugzeug gleichwertig. Für den geschlossenen (orientable oder non-orientable) Oberflächen mit der positiven Klasse hängt die maximale Nummer p von erforderlichen Farben von der Eigenschaft von Euler der Oberfläche χ gemäß der Formel ab

wo die äußersten Klammern die Fußboden-Funktion anzeigen.

Wechselweise für eine Orientable-Oberfläche kann die Formel in Bezug auf die Klasse einer Oberfläche, g gegeben werden:

:: (Weisstein).

Diese Formel, die Vermutung von Heawood, wurde von P.J. Heawood 1890 vermutet und von Gerhard Ringel und J. T. W. Youngs 1968 bewiesen. Die einzige Ausnahme zur Formel ist die Flasche von Klein, die Eigenschaft 0 von Euler hat (folglich, gibt die Formel p = 7), und verlangt 6 Farben, wie gezeigt, durch P. Franklin 1934 (Weisstein).

Zum Beispiel hat der Ring Eigenschaft von Euler χ = 0 (und Klasse g = 1) und so p = 7, so nicht mehr als sind 7 Farben erforderlich, jede Karte auf einem Ring zu färben. Das Szilassi Polyeder ist ein Beispiel, das sieben Farben verlangt.

Ein Möbius-Streifen verlangt auch sechs Farben (Weisstein).

Es gibt keine offensichtliche Erweiterung des sich färbenden Ergebnisses zu dreidimensionalen festen Gebieten. Indem man eine Reihe n flexibler Stangen verwendet, kann man dafür sorgen, dass jede Stange jede andere Stange berührt. Der Satz würde dann N-Farben oder n+1 verlangen, wenn Sie den leeren Raum denken, der auch jede Stange berührt. Die Nummer n kann genommen werden, um jede ganze Zahl, so groß zu sein, wie gewünscht. Solche Beispiele waren Fredrick Guthrie 1880 bekannt. Sogar für die Achse-Parallele cuboids (betrachtet, angrenzend zu sein, wenn zwei cuboids ein zweidimensionales Grenzgebiet teilen) kann eine unbegrenzte Zahl von Farben notwendig sein .

Siehe auch

Graph, der sich färbt

:the-Problem, optimalen colorings von Graphen zu finden, die nicht notwendigerweise planar sind.

Der Lehrsatz von Grötzsch

:triangle-freie planare Graphen sind 3-angeblich.

Problem von Hadwiger-Nelson

:how viele Farben sind erforderlich, um das Flugzeug zu färben, so dass keine zwei Punkte in der Einheitsentfernung einzeln dieselbe Farbe haben?

Liste von Sätzen von vier Ländern dass Grenze einander

:Contemporary-Beispiele von nationalen Karten, die vier Farben verlangen

Netz von Apollonian

Planare Graphen von:The, die vier Farben verlangen und genau einen vier-Färben-haben

Referenzen

Links