|
G sei ein (ungerichteter)
Graph mit Eckenmenge V
und Kantenmenge E. Eine (zulässige) Färbung von G
ist eine Färbung der Ecken mit den Farben 1,2,...,k
so daß benachbarte Ecken verschiedene Farben haben.
(also ist eine (zulässige) Färbung eine Abbildung
f: V ® {1,2,...,k} mit der Eigenschaft
f(x) ¹ f(y) für alle
Ecken x,y mit {x,y} Î E.)
Die kleinste natürliche Zahl k für die G eine zulässige Färbung mit Farben 1,2, ... , k hat, wird die chromatische Zahl c(G) genannt. |
Beachten Sie, daß bei jeder zulässigen Färbung f: V ® {1,2,...,k} die Urbildmengen f-1(1), f-1(2), ... , f-1(k) eine Partition der Eckenmenge in unabhängige Mengen ist. In diesem Applet können Sie versuchen 3 Graphen, darunter der aus obigem Beispiel entstehende, mit möglichst wenig Farben (zulässig) zu färben.
Ein Graph ist genau dann mit nur einer Farbe färbbar, falls es überhaupt keine Kanten gibt. Ein Graph ist mit zwei Farben färbbar, falls es eine Bipartition in zwei unabhängige Mengen gibt, d.h. falls G bipartit ist. Leider lassen sich 3-färbbare Graphen schon nicht mehr gut erkennen, das Problem ist NP-vollständig.
Den (bipartiten) Würfelgraphen rechts können Sie durch Anklicken der Ecken färben. Es wird jeweils die hellste noch mögliche Farbe verwendet, wobei die Farbenfolge "orange", "rot", "blau" und "schwarz" ist. In den meisten Fällen werden Sie zwei Farben brauchen, aber es gibt auch Anklickreihenfolgen (welche?), bei denen der Computer 4 Farben verwenden wird. Obwohl diese Prozedur also nicht immer das optimale Ergebnis liefert, ist die Methode interessant:
| Greedy-Algorithmus Wir ordnen die Ecken irgendwie an. Dann färben wir die Ecken nacheinander, jeweils mit der kleinstmöglichen Farbe (die Farben seien die Zahlen 1,2,3,...). |
Natürlich hängt die Zahl der verwendeten
Farben von der gewählten Anordnung der Ecken ab,
da aber jede Ecke x höchstens dG(x)
schon gefärbte Nachbarn hat, ist eine der Farben
{1,2,...,dG(x)+1} für x möglich.
c(G) £
maxx dG(x) + 1.
Das Ergebnis kann man noch minimal verbessern:
|
Satz von Brooks (1941)
Jeder endliche zusammenhängende Graph, der weder vollständig
ist, noch ein Kreis ungerader Länge, lässt sich mit
maxxÎV
dG(x) Farben zulässig färben.
|
Enthält ein Graph einen vollständigen Teilgraphen
mit k Ecken, so gibt es jedenfalls keine zulässige Färbung
von G mit weniger als k Farben, d.h.
c(G)
³ w(G),
wobei w(G) die maximale Kardinalität
eines vollständigen Teilgraphen in G ist.
Die beiden Parameter können verschieden sein
(ungerade Kreise), aber in den folgenden Beispielen
haben wir Gleichheit:
Übungsaufgabe:
Der Vergleichbarkeitsgraph bzw. Unvergleichbarkeitsgraph
einer geordneten Menge
(M,£) hat M als Eckenmenge.
Verschiedene Elemente x und y von M sind in G adjazent, falls
sie bzgl. "£"
vergleichbar bzw. unvergleichbar sind.
(a)
Zeigen Sie, daß sich jeder Vergleichbarkeitsgraph
G mit w(G) Farben zulässig färben
lässt.
(b)
Zeigen Sie, daß sich jeder Unvergleichbarkeitsgraph
G mit w(G) Farben zulässig färben
lässt.
|
Satz von de Bruijn-
Erdös (1951)
Lässt sich jeder endliche Teilgraph des unendlichen Graphen
G mit k Farben zulässig färben, so lässt sich
sogar ganz G mit k Farben zulässig färben.
|
|
Beweis: G sei ein unendlicher Graph mit Eckenmenge V.
Fund k sei eine feste natürliche Zahl.
Für x Î V und
1 £ i £ k
sei F(x,i) die Aussage
"x ist mit Farbe i gefärbt".
G ist genau dann k-färbbar, wenn die unendliche Menge
Xk von Aussagen
{ F(x,1) Ú F(x,2) Ú ... Ú F(x,k), / x Î V } È { ¬ F(x,i) Ú ¬ F(x,j) / x Î V, 1 £ i < j £ k } È { ¬ F(x,i) Ú ¬ F(y,i) / x Î V, 1 £ i £ k } erfüllbar ist. (Genauso sieht man, daß man im endlichen Fall das Problem, ob ein Graph k-färbbar ist., auf k-SAT zurückführen kann). Ist Xk unerfüllbar (d.h. der Graph nicht mit k Farben zulässig färbbar), so ist nach dem Kompaktheitssatz (in aussagenlogischer Version) sogar eine endliche Teilmenge davon unerfüllbar. W sei die endliche(!) Menge aller in diesen endlich vielen Aussagen vorkommenden Ecken. Unerfüllbarkeit dieser endlich vielen Aussagen impliziert, daß der endliche Teilgraph von G mit Eckenmenge W, bei denen zwei verschiedene Ecken genau dann benachbart sind, falls sie in G benachbart waren, auch nicht mit k Farben zulässig färbbar, wäre, im Widerspruch zur Voraussetzung. |