Graphenfärbung-Explorer

Ziehe Knoten, zeichne Kanten und färbe den Graphen von Hand oder mit einem Greedy-Algorithmus – die untere Clique-Schranke zeigt, wie viele Farben wirklich nötig sind.

Rechenbeispiel — Graphenfärbung-Explorer

Knoten	3
Kanten	3
Verwendete Farben	0
Konflikte	0

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

wie viele Farben brauchst du wirklich? 🖖

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.

Nachbarn müssen sich unterscheiden – das ist alles 🖖

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.

Gierige Färbung kann spektakulär scheitern 🖖

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.

Aufgaben vollständig gelöst

Die tatsächliche chromatische Zahl des Petersen-Graphen 5 Schritte
Der Petersen-Graph hat 10 Knoten, 15 Kanten und kein Dreieck. Das Panel meldet daher χ ≥ 2. Bestimmen Sie die tatsächliche chromatische Zahl. Dies ist der Zustand Petersen-Graph.
1. Zwei Schranken ergeben sich bei jedem Graphen von selbst: Er benötigt mindestens so viele Farben wie seine größte Clique und niemals mehr als eins mehr als sein Maximalgrad.
  
  $ω (G) \leq χ (G) \leq Δ (G) + 1 : Petersen has ω = 2, Δ = 3 ⟹ 2 \leq χ \leq 4$
2. Die Taillenweite des Petersen-Graphen beträgt 5, sodass sich nirgends ein Dreieck darin befindet und die Cliquenschranke auf die triviale 2 kollabiert. Das ist die Zahl, die das Panel meldet.
  
  $girth = 5 ⟹ no triangle ⟹ ω = 2, yet the graph is not bipartite$
3. Zwei Farben sind nur möglich, wenn der Graph bipartit ist, und bipartit bedeutet: kein ungerader Kreis. Das äußere Fünfeck ist ein 5-Kreis, somit scheiden zwei Farben aus.
  
  $bipartite ⟺ no odd cycle; the outer 5-cycle is odd ⟹ χ \geq 3$
4. Drei Farben genügen; eine passende Färbung beweist die obere Schranke vollständig. Färbe die Ecken des äußeren Fünfecks der Reihe nach mit 1, 2, 1, 2, 3, dann die fünf inneren Ecken in derselben Reihenfolge mit 2, 1, 3, 3, 2. Dabei gehört jede innere Ecke zu der äußeren Ecke auf ihrer Speiche. Prüfe alle fünfzehn Kanten: Keine verbindet gleich gefärbte Ecken.
  
  $a 3-colouring exists ⟹ χ = 3, strictly above the clique bound ω = 2$
5. Der Satz von Brooks besagt dasselbe von oben: Ein zusammenhängender Graph, der weder vollständig noch ein ungerader Kreis ist, benötigt höchstens Δ Farben, und Δ ist hier 3.
  
  $∣ V ∣ = 10, ∣ E ∣ = 15, Δ = 3 : Brooks’ theorem gives χ \leq 3 for a connected non-complete graph$
Antwort

3, was strikt über der Schranke liegt, die das Panel beweisen kann. Die größte Clique im Petersen-Graphen ist eine einzelne Kante, sodass die Cliquenschranke nur χ ≥ 2 liefert und um eins danebenliegt. Die Lücke ist bedeutender als es scheint: Der Petersen-Graph ist das Standard-Gegenbeispiel zu der Intuition, dass die Schwierigkeit der Färbung von Cliquen herrührt, und es gibt dreiecksfreie Graphen, die vier Farben, fünf oder beliebig viele benötigen — die Mycielski-Konstruktion erzeugt diese nach Wunsch. Die Kliquenzahl ist also eine untere Schranke, die beliebig weit entfernt sein kann, weshalb die Bestimmung der chromatischen Zahl NP-schwer ist, das Finden eines Dreiecks hingegen nicht. Was den Petersen-Graphen exakt auf 3 festlegt, ist ein ungerader Kreis für die untere und der Satz von Brooks für die obere Schranke.

$χ (Petersen) = 3 > ω = 2 : the clique bound is not tight$
Vergleich von Schranken für χ auf dem vollständigen K4-Graphen 5 Schritte
Nun K₄ — vier Knoten, alle sechs Kanten vorhanden. Bestimmen Sie χ und vergleichen Sie die Schranken mit deren Verhalten beim Petersen-Graphen. Dies ist der Zustand Vollständiger K4.
1. Zählen Sie die Kanten, anstatt dem Bild zu vertrauen: Jedes Paar von vier Knoten ist verbunden, und es gibt sechs Paare.
  
  $K_{4} : ∣ V ∣ = 4, ∣ E ∣ = (2 4) = 6, every pair adjacent$
2. Jeder Knoten ist zu jedem anderen benachbart, sodass keine zwei dieselbe Farbe teilen dürfen. Das ist eine untere Schranke von 4, die außer der Definition keiner weiteren Begründung bedarf.
  
  $all four vertices are mutually adjacent ⟹ ω = 4 ⟹ χ \geq 4$
3. Vier Farben genügen offensichtlich, somit wird die Schranke erreicht. Die gleiche Überlegung ergibt χ(Kₙ) = n für jedes n, was vollständige Graphen zum einfachen Fall macht.
  
  $four colours suffice trivially ⟹ χ (K_{n}) = n$
4. Stellt man die beiden Graphen nebeneinander: dieselbe Frage, dieselben zwei Schranken, und die Lücke dazwischen macht das gesamte Thema aus.
  
  $here ω = χ = 4 : the bound is tight, and Petersen showed it need not be$
5. Man beachte, wie sich der Satz von Brooks hier verhält. Seine Schranke von Δ = 3 wäre für K₄ falsch, weshalb vollständige Graphen darin namentlich ausgenommen sind.
  
  $Δ + 1 = 4 as well — Brooks’ theorem excludes complete graphs for exactly this reason$
Antwort

4, und hier ist jede Schranke gleichzeitig scharf. Die Kliquenzahl beträgt 4, da der gesamte Graph eine Clique ist, Δ + 1 ist 4, weil jeder Knoten mit den anderen drei verbunden ist, und die wahre Antwort ist dazwischen eingezwängt, ohne Ausweg. Das ist der Fall, auf den die meisten ihre Intuition stützen, und es ist genau der Fall, den der Satz von Brooks ausschließt — seine Schranke von Δ gilt für jeden zusammenhängenden Graphen ausgenommen vollständige Graphen und ungerade Kreise, und diese beiden Probleme sind der Grund für beide Ausnahmen. Petersen und K₄ markieren die beiden Enden: eines, bei dem die Cliquenschranke um eins danebenliegt, und eines, bei dem sie gar nicht danebenliegen kann.

$χ (K_{4}) = ω (K_{4}) = Δ + 1 = 4$

Quellen (2)

Insight block 1 — the four colour theorem, and the computer proof it needed: K. Appel and W. Haken, "Every planar map is four colorable. Part I: Discharging." Illinois Journal of Mathematics 21(3), 429–490, 1977.
And the descending-degree ordering the auto-colour button uses: D. J. A. Welsh and M. B. Powell, "An upper bound for the chromatic number of a graph and its application to timetabling problems." The Computer Journal 10(1), 85–86, 1967.

Vom 42Math-Team · Aktualisiert 2026-06-16

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Graphenfärbung-Explorer

wie viele Farben brauchst du wirklich? 🖖

Nachbarn müssen sich unterscheiden – das ist alles 🖖

Gierige Färbung kann spektakulär scheitern 🖖

Beispielaufgaben