Graphenfärbung

Einen Graphen mit möglichst wenigen Farben färben

Über diesen Rechner

Der Graphenfärbungs-Rechner ermittelt die chromatische Zahl χ(G) — die wenigsten Farben, die nötig sind, um die Knoten eines Graphen so zu färben, dass keine Kante zwei Knoten derselben Farbe verbindet — und zeigt eine optimale Färbung. Geben Sie die Anzahl der Knoten und eine Liste von Kanten ein; er berechnet χ exakt mit einer Branch-and-Bound-Suche, gibt den maximalen Grad Δ und die größte Clique ω (eine untere Schranke für χ) aus, kennzeichnet bipartite und vollständige Graphen und zeichnet den gefärbten Graphen. Nützlich für Ablaufplanung, Registerzuordnung, Landkartenfärbung und das Studium chromatischer Zahlen.

So färben Sie einen Graphen

  1. Geben Sie die Anzahl der Knoten ein; sie sind von 1 bis n nummeriert.
  2. Listen Sie die Kanten als Paare wie 1-2, 2-3 auf — ein Paar pro Verbindung.
  3. Lesen Sie die chromatische Zahl χ(G) und die jedem Knoten zugewiesene Farbe ab.
  4. Vergleichen Sie χ mit der größten Clique ω, um zu sehen, warum so viele Farben nötig sind, oder laden Sie ein Beispiel zum Erkunden.

Häufige Beispiele

  • Ein Dreieck (K₃) benötigt 3 Farben — jedes Paar seiner Knoten ist benachbart.
  • Gerade Kreise sind bipartit und benötigen nur 2 Farben; ungerade Kreise wie C₅ benötigen 3.
  • Der vollständige Graph Kₙ benötigt genau n Farben.
  • Eine größte Clique der Größe ω erzwingt mindestens ω Farben, daher gilt χ(G) ≥ ω.
  • Der Grötzsch-Graph benötigt 4 Farben, enthält aber kein Dreieck, sodass χ die Cliquenzahl übersteigen kann.

Häufig gestellte Fragen

Was ist die chromatische Zahl?

Die chromatische Zahl χ(G) ist die kleinste Anzahl von Farben, die nötig ist, um die Knoten eines Graphen so zu färben, dass keine Kante zwei Knoten derselben Farbe verbindet.

Wie wird die minimale Anzahl der Farben gefunden?

Da der Graph klein ist, sucht der Rechner exakt: Er probiert 1 Farbe, dann 2 und so weiter und gibt die erste Anzahl zurück, für die eine zulässige Färbung existiert. Diese Anzahl ist garantiert das wahre Minimum.

Was sind der maximale Grad und die größte Clique?

Der maximale Grad Δ ist die höchste Anzahl von Kanten, die an einem einzelnen Knoten zusammentreffen. Die größte Clique ω ist die größte Menge von Knoten, die alle paarweise benachbart sind; da sie sich alle unterscheiden müssen, ist χ(G) mindestens ω.

Warum kann ein dreiecksfreier Graph dennoch viele Farben benötigen?

Eine große Clique erzwingt viele Farben, ist aber nicht der einzige Grund. Ungerade Kreise und Graphen wie der Grötzsch-Graph benötigen auch ohne jedes Dreieck zusätzliche Farben, sodass χ(G) größer als die Cliquenzahl sein kann.

Gibt es eine Grenze für die Graphengröße?

Ja. Exakte Graphenfärbung ist rechnerisch schwierig, daher begrenzt der Rechner den Graphen auf 12 Knoten, um die Ergebnisse sofort und exakt zu halten.