Zur MathePrisma-Startseite
Zur Modul-Startseite  


Das Vierfarbenproblem (Backtracking 3)
 

 
 

 
Bei der Wahl der Farbe für ein neues Land müssen mindestens zwei Bedingungen erfüllt sein:
 
Bedingung 1:
 
Das neu gefärbte Land grenzt an kein bereits früher gefärbtes Land mit der gleichen Farbe.
 

 
Beispiel 1:

                                          

Bedingung 1 ist verletzt.
 
Bedingung 2:
 
Durch die Färbung des neuen Landes wird kein angrenzendes, noch nicht gefärbtes Land unfärbbar.
 
























notwendige Bedingung
 

Beispiel 2:

                                          

Bedingung 2 ist verletzt. (Land 6 ist unfärbbar.)


Die Bedingungen 1 und 2 müssen zwingend erfüllt sein, damit die Karte korrekt eingefärbt wird. Man bezeichnet sie auch als notwendige Bedingungen.

Die Bedingungen 1 und 2 analysieren nur die Situation für die direkt angrenzenden Länder. Es kann durchaus vorkommen, dass die Entscheidung, ein Land mit einer bestimmten Farbe zu belegen, zwar den Bedingungen 1 und 2 genügt, man aber erst später feststellt, dass diese Entscheidung in eine "Sackgasse" führte.
Wir werden das später an einigen Beispielen sehen.
 
Seite 7/18