Zur MathePrisma-Startseite
Zur Modul-Startseite  


Das Vierfarbenproblem (Karten+ 1)
 

 
 

 
Unser Färbungsproblem lautete:
 
Merke
 
"Färbe eine Karte mit n Ländern mit nur vier Farben. Und zwar so, dass je zwei aneinander grenzende Länder verschieden koloriert sind."
 

 
Für unsere eigenen Färbungsversuche und die Algorithmen "erschöpfendes Durchsuchen" und "Backtracking" war bisher immer die Karte die Grundlage für unsere Überlegungen. Begriffe wie "Land", "grenzen an" oder "korrekt koloriert" waren intuitiv klar.

Computerprogramme besitzen keine Intuition. Und auch für uns wird es schwer, bei komplizierten Karten mit mehreren tausend Ländern die Übersicht zu behalten. Außerdem haben Länder nicht immer eine so praktische quadratische Form.

Was wir also brauchen, ist ein Modell, das
  1. gleichwertig zu einer Karte ist,
  2. dabei nur die für unser Färbungsproblem wirklich wichtigen Eigenschaften einer Karte beinhaltet,
  3. für ein systematisches Vorgehen und eine Programmierung auf einem Computer geeignet ist.
Ein Modell, das diesen Forderungen genügt, ist ein Graph.

 
Seite 14/18