Glossar

Wähle eines der Schlüsselwörter auf der linken Seite…

Graphen und NetzwerkeKarten färben

Lesezeit: ~15 min

Wir haben die Graphentheorie bereits bei verschiedenen Landkarten angewendet. Wenn wir herauszoomen, verschwinden einzelne Straßen und Brücken und wir sehen stattdessen den Umriss ganzer Länder.

Beim Einfärben einer Karte - oder jeder anderen Zeichnung, die aus verschiedenen Regionen besteht - dürfen benachbarte Länder nicht die gleiche Farbe haben. Außerdem sollten wir so wenig verschiedene Farben wie möglich verwenden.

Einige einfache "Karten", wie ein Schachbrett, brauchen nur zwei Farben (schwarz und weiß), aber die meisten komplexeren Karten brauchen mehrere.

Wenn man die Karte der US-Bundesstaaten einfärbt, dann sind natürlich 50 Farben ausreichend, aber es sind weit weniger notwendig. Versuche die Karten unten mit so wenig Farben wie möglich einzufärben:

Vereinigte Staaten

0 verwendete Farben

Südamerika

0 verwendete Farben

Deutschland

0 verwendete Farben

England

0 verwendete Farben

Alle diese Karten können mit nur vier verschiedenen Farben eingefärbt werden, aber es ist nicht schwer, sich vorzustellen, dass andere, sehr komplizierte Karten viel mehr Farben benötigen. Tatsächlich brauchen manche Karten mindestens vier Farben, wenn sie vier Länder enthalten, die alle miteinander verbunden sind.

Wie zuvor können wir eine Karte mit Ländern und Grenzen in einen planaren Graphen umwandeln: jedes Land entspricht , und Länder, die werden durch eine Kante verbunden:

Jetzt wollen wir die Knoten eines Graphen einfärben, und zwei Knoten müssen eine andere Farbe haben, wenn sie durch eine Kante verbunden sind.

1852 musste der Botanikstudent Francis Guthrie eine Karte der Grafschaften in England ausmalen. Er bemerkte, dass vier Farben für jede Karte, die er ausprobierte, ausreichten, aber er konnte keinen Beweis dafür finden, dass das für alle Karten so ist. Dies stellte sich als äußerst schwieriges Problem heraus und wurde bekannt als Vier-Farben-Satz.

In den folgenden 100 Jahren veröffentlichten viele Mathematiker „Beweise“ für den Vier-Farben-Satz, nur um später Fehler zu finden. Einige dieser ungültigen Beweise waren so überzeugend, dass es mehr als 10 Jahre dauerte, um die Fehler zu entdecken.

Mathematiker konnten lange Zeit weder beweisen, dass vier Farben ausreichen, noch eine Karte finden, die mehr als vier Farben benötigte.

In Bezug auf das Vier-Farben-Problem wurden bis 1976 nur geringe Fortschritte erzielt, als Wolfgang Haken und Kenneth Appel einen Computer verwendeten, um es endgültig zu lösen. Sie reduzierten unendlich viele mögliche Karten auf 1936 Sonderfälle, die jeweils von einem Computer überprüft wurden, was insgesamt über 1000 Stunden in Anspruch nahm.

Der Vier-Farben-Satz ist der erste bekannte mathematische Satz, der mit Hilfe eines Computers bewiesen wurde, etwas, das inzwischen viel gebräuchlicher und weniger umstritten ist. Schnellere Computer und ein effizienterer Algorithmus tragen dazu bei, dass man heute den Vier-Farben-Satz auf einem Laptop in nur wenigen Stunden beweisen kann.

Stempel der mathematischen Fakultät der Universität von
Illinois Urbana-Champaign, wo Haken und Appel gearbeitet haben.
"Four colors suffice" bedeutet "Vier Farben reichen aus"

Der Vier-Farben-Satz funktioniert nur für Karten auf einer flachen Ebene oder einer Kugel, wobei alle Länder aus einem einzigen Gebiet bestehen.

Mathematiker haben sich aber auch Karten von Imperien angesehen, auf denen Länder aus mehreren nicht zusammenhängenden Gebieten bestehen können, und Karten auf unterschiedlich geformten Planeten, wie zum Beispiel einem Torus (Donutform). In diesen Fällen braucht man mehr als vier Farben, und die Beweise werden noch schwieriger.

Diese Karte auf einem Torus benötigt sieben Farben.