Kantenfärbung weist den Kanten eines Graphen Farben zu, sodass zwei Kanten, die sich einen Endknoten teilen (adjazente Kanten), niemals dieselbe Farbe tragen. Jede Farbklasse bildet damit ein Matching. Die kleinste benötigte Farbanzahl heißt chromatischer Index χ′(G). Während die Knotenfärbung Knoten trennt, trennt die Kantenfärbung Kanten — ein klassisches Werkzeug für Planungs- und Zuordnungsprobleme.
Die Regel im Detail
Ein Graph besteht aus Knoten und Kanten. Bei einer Kantenfärbung gilt:
- Zwei Kanten mit gemeinsamem Endknoten müssen verschiedene Farben haben.
- Kanten ohne gemeinsamen Endknoten dürfen dieselbe Farbe tragen.
- Jede Farbklasse ist ein Matching — Kanten, die paarweise keinen Knoten teilen.
- χ′(G) = kleinste Anzahl Farben, mit der eine gültige Kantenfärbung möglich ist.
Es gibt eine elegante Brücke zur Knotenfärbung: Die Kantenfärbung von G ist genau die Knotenfärbung seines Kantengraphen L(G), in dem Kanten zu Knoten werden und sie verbunden sind, wenn sie in G einen Endknoten teilen.
Vizing: Es sind immer Δ oder Δ+1 Farben
Mit Δ bezeichnet man den Maximalgrad — die meisten Kanten, die an einem einzigen Knoten zusammentreffen. Der Satz von Vizing (1964) grenzt den chromatischen Index streng ein:
Δ ≤ χ′(G) ≤ Δ + 1- Klasse 1: χ′ = Δ (die optimistische Variante).
- Klasse 2: χ′ = Δ + 1.
- In bipartiten Graphen gilt immer χ′ = Δ (Satz von König, 1916) — die Färbung ist dort in Polynomialzeit berechenbar.
- Vollständige Graphen Kn: χ′ = n − 1 bei geradem n, χ′ = n bei ungeradem n.
Wie schwer ist die Berechnung?
Für bipartite Graphen ist die Kantenfärbung einfach, für allgemeine Graphen dagegen hart: Holyer zeigte 1981, dass schon für kubische Graphen (jeder Knoten hat Grad 3) die Entscheidung, ob χ′ = Δ gilt, NP-vollständig ist. Exakte Verfahren nutzen Matching-Algorithmen, Integer-Programmierung oder Branch and Bound.
Anwendungen
- Turnierplanung: Jede Runde entspricht einer Farbe. Bei n Teams ergeben die Kanten des vollständigen Graphen Kn einen Plan mit n − 1 Runden (bei geradem n), in dem jede Mannschaft pro Runde genau einmal spielt.
- Stunden- und Prüfungspläne: Konflikte zwischen Prüfungen (gleiche Prüfer, gleiche Räume) werden zu Kanten — Farben sind die Zeitslots.
- Registerallokation im Compiler: Kantenkonflikte zwischen Werten, Farben = CPU-Register.
- Frequenz- und Kanalzuteilung: Sich störende Verbindungen erhalten verschiedene Kanäle.
- Lateinische Quadrate: Die Kantenfärbung von Kn,n mit n Farben entspricht einem n×n-Layout, in dem jede Farbe in jeder Zeile und Spalte genau einmal vorkommt.
Abgrenzung
Die Knotenfärbung trennt Knoten, die Kantenfärbung trennt Kanten — beide Begriffe gehören zur Graphentheorie und sind über den Kantengraphen miteinander verbunden. Ein perfektes Matching ist ein Sonderfall einer Farbklasse, die jeden Knoten genau einmal abdeckt. Grundlagen liefert die Graph-Datenstruktur.