Das Vierfarbenproblem

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

gleichwertig zu einer Karte ist,
dabei nur die für unser Färbungsproblem wirklich wichtigen Eigenschaften einer Karte beinhaltet,
für ein systematisches Vorgehen und eine Programmierung auf einem Computer geeignet ist.

Ein Modell, das diesen Forderungen genügt, ist ein Graph.

a)	Welche der folgenden Karten lassen sich mit nur drei Farben kolorieren ?

b)	Kann man die Deutschlandkarte der Startseite mit nur drei Farben kolorieren ?

a)	Ordne folgenden Karten jeweils den entsprechenden Tachostand zu.
0 = grün 1 = blau 2 = rot 3 = gelb
b)	Welchen Färbungszustand beschreiben folgende Tachostände ?

c)	Wieviele Färbungszustände hat eine Karte mit zehn Ländern ?
d)	Wieviele Färbungszustände hat eine Karte mit zehn Ländern, wenn man sechs verschiedene Farben zuläßt ?

a)	Es gibt keine Frucht, die mit dem Buchstaben D beginnt.
b)	Der Term $\frac{1}{x^{2}-4}$ ist für alle reellen Zahlen x definiert.
c)	Für alle natürlichen Zahlen k ist $\displaystyle 2^{(2^k)} + 1$ eine Primzahl.
d)	Mädchen sind doof. (Schwierig)