Graphenfärbung-Explorer

Die chromatische Zahl χ(G) ist die minimale Anzahl an Farben, sodass keine Kante zwei gleichfarbige Knoten verbindet. Sie exakt zu bestimmen ist NP-schwer – die beste allgemeine Garantie liegt zwischen einer unteren Clique-Schranke (jede Clique der Größe k erzwingt mindestens k Farben) und einer oberen Greedy-Schranke (die Welsh-Powell-Färbung nach absteigendem Grad verwendet nie mehr als Δ+1 Farben, wobei Δ der maximale Grad ist). Für planare Graphen – solche, die sich ohne Kantenüberschneidungen zeichnen lassen – garantiert der Vierfarbensatz, dass stets 4 Farben genügen; er wurde 1976 erstmals per Computer bewiesen und ist bis heute einer der wenigen bedeutenden Sätze, die eine erschöpfende Fallprüfung durch Computer erfordern. Graphenfärbung liegt realen Zuordnungsproblemen zugrunde: Registerzuteilung in Compilern, Prüfungsterminplanung und Funkfrequenzzuweisung lassen sich alle auf die Färbung eines Konfliktgraphen zurückführen.

Graphenfärbung folgt einer einzigen Regel: Keine Kante darf zwei Knoten gleicher Farbe verbinden, und man möchte mit möglichst wenigen Farben auskommen. Diese eine Bedingung entscheidet über alles. Eine nützliche Faustregel: Jeder Kreis gerader Länge kommt mit 2 Farben aus, jeder Kreis ungerader Länge braucht 3 – ein Dreieck (der kleinste ungerade Kreis) lässt sich also nie mit 2 Farben färben. Bau beide im Werkzeug nach und beobachte die Konfliktzahl.

Knoten nacheinander zu färben und stets die kleinste freie Farbe zu wählen, wirkt sicher – doch die Reihenfolge ist entscheidend. Bei einer Familie sogenannter Kronengraphen – 2n Knoten, die nur 2 Farben benötigen – zwingt eine bösartige Reihenfolge das gierige Verfahren dazu, stattdessen n Farben zu verwenden. Der schlimmste Fall ist unbeschränkt schlecht; genau deshalb sortiert die Auto-Färbung des Werkzeugs die Knoten nach absteigendem Grad (Welsh-Powell), um solche Fallen zu umgehen.