Eine Karte wird durch einen Graphen repräsentiert. Ein Knoten steht für ein Land. Grenzen zwei Länder aneinander, sind die entsprechenden Knoten durch eine Kante verbunden.

Für unser Färbungsproblem müssen wir jetzt noch überlegen, wie wir die Information über den Färbungszustand der Karte geeignet in den Graphen einbauen.

Wir geben zunächst eine allgemeine Beschreibung an. Weiter unten wird diese an einem Beispiel verdeutlicht.

Die Information über den Färbungszustand ist folgendermaßen codiert:

• Ist ein ganzes Viertel koloriert, so ist der Knoten mit der entsprechenden Farbe belegt.
• Ist nur die innere Ecke eines Viertels ausgefüllt, so ist die Färbung mit der entsprechenden Farbe erlaubt.
• Ist das ganze Viertel jedoch grau gefärbt, so darf die entsprechende Farbe nicht mehr benutzt werden, weil sie schon von einem benachbarten Knoten belegt ist.

Das Land, das durch diesen Knoten repräsentiert wird, ist mit Farbe blau belegt. Erlaubt wären auch die Farben grün und rot. Nicht erlaubt ist die Farbe gelb.

Die so ergänzten Graphen sind ein geeignetes Modell, um unseren Algorithmus "Backtracking" in ein lauffähiges Computerprogramm umzusetzen: Die erlaubten Farben für einen Knoten sind die nicht grau belegten Viertel. Wird ein Knoten mit einer bestimmten Farbe koloriert, färben wir in allen mit ihm durch eine Kante verbundenen Knoten das entsprechende Viertel grau. Unfärbbare Knoten erkennen wir daran, dass alle vier Viertel grau sind. Machen wir die Färbung eines Knoten rückgängig, müssen wir auch die benachbarten Knoten wieder aktualisieren.

Auf der folgenden, letzten Seite wollen wir zum Abschluss beobachten, wie der Backtracking-Algorithmus zwei frühere Beispiele bearbeitet.