Zur MathePrisma-Startseite
Zur Modul-Startseite  


Das Vierfarbenproblem (Durchsuchen)
 

 
 

 
Eine naheliegende systematische Methode ist, nacheinander einfach alle Färbungszustände durchzuprobieren und für jeden einzelnen zu überprüfen, ob die Karte korrekt koloriert ist. Man nennt diese Strategie auch erschöpfendes Durchsuchen.

Für diese Strategie brauchen wir eine Methode, die uns nacheinander alle möglichen Färbungszustände liefert. Dazu benutzen wir einen Zähler wie den Tachometer im Auto:
Jedem Tachostand entspricht ein Färbungszustand. Durch Weiterzählen im Tachometer erzeugt man also alle möglichen Färbungszustände. Bei einem Tachometer mit fünf Stellen starten wir mit 00000.
 

 
  • Jede Stelle in der Tacho-Anzeige ist einem Land in der Karte zugeordnet.
  • Die Ziffern 0, 1, 2 und 3 repräsentieren die Farben grün, blau, rot und gelb, d.h. die Farben werden folgendermaßen durch vier Ziffern codiert: 0=grün, 1=blau, 2=rot, 3=gelb.

     

     

    Jedem Land wird eine Tachostelle zugeordnet.
    Das erste Land färben wir gelb. Im Tacho erscheint für gelb die Ziffer 3.
    Das zweite Land färben wir grün.
    Das dritte Land färben wir rot.
    Das vierte Land färben wir blau.
    Das letzte Land färben wir grün.

 





0 = grün
1 = blau
2 = rot
3 = gelb

 
Welcher Tachostand gibt demnach folgende Färbung wieder?

Tachostand:
         
 

 
Mit den Funktiontasten "Reset", "weiter" und "nächste Lösung" können wir das erschöpfende Durchsuchen für ein kleines Beispiel anwenden.

 

 
Der Tachometer ist ein geeignetes Instrument, um nacheinander alle Färbungszustände der Karte durchzuzählen. Für jeden Tachostand wird geprüft, ob die Karte korrekt eingefärbt ist. Mit dieser Methode finden wir also garantiert alle Lösungen.

Ein Nachteil dieser Methode ist, dass sie sehr aufwändig ist. Die erste Lösung der folgenden Karte findet man bei Tachostand 012123, d.h. man muss 411 Färbungszustände durchprobieren.
(\(411=0*4^{5}+1*4^{4}+2*4^{3}+1*4^{2}+2*4^{1}+3*4^{0}\))
 
sehr aufwändiges Verfahren
 
 

 
Wenn also die Anzahl der Länder groß wird, ist der Aufwand der Tachometerstrategie nicht mehr zu vertreten.
 
Seite 4/18