Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 25. Juni 2019 

Vier-Farben-Satz


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Der Vier-Farben-Satz (früher auch als Vier-Farben-Vermutung oder Vier-Farben-Problem bekannt) der Graphentheorie Topologie bzw. Kartographie besagt dass vier Farben immer ausreichen eine beliebige Landkarte so einzufärben dass keine angrenzenden Länder die gleiche Farbe bekommen. Dies unter den Einschränkungen dass ein gemeinsamer Punkt als "Grenze" zählt und jedes Land aus zusammenhängenden Fläche besteht also keine Enklaven bzw. Exklaven vorhanden sind.

Der Satz wurde erstmals 1853 von Francis Guthrie als Vermutung veröffentlicht. ist offensichtlich dass drei Farben nicht ausreichen. konnten beweisen dass fünf Farben in jedem ausreichen. Ein Beweis für vier Farben konnte nicht gefunden werden.

Erst 1977 konnten Ken Appel und Wolfgang Haken solchen finden. Der Beweis reduzierte die Anzahl problematischen Fälle von Unendlich auf 1936 (eine Version sogar 1476) die durch einen Computer einzeln geprüft wurden.

1996 konnten Neil Robertson Daniel Sanders Paul und Robin Thomas einen modifizierten Beweis finden die Fälle auf 633 reduzierte. Auch diese per Computer geprüft werden.

Der Vier-Farben-Satz war das erste große Problem das mit Hilfe von Computern gelöst Deshalb wurde der Beweis von einigen Mathematikern anerkannt da er nicht direkt durch einen nachvollzogen werden kann. Schließlich muss man sich die Korrektheit des Compilers und der Hardware verlassen. Auch die mathematische Eleganz des wurde kritisiert ("Ein guter Beweis liest sich ein Gedicht - dieser sieht aus wie Telefonbuch!").

Formale Formulierung

Formal lässt sich das Problem am mit Hilfe der Graphentheorie beschreiben. Man fragt die Knoten jedes planaren Graphen mit maximal vier Farben so gefärbt können dass keine benachbarten Knoten die gleiche tragen. Oder kürzer: "Ist jeder planare Graph 4-färbbar ?" Dabei wird jedem Land der Karte ein Knoten zugewiesen und zwei Knoten deren angrenzen verbunden.

Das Vier-Farben-Problem ist ein Spezialfall der Heawood-Vermutung die seit ihrem Beweis im Jahre "Theorem von Ringel-Youngs" heißt (s. englische Version). klassische Vier-Farben-Problem betrifft Landkarten die auf einer oder Kugeloberfläche liegen. Die 'Heawood-Vermutung' stellt das Problem für allgemeine Oberflächen etwa die Kleinsche Flasche (6 Farben) das Möbiusband (6 Farben) die Projektive Ebene (6 und den Torus (7 Farben).

Bemerkung

Wenn (so wie in der Realität der Fall) ein Land auf mehrere nicht-angrenzende verteilt ist ( Kolonien Enklaven ...) dann ist der zugehörige Graph planar und es sind möglicherweise mehr als Farben zur Färbung notwendig.

Literatur

  • Kenneth Appel and Wolfgang Haken Every Planar Map is Four Colorable Contemp. Math. vol. 98 Amer. Math. Providence RI 1989.



Bücher zum Thema Vier-Farben-Satz

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Vier-Farben-Satz.html">Vier-Farben-Satz </a>