Vierfarben-Problem

Vierfarben-ProblemIm Jahre 1852 war der englische Mathematiker Francis Guthrie mit der Aufgabe beschäftigt, eine Karte mit den englischen Grafschaften zu kolorieren. Er bemühte sich, mit möglichst wenigen Farben auszukommen. Die Bedingung dabei war, dass benachbarte Länder farblich unterscheidbar sein sollten.

De Morgan gab eine Karte an, die zeigte, dass man mindestens vier Farben braucht. Da jedes Land an jedes andere angrenzt, braucht man zur Färbung vier Farben.

Daraus ergab sich die Frage:
Wie viele Farben reichen aus, um eine beliebige Karte so einzufärben, dass je zwei aneinandergrenzende Länder unterschiedliche Farben haben?

Dieses Problem konnte lange Zeit nicht gelöst werden. Erst 1976 gelang K. Appel und W. Haken mithilfe eines Computers der Beweis, dem viele Mathematiker jedoch sehr skeptisch gegenüber stehen, da der Beweis eine Rechenzeit von 1200 Stunden erforderte und für die meisten Mathematiker nicht nachprüfbar war.

In diesem Teilprogramm können Sie die Färbung von Karten durch den Computer durchführen lassen.

Dazu laden Sie zuerst über Bild laden eine Abbildung. Diese muss im Format GIF vorliegen und darf nur Schwarz und Weiß als Farben enthalten. Ein derartiges Bild können Sie zum Beispiel mit dem Windows-Programm PAINT zeichnen und dort als Monochrom-GIF-Bild speichern.
Alternativ können Sie auch eines der acht vordefinierten Bilder in der linken Liste auswählen.
Die Färbung der Karte erfolgt nun in mehreren Schritten:

  1. Über Gebiete ermitteln bestimmt das Programm wie viele weiße Gebiete mit schwarzem, geschlossenem Rand vorliegen.
  2. Der Schalter Grenze ermitteln sucht die exakte Lage der Grenzen zwischen den Gebieten.
  3. Färbung suchen füllt jedes Gebiet mit einer Farbe, sodass aneinandergrenzende Gebiete unterschiedliche Farben besitzen. Dabei können bis zu sieben Farben verwendet werden.
  4. Erst der Schalter Minimalfärbung sucht nach einer Färbung mit maximal vier Farben.

Beachten Sie bitte: Enthält die Karte viele Gebiete und viele Grenzen, so können die einzelnen Schritte auch auf schnellen Computern einige Zeit benötigen.

Beachte Sie bitte weiterhin:
Im Jahr 1975 veröffentlichte Martin Gardner unter dem Pseudonym W. McGregor eine aus 110 Ländern bestehende Landkarte von der er behauptete, zu ihrer Färbung benötige man mindestens 5 Farben, und damit sei die Vierfarbenvermutung widerlegt. Nach einiger Zeit wurde nachgewiesen, dass auch hier nur 4 Farben notwendig sind. Im Lexikon findet Sie unter dem Stichwort Vierfarbenproblem (2) eine Lösung.

Diese Karte können Sie auch auswählen. Das Programm findet auch eine Farbbelegung, allerdings mit 5 Farben. Bisher konnte das Programm noch keine 4-Farben-Lösung ermitteln, trotz sehr langer Rechenzeit.