Graphfärbung — chromatische Zahl & Anwendungen

Mit Graphfärbung ist meist die Knotenfärbung gemeint: Weise jedem Knoten eine Farbe zu, sodass benachbarte Knoten nicht dieselbe Farbe haben. Die kleinste Anzahl von Farben, die dafür ausreicht, heißt chromatische Zahl und wird als $\chi(G)$ geschrieben.

Wenn du die schnelle Intuition willst: Farben sind einfach konfliktfreie Bezeichnungen. Zwei Knoten dürfen genau dann dieselbe Farbe haben, wenn keine Kante zwischen ihnen liegt.

Definition der Graphfärbung in einer Minute

Bei einer zulässigen Färbung verbindet jede Kante zwei unterschiedlich gefärbte Knoten. Das ist die ganze Regel.

Wenn also $\chi(G)=3$ gilt, dann sind gleichzeitig zwei Aussagen wahr:

• Es gibt eine zulässige Färbung mit $3$ Farben.
• Es gibt keine zulässige Färbung mit nur $2$ Farben.

Deshalb ist die chromatische Zahl ein Minimum und nicht einfach die Anzahl von Farben, die du zufällig in einer Zeichnung verwendet hast.

Falls nichts anderes gesagt wird, bedeutet Graphfärbung in einem Einführungskurs das Färben der Knoten eines einfachen ungerichteten Graphen. Kantenfärbung ist ein anderes Problem mit anderen Regeln.

Was die chromatische Zahl wirklich misst

Die Namen der Farben spielen keine Rolle. Du kannst Rot, Blau und Grün verwenden oder die Bezeichnungen $1$, $2$ und $3$.

Wichtig ist die Gruppierung. Alle Knoten mit derselben Farbe bilden eine Menge, in der keine Kanten liegen, also eine Gruppe ohne Konflikte.

Genau diese Sichtweise macht Graphfärbung in Planungs- und Zuteilungsproblemen nützlich. Eine Farbe bedeutet oft: „Diese Elemente können denselben Zeitslot teilen.“

Durchgerechnetes Beispiel: Warum ein 5-Kreis 3 Farben braucht

Betrachte den Kreisgraphen $C_5$ mit den Kanten $AB, BC, CD, DE,$ und $EA$.

Probiere zuerst $2$ Farben. Gib $A$ die Farbe $1$ und $B$ die Farbe $2$. Dann ist die Färbung entlang des Kreises erzwungen:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Betrachte nun $E$. Es ist sowohl zu $D$ als auch zu $A$ benachbart, also kann es wegen $D$ nicht Farbe $2$ haben und wegen $A$ nicht Farbe $1$.

Also scheitern $2$ Farben.

Aber $3$ Farben funktionieren. Eine zulässige Färbung ist

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

also

$$\chi(C_5)=3$$

Dieses Beispiel lohnt sich zum Merken, weil es ein wichtiges Muster zeigt: Bei Kreisgraphen kann ein gerader Kreis mit $2$ Farben gefärbt werden, ein ungerader Kreis braucht aber $3$.

So argumentierst du bei Graphfärbung auf kleinen Graphen

Zwei schnelle Prüfungen helfen.

Erstens: Suche nach einem erzwungenen Konflikt. Im Beispiel oben führt das abwechselnde Verwenden von zwei Farben auf einem ungeraden Kreis dazu, dass der letzte Knoten mit beiden verfügbaren Möglichkeiten kollidiert.

Zweitens: Suche nach einer unteren Schranke. Wenn ein Graph ein Dreieck enthält, dann sind diese drei Knoten paarweise benachbart und brauchen daher bereits $3$ verschiedene Farben. Das liefert nicht immer die exakte Antwort, aber es beweist, dass die chromatische Zahl mindestens $3$ ist.

Häufige Fehler bei Aufgaben zur Graphfärbung

Ein häufiger Fehler ist, Knoten als benachbart zu behandeln, nur weil sie in der Zeichnung nah beieinander liegen. Nur eine tatsächliche Kante erzeugt eine Einschränkung für die Färbung.

Ein anderer Fehler ist die Annahme, dass jeder Knoten eine eigene Farbe braucht. Nicht benachbarte Knoten können dieselbe Farbe wiederverwenden, und effiziente Färbungen nutzen Farben normalerweise so oft wie möglich mehrfach.

Manche Lernende verwechseln außerdem Knotenfärbung und Kantenfärbung. Auf dieser Seite geht es um benachbarte Knoten, nicht um benachbarte Kanten.

Ein letzter Fehler ist, die Anzahl der Farben anzugeben, die du zufällig verwendet hast, statt die minimale erforderliche Anzahl. Wenn du auf einem Graphen $4$ Farben benutzt, beweist das nicht, dass die chromatische Zahl $4$ ist.

Wo Graphfärbung verwendet wird

Eine Standardanwendung ist die Stunden- oder Prüfungsplanung. Angenommen, jeder Knoten ist eine Prüfung und eine Kante bedeutet, dass zwei Prüfungen gemeinsame Studierende haben und nicht gleichzeitig stattfinden können. Dann kann eine Farbe einen Zeitslot darstellen.

In diesem Modell gibt die chromatische Zahl an, wie wenige Zeitslots möglich sind. Wenn $\chi(G)=4$ gilt, dann gibt es keinen gültigen Plan mit nur $3$ Zeitslots.

Dieselbe Idee taucht bei der Kartenfärbung auf, wo benachbarte Regionen verschieden sein müssen, und im Compilerbau, wo Variablen, die gleichzeitig benötigt werden, sich nicht dasselbe Register teilen können.

Probiere eine ähnliche Aufgabe zur Graphfärbung

Zeichne einen Graphen mit den Knoten $P,Q,R,S,T$ und den Kanten $PQ, QR, RS, ST, TP,$ und $PR$.

Beginne damit, ein Dreieck zu finden, um eine untere Schranke zu erhalten. Versuche dann, den Graphen mit so wenigen Farben wie möglich zu färben, und prüfe, ob benachbarte Knoten dieselbe Farbe haben. Wenn du einen nächsten Schritt willst, probiere deine eigene Version mit einem größeren Graphen aus und schau, ob du beweisen kannst, dass deine Färbung minimal und nicht nur gültig ist.