Graphenfärbung-Rechner
Welsh-Powell-Algorithmus · Chromatische Zahl · Vertex Coloring
Gib einen ungerichteten Graphen als Kantenliste ein, um sofort eine Knotenfärbung zu erhalten. Berechnet die Obergrenze der chromatischen Zahl mit dem Welsh-Powell-Algorithmus und visualisiert den gefärbten Graphen.
Schnellbeispiele
Eine Kante pro Zeile oder kommagetrennt. Bindestrich oder Leerzeichen zwischen Knoten-IDs verwenden. Z.B. 1-2, 1-3, 2-3 or A B pro Zeile. Max 20 Knoten für die Visualisierung.
Knotenfärbungs-Zuweisungen
| Knoten | Grad | Farbe # | Farbname |
|---|
Graph-Visualisierung
Grapheneigenschaften
Gradsequenz
Grenzen der chromatischen Zahl
Was ist Graphenfärbung?
Die Graphenfärbung ist eines der meistuntersuchten Probleme in der Kombinatorik und theoretischen Informatik. In der häufigsten Form — Knotenfärbung (vertex coloring) — ist das Ziel, jedem Knoten eine Farbe zuzuweisen, sodass keine zwei durch eine Kante verbundenen benachbarten Knoten dieselbe Farbe haben.
Die Graphenfärbung hat eine lange Geschichte, die auf das berühmte Kartenfärbungsproblem zurückgeht.
Chromatische Zahl
Die chromatische Zahl χ(G) eines Graphen G ist die minimale Anzahl von Farben, die für eine echte Knotenfärbung benötigt wird.
- Ein Graph ohne Kanten hat χ = 1
- Jeder Graph mit mindestens einer Kante hat χ ≥ 2
- Bipartit Graphen (keine ungeraden Kreise) haben χ = 2
- Ungerade Kreise C2k+1 haben χ = 3
- Vollständige Graphen Kn haben χ = n
- Bäume und Wälder haben χ = 2 (oder 1, falls leer)
Die Berechnung der exakten chromatischen Zahl ist NP-schwer, aber Polynomialzeit-Greedy-Algorithmen liefern effiziente Obergrenzen.
Welsh-Powell-Algorithmus
Der Welsh-Powell-Algorithmus (1967) ist eine Greedy-Heuristik zur Knotenfärbung, die eine clevere Knotenreihenfolge verwendet:
- Schritt 1: Sortiere alle Knoten absteigend nach Grad
- Schritt 2: Weise jedem Knoten in der sortierten Reihenfolge die niedrigste verfügbare Farbe zu, die nicht von Nachbarn verwendet wird
- Schritt 3: Die Anzahl der verwendeten Farben ist die Obergrenze für χ(G)
Die Idee ist, dass Knoten mit hohem Grad am schwersten zu färben sind.
Brooks' Theorem
Ein wichtiges theoretisches Ergebnis ist der Satz von Brooks (1941).
Untere Schranken: Cliquen-Zahl
Die Cliquen-Zahl ω(G) — die Größe des größten vollständigen Teilgraphen — liefert eine untere Schranke für die chromatische Zahl: ω(G) ≤ χ(G).
Der Vier-Farben-Satz
Der Vier-Farben-Satz besagt, dass jeder planare Graph 4-färbbar ist.
Anwendungen der Graphenfärbung
- Registerzuweisung: In Compilern.
- Ablaufplanung (Scheduling): Aufgaben, die um Ressourcen konkurrieren.
- Kartenfärbung: Regionen mit gemeinsamer Grenze benötigen unterschiedliche Farben.
- Sudoku: Das Lösen entspricht einer 9-Färbung.
- Frequenzzuweisung: Benachbarte Funkmasten benötigen unterschiedliche Frequenzen.
- Stundenplanung: Prüfungen mit gleichen Studenten dürfen sich nicht überschneiden.
Bipartit Graphen und 2-Färbbarkeit
Ein Graph ist bipartit, wenn seine Knoten in zwei disjunkte Mengen unterteilt werden können. Bipartit Graphen haben χ = 2.
| Graphentyp | Chromatische Zahl | Grund |
|---|---|---|
| Leerer Graph (keine Kanten) | 1 | Alle Knoten selbe Farbe |
| Baum / Wald | 2 | Bipartit (keine Kreise) |
| Gerader Kreis C2k | 2 | Bipartit |
| Ungerader Kreis C2k+1 | 3 | Nicht bipartit |
| Vollständiger Graph Kn | n | Alle Paare benachbart |
| Planarer Graph | ≤ 4 | Vier-Farben-Satz |
| Petersen-Graph | 3 | Nicht bipartit, kein Dreieck |