Stichpunkte

Allgemein
	Der Vier-Farben-Satz (früher auch als Vier-Farben-Vermutung oder Vier-Farben-Problem bekannt) der Graphentheorie
	Topologie bzw
	dass keine zwei angrenzenden Länder die gleiche Farbe bekommen
	Kartographie besagt
	dass vier Farben immer ausreichen
	um eine beliebige Landkarte so einzufärben
	dass ein gemeinsamer Punkt nicht als "Grenze" zählt und jedes Land aus einer zusammenhängenden Fläche besteht
	also keine Enklaven bzw
	Dies gilt unter den Einschränkungen
	Exklaven vorhanden sind
	Der Satz wurde erstmals 1853 von Francis Guthrie als Vermutung veröffentlicht
	dass drei Farben nicht ausreichen
	Es ist offensichtlich
	dass fünf Farben in jedem Fall ausreichen
	Mathematiker konnten beweisen
	Ein Beweis für vier Farben konnte lange nicht gefunden werden. Heinrich Heesch entwickelte in den 1960er und 70er Jahren Verfahren
	um einen Beweis mithilfe des Computers zu suchen
	Darauf aufbauend konnten Ken Appel und Wolfgang Haken 1977 einen solchen finden
	die durch einen Computer einzeln geprüft wurden
	Der Beweis reduzierte die Anzahl der problematischen Fälle von Unendlich auf 1.936 (eine spätere Version sogar 1.476)
	Paul Seymour und Robin Thomas einen modifizierten Beweis finden
	1996 konnten Neil Robertson
	Daniel Sanders
	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!"). [Bearbeiten]
Formale Formulierung
	dass keine benachbarten Knoten die gleiche Farbe tragen
	Bild nicht gefunden Darstellung der Formulierung in der Graphentheorie 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
	verbunden
	deren Länder angrenzen
	Oder kürzer: "Ist jeder planare Graph 4-färbbar?" Dabei wird jedem Land der Karte genau ein Knoten zugewiesen und zwei Knoten
	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)
	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)
	Das klassische Vier-Farben-Problem betrifft Landkarten
	die Projektive Ebene (6 Farben) und den Torus (7 Farben). [Bearbeiten]
Bemerkung
	Enklaven
	Exklaven
	Wenn (so wie in der Realität häufig der Fall) ein Land auf mehrere nicht-angrenzende Gebiete verteilt ist (Kolonien
	...)
	dann ist der zugehörige Graph nicht notwendigerweise planar und es sind möglicherweise mehr als vier Farben zur Färbung notwendig. [Bearbeiten]
Literatur
	Kenneth Appel and Wolfgang Haken
	Every Planar Map is Four Colorable
	Contemp
	vol
	Math.
	Amer
	98
	Math
	Soc.
	Providence
	Seymour und Thomas (http://www.math.gatech.edu/~thomas/FC/fourcolor.html) en:Four color theorem it:Teorema dei quattro colori ja:四色定� nl:Vierkleurenstelling pt:Teorema das quatro cores sv:Fyrfärgssatsen zh:四色定�
	1989. Beweis von Robertson
	Sanders
	RI

Dieser Artikel basiert auf dem Artikel Vier-Farben-Satz aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.