Wir stellen uns vor, dass wir den Fährverkehr zwischen vielen kleinen Inseln sicherstellen sollen.

Hier ist ein Kartenausschnitt, bei dem alle Inseln rund und gleich groß eingezeichnet sind.

Wir können nun Fähren einsetzen, um Verbindungen zwischen den Inseln herzustellen. Gibt es eine Direktverbindung von einer Insel zur anderen, so wird diese durch eine durchgezogene Linie dargestellt. Wird der Mauszeiger in die obige Skizze hinein bewegt, so erscheinen diese Linien.

Solche Gebilde aus Kreisen und Verbindungslinien nennen wir Graphen. Die Kreise werden auch als Knoten und die Linien als Kanten bezeichnet.


Graphen können eine Vielzahl von Situationen und Sachverhalten beschreiben, z.B. Computernetzwerke (Internet), Spielpläne für Turniere oder Hackordnungen. Mit etwas Überlegung kann man viele weitere Beispiele finden.

Insbesondere kann man mit einem Graphen die Nachbarschaftsbeziehungen zwischen den Ländern einer Karte darstellen. Wir betrachten dazu folgende Karte. (Bewegt man den Mauszeiger in die Skizze hinein, erscheint der zugehörige Graph.)

• Jedes Land wird durch einen Knoten vertreten.
• Grenzen zwei Länder aneinander, so sind die entsprechenden Knoten durch eine Kante verbunden.

Beim Zeichnen einer Kante ist es unerheblich, ob sie auf ihrem Weg von einem Knoten zum anderen nur die tatsächliche oder noch weitere Grenzen überschreitet. Nachdem wir den Graphen aufgebaut haben, benötigen wir die Karte sowieso nicht mehr.
Land 1 und Land 6 sind beispielsweise benachbart. Die Kante, die diese Nachbarschaft repräsentiert, kann durch Land 2 verlaufen.

Wir sehen nun auch, dass die Form und Größe der Länder überhaupt keine Rolle spielt. Wichtig ist nur der Nachbarschaftsbegriff.

Diese drei Karten stellen für unser Färbungsproblem also identische Konfigurationen dar.


In allen drei Karten ist z. B. Land 4 mit den Ländern 2, 3 und 5 benachbart, hat aber keine Grenze mit Land 1 gemeinsam.

Die obigen Karten können also durch einen einzigen Vertreter dargestellt werden. Dieser Vertreter, der Graph, kann so aussehen:


Beim Übergang von einer Karte zu einem Graphen kann man also den Begriff "Land" durch "Knoten" ersetzen. Die alte Formulierung "grenzen an" bedeutet jetzt "verbunden sein mit einer Kante".

Auf der nächsten Seite wollen wir den Übergang von Karten auf Graphen weiter präzisieren.