Mathe Vital Banner Zentrum Mathematik Banner TUM Banner

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:

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