Graphfärbung (Graph Coloring) ordnet jedem Knoten eines Graphen eine Farbe zu, mit nur einer Regel: Zwei Knoten, die durch eine Kante verbunden sind, müssen verschiedene Farben bekommen. Ziel ist es, mit möglichst wenigen Farben auszukommen. Die minimale Anzahl heißt chromatische Zahl χ(G). Das Problem klingt harmlos, ist aber eines der klassischen NP-vollständigen Probleme der Informatik.
Die Grundidee
Ein Graph besteht aus Knoten und Kanten. Eine gültige Färbung verlangt: Jede Kante verbindet zwei Knoten mit unterschiedlicher Farbe. Ein einfaches Beispiel ist ein Stundenplan: Kurse sind Knoten, eine Kante entsteht zwischen zwei Kursen, die gemeinsame Teilnehmer haben, und die Farben sind die Zeitslots. Zwei Kurse mit gemeinsamer Kante dürfen also nicht gleichzeitig stattfinden. Die chromatische Zahl ist dann die Mindestanzahl an Zeitslots.
Leicht oder schwer?
Die Frage, ob ein Graph mit zwei Farben färbbar ist, ist leicht zu beantworten: Das ist genau dann der Fall, wenn der Graph bipartit ist. Ab drei Farben wird das Problem jedoch NP-vollständig (Karp, 1972) — die Entscheidungsfrage „Ist χ(G) ≤ 3?“ ist genauso schwer wie SAT. Wer einen effizienten Algorithmus für die 3-Färbbarkeit fände, hätte damit auch alle anderen NP-Probleme in Polynomzeit gelöst.
Nützliche Schranken helfen trotzdem: Die Cliquenzahl ω(G) (größte vollständig verbundene Gruppe) ist eine Untergrenze, der Maximalgrad Δ plus 1 eine Obergrenze: ω(G) ≤ χ(G) ≤ Δ+1.
Wichtige Spezialfälle
- Bipartite Graphen sind immer mit 2 Farben färbbar (χ = 2).
- Planare Graphen (zeichnen ohne kreuzende Kanten) brauchen höchstens 4 Farben — der berühmte Vier-Farben-Satz (1976 per Computer bewiesen). Landkarten lassen sich so mit vier Farben einfärben.
Algorithmen
Ein Greedy-Algorithmus färbt Knoten in einer Reihenfolge und vergibt jeweils die kleinste freie Farbe. Er ist schnell, braucht aber nie mehr als Δ+1 Farben — die Qualität hängt stark von der gewählten Reihenfolge ab. Bessere Ergebnisse liefern Backtracking-Verfahren (etwa DSATUR), ganzzahlige Optimierung (ILP mit Binärvariablen x_{v,c}: genau eine Farbe pro Knoten, höchstens eine gemeinsame Farbe pro Kante) oder Branch-and-Bound, die die chromatische Zahl exakt bestimmen.
Praxis
Graphfärbung steckt in überraschend vielen Anwendungen: Stunden- und Prüfungspläne, Registerallokation in Compilern (zeitgleich lebende Variablen brauchen verschiedene Register), Frequenzplanung im Mobilfunk, Sudoku (eine 9-Färbung eines 9×9-Gitters) und die Einfärbung von Karten. Eine verwandte Variante ist die Kantenfärbung, bei der Kanten statt Knoten gefärbt werden.
Verwandte Themen: Max-Flow-Min-Cut, Subset-Sum.