Der Vier-Farben-Satz

In der Mathematik gibt es viele schwere offene Probleme, die man nur nach einem Mathematikstudium verstehen kann. Es gibt aber auch Probleme die richtig schwer zu lösen sind, die aber jeder verstehen kann. Ein solches Problem ist der Vier-Farben-Satz. Er wurde von Neil Robertson, Daniel Sanders, Paul Seymour und Robin Thomas 1996 mit Hilfe eines Computers bewiesen. Hier also zunächst einmal der Satz:

Satz
Jeder planare Graph lässt sich zulässig mit vier Farben färben.

In dem Satz kommen einige Begriffe vor, die zunächst definiert werden müssen. Ein planarer Graph ist ein Graph, der ohne Kantenüberschneidungen in der Ebene gezeichnet werden kann. In der folgenden Abbildung ist ein planarer und ein nicht-planarer Graph zu sehen.

Die Knoten eines Graphen können wir mit verschiedenen Farben färben. Dabei heißt eine Färbung zulässig, wenn benachbarte Knoten verschiedene Farben haben. In der folgenden Abbildung ist ein zulässig gefärbter Graph zu sehen.

Bringt man jetzt diese beiden Begriffe zusammen, kommt man zur der Frage, wie viele Farben man braucht, damit man jeden planaren Graphen zulässig färben kann. Über die Jahre hinweg wurden viele Versuche unternommen die Vier-Farben-Vermutung zu beweisen. Entweder per direkten Beweis oder per Gegenbeweis (-beispiel). Es hätte nämlich ausgereicht, einen planaren Graphen anzugeben, für den man mindestens fünf Farben benötigt. Auch nach dem Beweis von Robertson et al. ist es noch interessant sich mit dem Vier-Farben-Satz zu beschäftigen, da ihr Beweis auf einer recht großen Fallunterscheidung (633 Fälle) beruht, die nur mit Computern überprüft werden können. Ein schöner, kurzer Beweis ohne Computerunterstützung fehlt immer noch.

Ursprünglich geht das Problem auf die Färbung von Landkarten zurück. Erstmal wurde die Frage von Francis Guthrie 1852 gestellt und später dann von Augustus De Morgan und William Rowan Hamilton ausführlich diskutiert.

Genügen vier oder weniger Farben, um die Länder einer Karte so zu färben, dass benachbarte Länder verschiedene Farben tragen?

Zu beachten ist, dass die Länder keine Exklaven haben dürfen, also nur aus einem zusammenhängenden Gebiet bestehen dürfen. Statt einer Landkarte kann man auch eine beliebige “Karte” in der euklidischen Ebene betrachten.

Von Inductiveload – Based on a this raster image by chas zzz brown on en.wikipedia., CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1680050

Um von der Landkarte zur Graphenfärbung zu kommen, zeichnet man in jedes Land der Karte einen Knoten und verbindet solche Knoten miteinander die in benachbarten Ländern sind. Der Graph der so entsteht ist planar. Eine zulässige Färbung dieses Graphen liefert eine zulässige Färbung der Karte und umgekehrt.

Von Inductiveload – Based on a this raster image by chas zzz brown on en.wikipedia., CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1680063

Die Eulersche Polyederformel

Bevor ihr euch daran macht, den Vier-Farben-Satz zu beweisen, möchte ich euch kurz einen (einfachen) Beweis des Fünf-Farben-Satzes zeigen. Er wurde 1890 von Percy Heawood bewiesen. Grundlage für den Beweis ist die Eulersche Polyederformel. Diese Formel gibt die Beziehung von Knoten, Kanten und Flächen in einem planaren Graphen an. Sei n die Anzahl der Knoten, m die Anzahl der Kanten und f die Anzahl der Flächen einer Einbettung  eines planaren Graphen, dann gilt:

\[n+f-m = 2\].

Der Graph in der vorherigen Abbildung hat 4 Knoten, 6 Kanten und 4 Flächen (die äußere Fläche zählt mit). Also gilt 4+4-6=2. Die Formel kann man relativ einfach per Induktion beweisen. Dazu beginnt man mit einem einzelnen Knoten. Für den gilt die Formel: 1+1-0=2. Jeder beliebige Graph kann aus diesem Startgraphen mit Hilfe der folgenden Operationen erzeugt werden:

  1. Hinzufügen eines Knotens der mit einer Kante mit dem bestehenden Graphen verbunden wird. Die Knoten- und Kantenzahl nimmt jeweils um Eins zu.
  2. Hinzufügen einer Kante. Die Anzahl der Kanten und Flächen steigt jeweils um Eins.

Auf dieser Seite gibt es eine Auswahl von 20 weiteren Beweisen um die Eulersche Polyederformel zu beweisen. Mit Hilfe dieser Formel kann man einige Aussagen für planare Graphen herleiten. In einem planaren Graphen wird eine Fläche von mindestens drei Kanten begrenzt und jede Kante grenzt an genau zwei Flächen. Es gilt somit:

\[3f \leq 2m\]

Stellt man die Formel jetzt nach f um, erhält man

\[f \leq \frac{2}{3}m\].

Setzt man diese Schranke in die Eulersche Polyederformel ein, erhält man eine Aussage über das Verhältnis von Knoten und Kanten in einem planaren Graphen:

\[2 = n+f-m <= n + \frac{2}{3}m – m =n – \frac{1}{3}m \].

Stellt man die Formel nach m um, erhält man:

\[m \leq 3n -6\].

Es gibt also in einem planaren Graphen höchstens 3n-6 Kanten.

Kommen wir jetzt zum Durchschnittsgrad eines Graphen. Der Grad eines Knoten ist die Anzahl der Kanten, die in diesem Knoten enden. Der Durchschnittsgrad d ist der Durchschnitt aller Knotengrade des Graphen oder einfach

\[d=\frac{2m}{n}\].

Setzen wir in diese Formel die Abschätzung für die Anzahl der Kanten in einem planaren Graphen ein, dann erhalten wir:

\[d=\frac{2m}{n}\leq\frac{6n-12}{n}<6\].

Der Durchschnittsgrad in einem planaren Graphen ist also immer kleiner als sechs. Daraus folgt, dass es in jedem planaren Graphen einen Knoten mit Grad kleiner gleich fünf geben muss. Diese Erkenntnis schafft die Voraussetzung für den Beweis des Fünf-Farben-Satzes.

Ein Beweis des Fünf-Farben-Satzes

Kommen wir also zum Beweis. Doch zunächst einmal der Satz:

Satz
Jeder planare Graph lässt sich zulässig mit fünf Farben färben.

Beweisen kann man den Satz mittels Induktion. Den Induktionsanfang bildet ein Graph mit einem Knoten. Er ist planar und kann mit fünf Farben zulässig gefärbt werden.

Jetzt geht man davon aus, dass der Satz auch für Graphen mit n-1 Knoten gilt und zeigt, dass er dann auch für Graphen mit n Knoten gültig ist.

Sei also G ein Graph mit n Knoten, dann besitzt dieser mindestens einen Knoten mit Knotengrad kleiner gleich fünf. Sei v ein Knoten mit Knotengrad kleiner fünf, dann ist der Graph G-v (ein Graph mit n-1 Knoten) zulässig mit fünf Farben färbbar.  Der Knoten v kann dann mit einer Farbe gefärbt werden, die keine seiner Nachbarn hat.

Gibt es keinen Knoten vom Grad kleiner fünf, dann muss es einen Knoten w vom Grad fünf geben. Der Graph G-w ist wieder mit fünf Farben zulässig färbbar. Sind bei dieser Färbung mindestens zwei Nachbarn von w in G gleich gefärbt, dann bleibt (mindestens) eine Farbe für w übrig und wir erhalten eine zulässige Färbung von G mit fünf Farben. Sind die Nachbarn von w in G alle verschieden gefärbt, dann haben wir zwei Fälle (sei \(N=\{w_1,\dots , w_5\}\) die Nachbarschaft von w im Uhrzeigersinn nummeriert):

  1. Es gibt keinen Weg zwischen \(w_1\) und \(w_3\) der nur die Farben der beiden Knoten verwendet und nicht über w führt. Wir können dann die Knoten des Weges so umfärben, dass \(w_1\) und \(w_3\) die selbe Farbe besitzen. Die Nachbarn von w sind also mit nur vier Farben gefärbt und es bleibt eine Farbe für w.

2. Es gibt einen solchen Weg zwischen \(w_1\) und \(w_3\). Dann kann es aber keinen solchen Weg zwischen \(w_2\) und \(w_4\) geben, der nur die Farben von \(w_2\) und \(w_4\) verwendet und nicht über w geht, da er (auf Grund der Planarität) den Weg zwischen  \(w_1\) und \(w_3\) schneiden würde und somit nicht nur die Farben von  \(w_2\) und \(w_4\) verwendet. Wir können also die Knoten \(w_2\) und \(w_4\) gleich färben. Die Situation ist in der folgenden Abbildung dargestellt.

Der Beweis funktioniert so natürlich nicht für den Vier-Farben-Satz. Ich finde aber, dass er relativ elegant ist und schon mal ein Gefühl für die Argumentation bei solchen Beweisen gibt.

Anwendungen

Eine der wohl verhasstesten Fragen an Mathematiker ist wohl die Frage nach der Anwendung, also was jetzt das Ergebnis mit einer “realen” Welt zu tun hat. Ich bin auch regelmäßig davon genervt, verstehe aber das Anliegen. Möchte aber auch betonen, dass es hier viel um die Schönheit und Eleganz von Beweisen geht und nicht zu sehr um die Anwendung. Ein Gemälde von Rembrandt oder Monet hat auch nur den Sinn, dass man sich an ihm erfreut und seine Schönheit genießt.

Aber gut, kommen wir zu Anwendung der ganzen Färberei. Neben der Anwendung “Landkarten färben”, die ich oben schon beschrieben habe, drehten Färbungen oft bei Optimierungsproblemen auf. Wenn wir zum Beispiel Mobilfunkfrequenzen so an Masten vergeben wollen, dass zwei Masten, deren Funkbereich sich überschneidet, auf verschiedenen Frequenzen senden, dann suchen wir eigentlich eine zulässige Färbung im zugrundeliegenden Graphen. Aber auch Stundenplanungsprobleme oder Fahrplanprobleme lassen sich auf Graphenfärbungen zurückführen.

Ich hoffe, ich konnte euch den Vier-Farben-Satz etwas näher bringen und bin schon gespannt auf eure Beweise!


Wie hat dir der Artikel gefallen? 1 Stern2 Sterne3 Sterne4 Sterne5 Sterne (Bisher keine Bewertungen)

Loading...

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Ich akzeptiere

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.