Erweiterungen (Färbung, Gewichte)

Um einem Graphen $G = (V,E)$ zusätzliche Informationen hinzufügen zu können, erweitert man das Paar $(V,E)$ zu einem Tripel $(V,E,f)$. Falls hierbei $f$ eine Abbildung von der Knotenmenge $V$ in die Menge der natürlichen Zahlen $\mathbb{N}$ ist, spricht man von einer (Knoten-)Färbung von $G$ (man identifiziert sozusagen die diskreten Werte von $f$ mit verschiedenen Farben). Falls $f$ von $V$ in die Menge der reellen Zahlen $\mathbb{R}$ abbildet so nennt man $G = (V,E,f)$ einen knotengewichteten Graph. Analog dazu gibt es kantengefärbte bzw. kantengewichtete Graphen.

Probleme & Applet

Ein klassisches Problem in der Graphentheorie ist die $k$-Färbbarkeit eines Graphen $G$, $k \in \mathbb{N}$. Ein Graph $G = (V,E)$ heißt $k$-färbbar (genauer $k$-knotenfärbbar), wenn es eine Knotenfärbung $f: V \rightarrow {1, \ldots, k}$ von $G$ gibt, so dass für alle $v \in V: ~ f(v) \neq f(w)$, wobei $w$ Nachbar von $v$ ist. Anschaulich gesprochen ist ein Graph $k$-knotenfärbbar falls man die Knoten so mittels $k$ Farben färben kann, so dass kein Paar benachbarter Knoten die selbe Farbe hat. Identifiziert man zum Beispiel die Länder einer gegebenen Landkarte mit den Knoten und gemeinsame Landesgrenzen mit den Kanten eines ungerichteten Graphen $G$, so steckt hinter der $k$-Färbbarkeit von $G$ die Frage, ob man die Länder der Landkarte mit $k$ Farben so färben kann, dass kein Paar von Ländern mit gemeinsamer Landesgrenze die gleiche Farbe erhält.

Im nachfolgenden Applet kann man sich mit den Begriffen knotengefärbter bzw. kantengewichteter Graph vertraut machen. Dabei kann man am Beispiel des “Nachbarschaftsgraphen” von Deutschland sehen, dass man mindestens vier Farben benötigt um einen beliebigen Graphen korrekt knotenfärben zu können. Später werden wir noch konstruktiv sehen, dass fünf Farben bei planaren Graphen (grob gesprochen kein Überschneiden von Kanten) immer ausreichen (vgl. Fünffarbensatz. Mehr noch lässt sich zeigen, dass selbst vier Farben im Fall planarer Graphen ausreichen (vgl. Vierfarbensatz).

Zur Bedienung des Applets:

• Analog zum Applet auf Was ist ein Graph?.
• Im Modus Färbung kann man durch Anclicken eines Knoten dessen Farbe ändern. Die gewünschte Farbe kann durch vorheriges Drücken der Tasten “r”, “g”, “b”, “y”, “m” oder “w” ausgewählt werden. Knoten, welche bzgl. ihrer Färbung noch im Konflikt mit Ihren Nachbarn stehen werden mit einem grauen Kreis hinterlegt.
• Im Modus Gewichte kann man durch Anclicken von Kanten/Bögen deren Gewicht verändern. Für ein Erhöhen des jeweiligen Kantengewichts muss vorher die Taste “+” (Plus) zum Erniedrigen die Taste “-“ (Minus) gedrückt werden.

GraphExtensions.cdy (Dieses Applet kann in Cinderella ausgeführt werden.)