4-Farben-Satz

Einleitung

Der 4-Farben-Satz besagt, dass man in jedem planaren Graphen die Knoten mit 4 Farben färben kann, ohne dass eine Kante an beiden Endknoten die gleiche Farbe hat.

Viel anschaulicher bedeutet das, dass man jede Landkarte, egal welche Form und Anordnung die Länder haben, mit 4 Farben färben kann, ohne dass zwei benachbarte Länder (also zwei Länder, die sich eine Grenze teilen) die gleiche Farbe haben.

"4-Colorizer"

Dieses Beispiel wurde von unserem selbstgeschriebenen Programm eingefärbt.

Im Rahmen des Projektes haben wir ein interaktives Programm entwickelt, das einen gegebenen Graphen mit nur vier Farben einfärben kann.

Zeichnet man eine Karte (wie z.B. rechts zu sehen) in das Rechteck, so wird es automatisch mit lediglich vier Farben so eingefärbt, dass keine zwei benachbarten Felder die gleiche Farbe besitzen.

Bei der Berechnung des dualen Graphen treten allerdings momentan noch kleinere Fehler auf.

Graphentheorie Crash Course

Ein Graph besteht aus Knoten und Kanten. Eine Kante verbindet jeweils zwei Knoten. Mit Hilfe dieses mathematischen Konstruktes können zum Beispiel auch verschiedene Situationen aus der echten Welt repräsentiert werden, beispielsweise können Knoten für Länder stehen und Kanten für Grenzen zwischen Ländern (sodass genau dann eine Kante zwischen zwei Ländern existiert, wenn diese benachbart sind).

Ein planarer Graph ist nun ein Graph, der in einer 2-dimensionalen Ebene, mit Punkten als Knoten und Linien als Kanten, gezeichnet werden kann, ohne dass sich zwei Kanten schneiden. Dies ist für das Landkarten-Problem auf jeden Fall erfüllt, da man die Länder durch Punkte und die Ländergrenzen durch Linien zwischen den Punkten ersetzten kann, sodass man einen Graphen erhält, wo sich keine Linien überschneiden müssen, da sich unterschiedliche Ländergrenzen auch nicht überschneiden können. Die Bundesländer würden allerdings einen Sonderfall auf Grund der Exklave von Bremen, Bremerhaven, darstellen.

Der Grad eines Knotens gibt an, mit wie vielen anderen Knoten er durch Kanten direkt verbunden ist. Ein Knoten mit zwei Nachbarknoten ist also vom Grad zwei.

5-Farben-Satz

Der 5-Farben Satz ist der kleine langweilige Bruder des 4-Farben Satzes. Er besagt, dass man die Knoten eines planaren Graphen mit 5 Farben färben kann, ohne dass zwei Knoten, die durch eine Kante direkt miteinander verbunden sind, die gleiche Farbe haben. Also einfach wie der 4-Farben Satz nur mit 5 Farben. Offensichtlich impliziert der 4-Farben Satz den 5-Farben Satz.

Dafür kann man den 5-Farben Satz verständlich beweisen (und der Beweis ist schön). Für Informationen über den Beweis vom 4-Farben Satz siehe nächsten Abschnitt.

Beweis des 5-Farben-Satzes

Der Beweis ist deutlich einfacher zu verstehen, wenn man ihn graphisch präsentiert bekommt, wie beispielsweise in diesem Video.

Im Folgenden bezeichne '5-färbbar', dass man die Knoten eines Graphen mit 5 Farben färben kann, sodass keine zwei Knoten, die durch eine Kante verbunden sind, die gleiche Farbe haben.

Der Satz wird durch vollständige Induktion bewiesen:

Induktionsanfang: Offensichtlich ist ein Graph mit einem Knoten mit 5-färbbar.

Induktionsschritt: Es wird gezeigt, dass, wenn jeder planare Graph mit n-1 Knoten 5-färbbar ist, auch jeder planare Graph mit n Knoten 5-färbbar ist.

Jeder planare Graph enthält einen Knoten von Grad maximal 5, das heißt es gibt einen Knoten mit maximal 5 Nachbarknoten. Dies folgt aus einer einfachen Umformung der eulerschen Polyederformel. Diese besagt, dass in einem planaren Graphen die Summe aus der Anzahl der Ecken und der der Flächen subtrahiert der Anzahl der Kanten immer zwei ergibt: E - K + F = 2.

Nun können wir folgende zwei Fälle separat betrachten:

Fall 1: Es gibt einen Knoten vom Grad maximal 4, das heißt alle Knoten haben mindestens fünf Nachbarknoten. Da der Graph ohne diesen Knoten nach der Induktionsannahme 5-färbbar ist, können wir die Färbung dieses Graphen einfach für den Graph mit dem Knoten übernehmen und den Knoten in einer Farbe färben, die kein Nachbarknoten von dem Knoten hat. Da es 5 Farben und nur maximal 4 Nachbarknoten gibt, existiert eine solche Farbe.

Fall 2: Es gibt keinen Knoten vom Grad maximal 4. Wie oben schon beschrieben, gibt es jedoch einen Knoten mit maximal 5 Nachbarknoten. Sei dieser Knoten der Knoten w. Nach Induktionsannahme ist der Graph ohne w 5-färbbar. Hier gibt es wieder 2 Fälle zu unterscheiden:

Fall 2.1: Die Nachbarknoten von w sind nur mit maximal 4 unterschiedlichen Farben gefärbt. In diesem Fall können wir w einfach mit einer Farbe färben, mit der kein Nachbarknoten gefärbt ist.

Fall 2.1

Fall 2.2: Die 5 Nachbarknoten sind mit 5 unterschiedlichen Farben gefärbt. Wir bezeichnen die Nachbarknoten von w als w1, w2, ..., w5 im Uhrzeigersinn. Nun überprüfen wir, ob es einen Weg von w1 nach w3 gibt, der nicht über den Knoten w geht, sodass die Knoten auf diesem Weg nur mit den Farben von w1 und w3 gefärbt sind.

Fall 2.2.1: Nein, es existiert kein solcher Weg. Dann wird der Knoten w auf die Farbe von w3 und w3 auf die Farbe von w1 umgefärbt. Die Nachbarknoten von w3 mit der Farbe von w1 werden dann auf die ursprüngliche Farbe von w3 umgefärbt und die Nachbarknoten von diesen Knoten mit der ursprünglichen Farbe von w3 wieder auf die Farbe von w1 umgefärbt und so weiter, bis alle Wege in w1/w3-Farben von w ausgehend umgefärbt sind. Der resultierende Graph ist nun mit 5 Farben so gefärbt, dass keine zwei Knoten, die durch eine Kante direkt verbunden sind, die gleiche Farbe haben.

Fall 2.2.1

Fall 2.2.2: Ja, ein solcher Weg existiert. Da der Graph planar ist, kann es keinen Weg mit von w2 zu w4 geben, der nicht über w geht, sodass alle Knoten des Weges nur mit den Farben von w2 und w4 gefärbt sind, da ein solcher Weg unweigerlich durch einen Knoten auf dem beschriebenen Weg zwischen w1 und w3 gehen müsste, der ja entweder die Farbe von w1 oder w3 hat. Daher können wir nun den Knoten w mit der Farbe von w2 färben, den Knoten w2 mit der Farbe von w4, die Nachbarknoten von w2, die die Farbe von w4 haben mit der ursprünglichen Farbe von w2 färben, und so weiter, sodass der resultierende Graph wie gewünscht 5-gefärbbt ist. (Wie bei Fall 2.2.1, nur mit w2 und w4 anstatt mit w1 und w3.)

Fall 2.2.2: Der braun-gestrichelte Weg soll aufzeigen, dass es nicht möglich ist, dass ein Pfad von w2 nach w4 existiert, dessen Knoten nur mit den Farben lila und blau gefärbt sind, da der rot-grüne Pfad im Weg ist.

4-Farben-Satz

Der 4-Farben-Satz wurde 1852 erstmals von dem südafrikanischen Mathematiker Francis Guthrie als Vermutung aufgestellt. Bereits im 19. Jahrhundert wurden einige vermeintliche Beweise dieses Satzes aufgestellt, jedoch stellten sich alle Versuche im Nachhinein als inkorrekt heraus.[1]

Erst 1976 verkündeten Kenneth Appel und Wolfgang Hagen der University of Illinois, dass es ihnen gelang, den Satz durch einen computergestützten Beweis zu zeigen. Der Beweis widerlegte, dass es eine minimale Anzahl an Flächen gibt, sodass der Graph nicht mehr vierfärbbar wäre, indem die unendliche Menge von Graphen auf 1834 (später auf 633) relevante Möglichkeiten vereinfacht wurde, die dann einzeln mit Hilfe eines Computers überprüft wurden.[2]

Dies war der erste computergestützte Beweis dieser Art.[3]

Autoren

Simon Skade und Fynn Kiwitt