Vier-Farben-Satz
Das Vier-Farben-Problem ist die Frage, ob vier Farben immer ausreichen, um eine beliebige Landkarte so einzufärben, dass keine zwei angrenzenden Länder die gleiche Farbe haben.
(Ein gemeinsamer Punkt zählt nicht als Grenze.)
Dass dem so ist, wurde als erstes 1853 von Francis Guthrie als Vermutung veröffentlicht.
Es ist offensichtlich, dass drei Farben nicht ausreichen.
Mathematiker konnten beweisen, dass fünf Farben in jedem Fall ausreichen.
Ein Beweis für vier Farben konnte lange nicht gefunden werden.
Erst 1977 konnten Ken Appel und Wolfgang Haken einen solchen finden.
Der Beweis reduzierte die Anzahl der problematischen Fälle von Unendlich auf 1936 (eine spätere Version sogar 1476), 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.
Das Vier-Farben-Problem 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 besten mit Hilfe der Graphentheorie beschreiben.
Man sucht einen planaren Graphen, dessen Knoten mit maximal vier Farben gefärbt werden können, so daß keine benachbarten Knoten die gleiche Farbe haben.
Oder kürzer: "Ist jeder planare Graph vierfärbbar?"
Dabei wird jedem Land der Karte genau ein Knoten zugewiesen und zwei Knoten, deren Länder angrenzen, verbunden.
Bemerkung:
Wenn (so wie in der Realität öfters der Fall) ein Land auf mehrere nicht-angrenzende Gebiete verteilt ist (Kolonien, Enklaven, ...), dann ist der zugehörige Graph nicht planar und es sind möglicherweise mehr als vier Farben zur Färbung notwendig.
ein neuer beweis für das vier-farben-problem.
zunächst einmal die grundstruktur unseres beweises. wir stellen uns
einfach die menge aller tatsächlichen lösungen vor und unterteilen diese in
zwei gruppen von denen die erste eine bestimmte eigenschaft(E1) hat während
wir für unseren beweis ein bestimmte zweite eigenschaft(E2) brauchen.
sollte nun in der ersten gruppe E2 nicht auftauchen so liefert gerade dies
uns den grund dass sie ganz bestimmt in der anderen gruppe zu finden ist.
wir zeigen also dass wenn die lösung nicht in der ersten gruppe vorkommt
gerade dies der beweis ist dass sie in der zweiten existiert.
E1 und E2 nun sind dadurch bedingt dass man die länder nicht mehr mit vier
farben einfärbt sondern nur noch mit zwei (sagen wir F1 und F2) wobei die
länder die die gleiche farbe haben ketten und zweige (also bäume) bilden
dürfen aber niemals geschlossene ringe. das heisst also dass von drei ländern
die ein dreieck bilden nur zwei F1 (bzw. F2) sein können während das dritte
die komplementärfarbe haben muss. das heisst weiter dass wenn ich von einem
F1-land ausgehe und auf irgendein anderes angrenzendes F1-land überwechsle
(jedoch nicht auf das unmittelbar davor verlassene) ich in kein land mehr komme
wo ich schon einmal war wie oft auch immer ich diesen schritt wiederhole (bzw.
wiederholen kann). gleichzeitig bedeutet das dass ich jeweils von einem F1-
ursprungsland zu einem beliebigen anderen F1-land kommen kann denn nur dadurch
dass die F1-länder einen zusammenhang bilden können sie ja verhindern dass
die F2-länder einen ring bilden (und umgekehrt). diesen F1-(bzw. F2-)zusammen-
hang kann ich jetzt abwechselnd mit F1a und F1b (bzw. F2a und F2b) einfärben
so dass beispielsweise jeweils zwei F1a-länder durch ein F1b-land getrennt sind
und brauche so natürlich nie mehr als vier farben um die bedingung zu erfüllen
dass keine zwei aneinandergrenzenden länder die gleiche farbe haben.
wie brauchen also ein verfahren dass eine ringbildung zuverlässig verhindert
und so die bedingung erfüllt.
wir gehen zunächst von einem einzigen land aus dass wir uns so gross denken
wie alle länder zusammen die eine beliebige länderkombination bilden mögen.
das heisst wir können durch entsprechende abtrennung (also aufteilung und
umfärbung) aus einem land jede beliebige länderkombination bilden.
dabei gehen wir schrittweise vor. wir nennen unser ursprungsland |1| und
trennen zunächst einmal |2| ab. dadurch wird |1| zwar kleiner und ändert seine
form aber wie der leser wahrscheinlich schon längst weiss oder zumindest ahnt
kommt es hierauf überhaupt nicht an sondern allein auf die rein topologischen
beziehungen. so können wir also |1| und |2| ohne rücksicht auf ihr aussehen
und ihren grenzverlauf immer mit F1 und F2 einfärben so wie bei einem weiteren
abgetrennten |3| und |4| die farben F1a F1b F2a F2b ausreichend sind wobei wir
auch keine richtigen farben brauchen sondern blosse benennungen genügen.
genauso können wir den sonderfall dass zwei oder mehrere länder nur einen
punkt gemeinsam haben (was die färbung (oder benennung) vereinfachen würde da
diese länder alle die gleiche farbe haben dürfen) dadurch aufheben dass wir die
punktgrenze in einer beliebigen richtung um mindestens einen punkt erweitern.
und den ebenso vereinfachenden sonderfall dass ein oder zwei länder ein weiteres
völlig einschliessen können wir dadurch aufheben dass wir die fehlenden ein
oder zwei länder dazuerfinden so dass jedes land von mindestens drei ländern
eingeschlossen wird (die topologischen bedingungen auf die es uns ankommt
bleiben dabei erhalten).
topologisch gesehen gilt also bei vier ländern für jedes land (also auch für
|1|) dass es von den drei anderen eingeschlossen ist. ich habe noch vergessen
zu sagen dass jedes neue land das wir abtrennen von |1| abgetrennt wird
was man sich dadurch anschaulich machen kann dass man |1| immer als die
zusammenfassung aller noch nicht abgetrennten länder definiert. so ist es
auch völlig ausreichend nur |1| und seine unmittelbaren nachbarn zu betrachten
und zu zeigen dass man diese nachbarn immer so färben kann dass bei einem
beliebig abgetrennten neuen land der farbzusammenhang zu dem |1| gehört (im
folgenden immer F1) um ein glied erweitert wird ohne dass ein F1-ring entstehen
kann. diesen vorgang können wir nun auf grund der allgemeingültigkeit des verfah-
rens beliebig oft wiederholen was zu einer vollständigen induktionskette führt.
nun ist es ja so dass bei einem neu abgetrennten land (nennen wir es N)
immer zwei länder der nachberschaftskette (nennen wir sie L und R (für links
und rechts)) sowohl mit |1| als auch mit N verbunden bleiben (d.h. eine
gemeinsame grenze haben) während die zwischen L und R liegenden länder der
kette (falls vorhanden) zur abtrennunggsseite hin von N übernommen werden (zu
dessen nachbarschaftskette zählen). gehören nun L und R dem F2-zusammenhang an
während |1| ja zu F1 gehört so ist unmittelbar einsichtig dass wie oben schon
gesagt F1 durch N um ein glied erweitert werden kann ohne dass ein F1-ring
entsteht da bei der neu entstandenen verbindung |1|-N keine seiteneffekte
auftreten also alle übrigen länder ihre färbung und ihre (topologische)
färbungsumgebung behalten. d.h. wenn vorher kein farbring da war ist auch jetzt
keiner da. und hier kommen wir schon zu den oben erwähnten eigenschaften:
E1 := wenn wir |1| als F1 voraussetzen können wir für irgend ein L immer F2
erzwingen indem wir einen unmittelbaren nachbarn NB von |1| und L als F1 färben
(indem wir ihn wie oben beschrieben als das zuletzt hinzugekommene N ansehen).
(es sei hier noch einmal an die grundstruktur unseres beweises erinnert der
eine lösungsgruppe durch E1 definiert. somit handelt es sich dabei um alle
lösungen bei denen |1| und NB dem F1-zusammenhang angehören wodurch L
automatisch zu F2 gehört.)
E2 := können wir in entweder der einen oder der anderen lösungsgruppe immer
eine lösung finden bei der für ein beliebig gewähltes L und R beide F2 sind
dann können wir auch jede beliebige länderkombination erzeugen.
man kann das alles leichter nachvollziehen wenn man sich statt der länder
kleine kreise denkt (sozusagen die schwerpunkte der länder) und für jeweils
zwei länder die eine gemeinsame grenze haben die entsprechenden kreise mit
einer linie verbindet wobei sich keine zwei linien kreuzen dürfen. man erhält
dann eine entsprechende kombination von dreiecken (natürlich nur topolologisch)
deren eckpunkte eben die kleinen kreise bilden die man dann weiss (was F1
entsprechen soll) oder schwarz (entspricht F2) einfärben kann. wir betrachten
auch hier nur |1| rings umgeben von seinen direkten nachbarn die mit ihm wie
ein radkranz durch speichen mit der nabe verbunden sind.
unsere anfängliche 4-länderkombination können wir uns jetzt als ein auf eine
fläche abgebildetes tetraeder vorstellen welches nur aus kanten und eckpunkten
besteht wobei die eckpunkte alle als kleine kreise dargestellt sind.
2_________ 3
|\ /|
| \ / |
| \ / |
| 1 |
\ | /
\ | /
\ | /
\|/
4
wenn wir uns fragen welcher der |1|-nachbarn das zuletzt hinzugekommene N
ist wird klar dass es jeder sein kann denn wenn wir bei irgendeinem die
abtrennung (die ja hier ein herausziehen ist) wieder umkehren (ihn also nach
|1| hineinziehen) entsteht eine reale n minus 1 länderkombination und diesen
vorgang kann man bis zurück zu 1 wiederholen. folglich kann jeder nachbar
(natürlich nicht alle zugleich) dem farbzusammenhang von |1| (hier weiss)
angehören was wiederum bedeutet dass die rechts und links von ihm liegenden
nachbarn dem komplementärzusammenhang angehören (um gleichfarbige dreiecke zu
vermeiden).
bei unserer 4-länderkombination ist es allein schon auf grund der völligen
symmetrie klar dass jeder der drei nachbarn von |1| N sein kann während die
links und rechts von ihm liegenden länder L und R sind. somit ist hier also E2
unmittelbar erfüllt: jeweils zwei beliebige nachbarn von |1| können als L und
R fungieren. damit habe ich 6 möglichkeiten ein neues N oder |5| zu erzeugen
die ich hier der anschaulichkeit wegen einzeln anführe wobei das jeweils links
stehende land als L und das jeweils rechts stehende als R fungiert:
|2|-|3| |2|-|4| |3|-|4| |3|-|4|-|2| |4|-|3|-|2| |4|-|2|-|3|.
dies ist nun die menge aller tatsächlich möglichen topologischen konstruktionen
und damit leider auch schon die lösung unseres problems denn da E2 offensicht-
lich immer erfüllt ist muss E1 gar nicht mehr in anspruch genommen werden.
und das ist auch kein zufall denn wir haben es hier nur mit teilketten zu tun
die aus zwei oder drei gliedern bestehen. und wenn bei drei gliedern das mittlere
NB und also weiß ist müssen L und R schwarz sein weil sie sich ja im dreieck
mit |1| und NB befinden. bei nur zwei gliedern gehen wir vermittels einer
schöpferischen anwendung von E1 einfach davon aus dass L hier als |1| fungiert
und R als NB wobei das ursprüngliche |1| die rolle von R übernimmt. damit ist
sofort klar dass das neue |1| und das neue N die gleiche farbe haben dürfen
und somit haben auch bei einer zurückbenennung L und R die gleiche farbe.
verlassen wir jetzt den konkreten einzelfall und kommen wir zur alles
entscheidenden abstraktion. wir stellen uns für eine beliebig gewählte länder-
kombination die menge aller tatsächlichen lösungen vor und unterteilen diese in
zwei gruppen von denen die erste durch E1 bestimmt ist also |1| und NB weiß
sind und damit L schwarz ist.
jetzt suchen wir in dieser gruppe nach einer lösung bei der R ebenfalls
schwarz ist. haben wir erfolg dann ist E2 erfüllt und wir können ein neues N
erzeugen. haben wir aber hier keinen erfolg dann bedeutet das dass das von uns
auf weiss gesetzte NB immer ein ebenfalls weisses R erzwingt. das bedeutet aber
dass wenn der eine weiss ist nur dann ein farbring verhindert werden kann
wenn auch der andere weiss ist da wir nicht sagen können wer zuerst da war
das weisse NB oder das weisse R. folglich gilt umgekehrt: ein weisses R erzwingt
ein weisses NB.
folglich sind beide entweder weiss oder schwarz (die denknotwendigkeit
auf welcher der ganze beweis beruht ist somit die umkehrbarkeit einer ein-
deutigen wirkung in einem gebilde in dem von natur aus (von der struktur her)
keine richtung bevorzugt wird).
der rest ist ein kinderspiel. da eine verschiedene färbung der beiden letzge-
nannten felder ausscheidet brauchen wir nur noch zu beweisen dass es eine
lösung gibt (nun natürlich in der restgruppe) bei der eines dieser felder
schwarz ist (|1| immer als weiss vorausgesetzt). nun haben wir ja schon
gezeigt dass eine zweigliedrige teilkette immer die komplementärfarbe von
|1| annehmen kann und L und NB sind eine solche teilkette. folglich werden wir
in der zweiten gruppe erfolg haben.
(ich hätte sagt man mir den letzten absatz etwas unzulässig formuliert.
ein bisschen spass muss sein.)
/Diskussion