Vier-Farben-Satz
Der Vier-Farben-Satz (früher auch als Vier-Farben-Vermutung oder Vier-Farben-Problem bekannt) der Graphentheorie, Topologie bzw. Kartografie besagt, dass vier Farben immer ausreichen, um eine beliebige Landkarte so einzufärben, dass keine zwei angrenzenden Länder die gleiche Farbe bekommen.
Dies gilt unter den Einschränkungen, dass ein gemeinsamer Punkt nicht als "Grenze" zählt und jedes Land aus einer zusammenhängenden Fläche besteht, also keine Enklaven bzw. Exklaven vorhanden sind.
| Inhaltsverzeichnis |
Geschichte
Der Satz wurde erstmals 1852 von Francis Guthrie als Vermutung angeregt, als er die counties von England färben wollte. Es war offensichtlich, dass drei Farben nicht ausreichten und man fünf in keinem konstruierten Beispiel brauchte. In einem Brief, vom 23. Oktober 1852, vom Londoner Mathematikprofessor Augustus De Morgan an den irischen Kollegen William Rowan Hamilton, wurde die Vermutung erstmals diskutiert und veröffentlicht: "Können die Länder einer Karte so gefärbt werden, dass vier oder weniger Farben genügen, so dass benachbarte Länder verschiedene Farben tragen?".
Der englische Mathematiker Arthur Cayley stellte das Problem 1878 der mathematischen Gesellschaft Londons vor. Innerhalb nur eines Jahres fand Alfred Kempe einen Beweis für den Satz. Elf Jahre später, 1890, zeigte Percy Heawood, dass Kempes Beweis fehlerhaft war. Ein zweiter fehlerhafter Beweis, 1880 von Peter Tait veröffentlicht, konnte ebenfalls elf Jahre lang nicht widerlegt werden. Erst 1891 zeigte Julius Petersen, dass auch Taits Beweis nicht korrekt war. Heawood gab im Jahre 1890 mit der Widerlegung von Kempes Vier-Farben-Beweis, zusätzlich einen Beweis für den Fünf-Farben-Satz an, womit eine obere Grenze für die Färbung von planaren Graphen, zum ersten Mal fehlerfrei bewiesen wurde. In Kempes fehlerhaftem Beweis steckten bereits grundlegende Ideen, die zum späteren Beweis durch Appel und Haken führten.
Heinrich Heesch entwickelte in den 1960er und 1970er Jahren Verfahren, um einen Beweis mithilfe des Computers zu suchen.
Darauf aufbauend konnten Ken Appel und Wolfgang Haken 1977 einen solchen finden. Der Beweis reduzierte die Anzahl der problematischen Fälle von Unendlich auf 1.936 (eine spätere Version sogar 1.476), die durch einen Computer einzeln geprüft wurden.
1996 konnten Neil Robertson, Daniel Sanders, Paul Seymour und Robin Thomas einen modifizierten Beweis finden, der die Fälle auf 633 reduzierte. Auch diese mussten per Computer geprüft werden.
Der Vier-Farben-Satz war das erste große mathematische Problem, das mit Hilfe von Computern gelöst wurde. Deshalb wurde der Beweis von einigen Mathematikern nicht anerkannt, da er nicht direkt durch einen Menschen nachvollzogen werden kann. Schließlich muss man sich auf die Korrektheit des Compilers und der Hardware verlassen. Auch die mathematische Eleganz des Beweises wurde kritisiert ("Ein guter Beweis liest sich wie ein Gedicht - dieser sieht aus wie ein Telefonbuch!").
Formale Formulierung
Formal lässt sich das Problem am einfachsten mit Hilfe der Graphentheorie beschreiben. Man fragt ob die Knoten jedes planaren Graphen mit maximal vier Farben so gefärbt werden können, dass keine benachbarten Knoten die gleiche Farbe tragen. Oder kürzer: "Ist jeder planare Graph 4-färbbar?" Dabei wird jedem Land der Karte genau ein Knoten zugewiesen und zwei Knoten, deren Länder angrenzen, verbunden.
Das Vier-Farben-Problem ist ein Spezialfall der Heawood-Vermutung, die seit ihrem Beweis im Jahre 1968 "Theorem von Ringel-Youngs" heißt (s. englische Version). Das klassische Vier-Farben-Problem betrifft Landkarten, die auf einer Ebene oder Kugeloberfläche liegen. Die 'Heawood-Vermutung' stellt das analoge Problem für allgemeine Oberflächen, etwa die Kleinsche Flasche (6 Farben), das Möbiusband (6 Farben), die Projektive Ebene (6 Farben) und den Torus (7 Farben).
Bemerkung
Wenn (so wie in der Realität häufig der Fall) ein Land auf mehrere nicht-angrenzende Gebiete verteilt ist (Kolonien, Enklaven, Exklaven, ...), dann ist der zugehörige Graph nicht notwendigerweise planar und es sind möglicherweise mehr als vier Farben zur Färbung notwendig.
Literatur
- Kenneth Appel and Wolfgang Haken, Every Planar Map is Four Colorable, Contemp. Math., vol. 98, Amer. Math. Soc., Providence, RI, 1989.
- Beweis von Robertson, Sanders, Seymour und Thomas
- George Spencer-Brown, "Laws of Form", Appendix 5. Two proofs of the four-colour map theorem