Graphenfärbung Löser

Pseudocode

Gierige Färbung besteht aus drei Zeilen und liefert stets eine gültige Färbung. Was sie nicht zwangsläufig liefert, ist eine minimale, und die Knotenreihenfolge entscheidet, wie nah sie herankommt.

GierigeFärbung(graph, reihenfolge):
    farbe = {}
    für jeden Knoten v in reihenfolge:
        belegt = { farbe[n] : n Nachbar von v, gefärbt }
        c = kleinste positive ganze Zahl nicht in belegt
        farbe[v] = c
    gib farbe zurück

// Welsh-Powell: nach absteigendem Grad sortieren
// DSatur: wiederholt den ungefärbten Knoten mit den meisten
//         verschieden gefärbten Nachbarn (Sättigung) wählen,
//         bei Gleichstand nach Grad entscheiden

Die gierige Färbung braucht nie mehr als Maximalgrad plus eins Farben, denn wenn du einen Knoten erreichst, hat er höchstens so viele Nachbarn und damit höchstens so viele verbotene Farben. Das ist eine echte Garantie, kann aber weit von der wahren chromatischen Zahl entfernt liegen. DSatur ist die praktische Verbesserung: den am stärksten eingeschränkten Knoten als nächsten zu wählen ist genau die Heuristik, die verhindert, dass du dich selbst in die Enge treibst.

Durchgerechnetes Beispiel, Schritt für Schritt

Färbe einen Fünferzyklus gierig in alphabetischer Reihenfolge und vergleiche das Ergebnis dann mit der wahren chromatischen Zahl.

Beispielgraph: Ungerichteter Zyklus A-B, B-C, C-D, D-E und E-A.

1. A färben. Noch ist kein Nachbar gefärbt, A erhält also Farbe 1.
2. B färben. B ist zu A benachbart, das Farbe 1 trägt, die kleinste verfügbare ist also Farbe 2.
3. C färben. C ist zu B (Farbe 2) und zum noch ungefärbten D benachbart. Farbe 1 ist frei, C nimmt also die 1.
4. D färben. D ist zu C (Farbe 1) und zum ungefärbten E benachbart. Farbe 2 ist frei, D nimmt also die 2.
5. E erzwingt eine dritte Farbe. E ist zu D (Farbe 2) und zu A (Farbe 1) benachbart. Beide vorhandenen Farben sind belegt, E braucht also Farbe 3.

Die Färbung lautet A 1, B 2, C 1, D 2, E 3 und benutzt drei Farben, und eine erschöpfende Prüfung bestätigt, dass die chromatische Zahl eines Fünferzyklus tatsächlich 3 beträgt. Gierig war hier also optimal. Der Grund, warum überhaupt drei nötig sind, ist die ungerade Länge des Zyklus: Farben müssen entlang eines Zyklus alternieren, und ein ungerader Zyklus führt dich zum Start zurück, wo du eine andere Farbe als die bereits vergebene bräuchtest. Jeder gerade Zyklus kommt mit 2 aus.

Komplexität und woher sie kommt

Zeit: O(V + E) gierig, exakt NP-schwer · Speicher: O(V)

Die gierige Färbung betrachtet jeden Knoten einmal und prüft jede Kante zweimal, einmal von jedem Endpunkt, ist also O(V + E) mit O(V) Speicher für das Farbfeld. Dieser Aufwand erkauft eine gültige Färbung mit höchstens Maximalgrad plus eins Farben, nie ein garantiertes Minimum. Die tatsächliche chromatische Zahl zu berechnen ist NP-schwer, und sie auch nur innerhalb eines Faktors V hoch 1 minus Epsilon zu approximieren ist NP-schwer, was ungewöhnlich stark ist: für die meisten Probleme existiert irgendeine brauchbare Approximation, für die Färbung im Wesentlichen keine. Die 2-Färbbarkeit ist die Ausnahme und ist leicht, denn sie ist genau der Bipartitheitstest mit O(V + E). Die 3-Färbbarkeit zu entscheiden ist bereits NP-vollständig.

Wann Graphenfärbung passt und wann nicht

Wähle danach, wie viele Farben du erwartest und ob du das wahre Minimum brauchst.

Häufige Fehler

• Annehmen, gierig liefere die chromatische Zahl. Es liefert eine gültige Färbung, keine minimale, und der Abstand kann groß sein. Auf dem Kronengraphen mit den Teilen {a1,a2,a3} und {b1,b2,b3}, in dem ai mit bj verbunden ist, sobald i von j verschieden ist, lässt die verschränkte Reihenfolge a1,b1,a2,b2,a3,b3 den gierigen Algorithmus 3 Farben verwenden, obwohl der Graph bipartit ist und 2 genügen. Dieselbe Menge in der Reihenfolge a1,a2,a3,b1,b2,b3 kommt mit 2 aus.
• Übersehen, wie stark die Knotenreihenfolge zählt. Es gibt stets eine Reihenfolge, die die wahre chromatische Zahl erreicht, und sie zu finden ist genauso schwer wie das Färbungsproblem selbst. Deshalb wählt DSatur laufend dynamisch statt eine Reihenfolge vorab festzulegen.
• Chromatische Zahl mit Cliquenzahl verwechseln. Eine Clique der Größe k erzwingt mindestens k Farben, die Cliquenzahl ist also eine untere Schranke, doch beide können auseinanderfallen. Ungerade Zyklen der Länge 5 oder mehr brauchen 3 Farben und enthalten überhaupt kein Dreieck.
• Eine gute Approximation erwarten. Anders als bei vielen NP-schweren Problemen ist für die Graphfärbung keine Approximation mit konstantem Faktor bekannt, und starke Härteergebnisse legen nahe, dass es keine gibt. Heuristiken können in der Praxis gut abschneiden, tragen aber keine Garantie für den schlechtesten Fall.
• Vergessen, dass Schleifen es unmöglich machen. Ein zu sich selbst benachbarter Knoten kann sich niemals von sich selbst unterscheiden, ein Graph mit einer Schleife besitzt also überhaupt keine zulässige Färbung. Weise solche Eingaben von vornherein zurück.

Häufig gestellte Fragen

Was ist Graphfärbung?

Die Graphfärbung weist jedem Knoten eine Farbe zu, sodass keine zwei benachbarten Knoten dieselbe tragen. Die kleinste funktionierende Farbanzahl ist die chromatische Zahl des Graphen. Sie modelliert jedes Problem, in dem einander widersprechende Elemente getrennt werden müssen, etwa Prüfungen so zu legen, dass niemand zwei gleichzeitig schreibt.

Was ist die chromatische Zahl eines Graphen?

Die minimale Anzahl Farben für eine zulässige Färbung. Ein bipartiter Graph hat chromatische Zahl 2 oder weniger, ein ungerader Zyklus hat 3, und ein vollständiger Graph auf n Knoten hat n. Sie allgemein zu berechnen ist NP-schwer, wobei eine Clique der Größe k eine einfache untere Schranke von k liefert.

Verwendet der gierige Algorithmus immer die wenigsten Farben?

Nein. Er liefert stets eine gültige Färbung mit höchstens Maximalgrad plus eins Farben, doch das kann die chromatische Zahl übersteigen. Auf dem Kronengraphen, einem bipartiten Graphen mit nur 2 nötigen Farben, lässt eine unglückliche Reihenfolge den gierigen Algorithmus 3 verwenden. Es gibt stets eine optimale Reihenfolge, sie zu finden ist jedoch so schwer wie das ursprüngliche Problem.

Was ist der Unterschied zwischen gieriger Färbung und DSatur?

Gierig legt eine Knotenreihenfolge vorab fest und färbt in dieser Reihenfolge. DSatur wählt den nächsten Knoten dynamisch, stets jenen mit den meisten verschieden gefärbten Nachbarn, und entscheidet Gleichstände nach Grad. Diese Konzentration auf den am stärksten eingeschränkten Knoten macht DSatur auf bipartiten Graphen optimal und allgemein deutlich besser, zum Preis von O(V hoch 2) statt O(V + E).

Wofür wird Graphfärbung verwendet?

Für die Registerzuteilung in Compilern, wo Register die Farben sind und sich überlappende Variablen benachbart. Außerdem für Prüfungs- und Schichtpläne, die Vergabe von Funkfrequenzen ohne Störung zwischen nahen Sendern, das Lösen von Sudokus und die Trennung widerstreitender Aufgaben in beliebigen Ressourcenzuteilungsproblemen.