🎨 Graphfärbung

Welsh–Powell ist Greedy-Färbung, angewendet auf Knoten, die in absteigender Reihenfolge nach Grad sortiert sind, sodass Knoten mit hohem Grad zuerst gefärbt werden. Diese Reihenfolge reduziert oft die Anzahl der Farben im Vergleich zu einer beliebigen Sequenz und garantiert eine Färbung mit höchstens einer Farbe mehr als dem Maximalgrad.

DSatur, kurz für Sättigungsgrad, färbt wiederholt den ungefärbten Knoten mit den meisten unterschiedlichen Farben, die bereits unter seinen Nachbarn vorhanden sind, wobei Gleichstände durch den höchsten Grad entschieden werden. Er passt die Reihenfolge dynamisch an, während Farben vergeben werden, und findet tendenziell nahezu optimale Färbungen, wobei er alle bipartiten Graphen exakt färbt.

Nicht unbedingt. Greedy, Welsh–Powell und DSatur sind Heuristiken, sodass sie mehr Farben als das Minimum verwenden können. Die exakte chromatische Zahl zu finden ist im Allgemeinen NP-schwer, sodass diese Methoden für beliebige Graphen gute, schnelle Antworten liefern, statt ein garantiertes Optimum.

Ein bipartiter Graph wie K₃₃ teilt seine Knoten in zwei Gruppen mit Kanten, die nur zwischen den Gruppen verlaufen. Da keine Kante innerhalb einer Gruppe liegt, kann man eine Gruppe mit Farbe eins und die andere mit Farbe zwei färben, was eine chromatische Zahl von genau zwei für jeden Graphen ohne ungeraden Kreis ergibt.

Der Vierfarbensatz besagt, dass jeder planare Graph — einer, der ohne sich kreuzende Kanten gezeichnet werden kann — mit höchstens vier Farben gefärbt werden kann. Er entspricht der Färbung von Ländern auf einer Karte, sodass Nachbarn sich unterscheiden, und war 1976 der erste bedeutende Satz, der mit erheblicher Unterstützung durch einen Computer bewiesen wurde.

Der Maximalgrad Δ ist die größte Anzahl von Kanten, die an einem einzelnen Knoten zusammentreffen. Greedy-Färbung benötigt nie mehr als Δ + 1 Farben, und der Satz von Brooks verschärft dies für zusammenhängende Graphen, die weder vollständig noch ungerade Kreise sind, auf Δ Farben.

Knoten können Prüfungen, Prozessorregister, Senderfrequenzen oder Arbeiter darstellen, wobei Kanten Konflikte markieren, die sich unterscheiden müssen. Die Färbung plant dann Prüfungen ohne Überschneidungen, weist Register ohne Überschreibung zu, vergibt störungsfreie Frequenzen und packt Aufgaben in möglichst wenige Zeitfenster — genau wie die hier gezeigten Farben.