Graphfärbung Rechner

Graphfärbung Rechner

Der Graphfärbung-Rechner berechnet die chromatische Zahl χ(G) und eine gültige Knotenfärbung für jeden ungerichteten Graphen. Geben Sie Ihren Graphen als Kantenliste oder Adjazenzliste ein und das Tool liefert die minimale Anzahl der benötigten Farben, damit keine zwei benachbarten Knoten die gleiche Farbe teilen, zusammen mit einer interaktiven SVG-Visualisierung, einem animierten DSATUR-Trace und einer Aufschlüsselung, welche Knoten welche Farbe erhalten.

Was ist Graphfärbung?

Eine ordnungsgemäße Knotenfärbung eines Graphen G = (V, E) weist jedem Knoten eine Farbe zu, sodass jede Kante Endpunkte mit unterschiedlichen Farben hat. Die chromatische Zahl, geschrieben als χ(G), ist die kleinste Anzahl an Farben, für die eine solche Färbung existiert. Die Berechnung von χ(G) ist im Allgemeinen NP-schwer, aber das Problem hat eine schöne mathematische Theorie und viele praktische Anwendungen: Prüfungsplanung, Funkfrequenzzuweisung, Registerallokation in Compilern und der berühmte Vier-Farben-Satz für ebene Karten.

Wichtige Sätze und Schranken

• Triviale Schranken: 1 ≤ χ(G) ≤ |V| für jeden Graphen.
• Untere Cliquenschranke: χ(G) ≥ ω(G), wobei ω(G) die Größe der größten Clique ist.
• Bipartite Charakterisierung: χ(G) ≤ 2 genau dann, wenn G keinen ungeraden Zyklus hat (König).
• Satz von Brooks: χ(G) ≤ Δ(G), es sei denn, G ist ein vollständiger Graph oder ein ungerader Zyklus, in welchem Fall χ(G) = Δ(G) + 1 ist. Hierbei ist Δ(G) der maximale Grad.
• Vier-Farben-Satz: Jeder planare Graph ist 4-färbbar.
• Obere Greedy-Schranke: Jeder Greedy-Algorithmus verwendet höchstens Δ(G) + 1 Farben.

In diesem Rechner verwendete Algorithmen

DSATUR (Degree of Saturation)

DSATUR wurde 1979 von Daniel Brélaz eingeführt und ist eine der stärksten praktischen Heuristiken für die Graphfärbung. Es wählt wiederholt den ungefärbten Knoten aus, dessen Nachbarn bereits die meisten unterschiedlichen Farben verwenden (seine Sättigung), löst Gleichstände nach dem Knotengrad auf und weist ihm die kleinste Farbe zu, die nicht von seinen Nachbarn verwendet wird. DSATUR ist nachweislich optimal für bipartite Graphen und viele strukturierte Graphfamilien und liefert in Millisekunden hochwertige Färbungen für Graphen mit Hunderten von Knoten.

Welsh-Powell

Der Welsh-Powell-Algorithmus sortiert Knoten in absteigender Reihenfolge ihres Grades und färbt sie dann gierig (greedy). Er läuft in O(|V|²)-Zeit und garantiert höchstens Δ(G) + 1 Farben. Er ist extrem schnell und oft eine gute erste Annäherung, obwohl er von DSATUR bei Graphen mit variierender lokaler Struktur übertroffen werden kann.

Greedy (Eingabereihenfolge)

Der einfachste Algorithmus: Gehe die Knoten in der Reihenfolge der Eingabe durch und gib jedem die kleinste Farbe, die nicht von einem bereits gefärbten Nachbarn verwendet wird. Das Ergebnis hängt stark von der Eingabereihenfolge ab, aber eine zufällige Reihenfolge bietet einen Basiswert, gegen den man intelligentere Heuristiken vergleichen kann.

Exaktes Backtracking

Für kleine Graphen (bis etwa 18 Knoten) kann der Rechner die wahre chromatische Zahl finden, indem er k = 2, 3, 4, ... ausprobiert und versucht, den Graphen mittels Tiefensuche-Backtracking k-farbig zu färben. Die Suche ordnet Knoten nach absteigendem Grad und bricht ab, wenn keine Farbe verfügbar ist. Wenn der exakte Algorithmus erfolgreich ist, wird das Ergebnis als "Exakt" gekennzeichnet.

Eingabeformate

Kantenliste

Schreiben Sie jede Kante als zwei Knotenbezeichnungen, getrennt durch einen Bindestrich, ein Leerzeichen oder einen Pfeil. Trennen Sie Kanten durch Kommas oder Zeilenumbrüche. Knotenbezeichnungen können Buchstaben, Ziffern oder Unterstriche sein. Beispiel:

Adjazenzliste

Schreiben Sie jeden Knoten, einen Doppelpunkt und die kommagetrennte Liste seiner Nachbarn. Beispiel:

Selbstschleifen werden abgelehnt, da ein Knoten nicht eine andere Farbe als er selbst erhalten kann. Doppelte Kanten werden stillschweigend dedupliziert, und der Graph wird als ungerichtet behandelt.

Wie man diesen Rechner benutzt

1. Format wählen: Wechseln Sie zwischen Kantenliste und Adjazenzliste mit den Radio-Buttons.
2. Graph eingeben: Fügen Sie Ihre Daten ein oder klicken Sie auf eines der Schnellbeispiele (Dreieck, vollständiger K₅, Petersen-ähnliches Rad, bipartit K₃,₃, Prüfungsplanung).
3. Algorithmus wählen: Lassen Sie "Auto" für die beste Voreinstellung stehen oder erzwingen Sie Welsh-Powell, Greedy, DSATUR oder exaktes Backtracking.
4. Auf "Graph färben" klicken: Die chromatische Zahl, eine farbweise Liste, ein interaktives SVG mit ziehbaren Knoten und ein animierter Schritt-für-Schritt-Trace erscheinen unten.
5. Erkunden: Drücken Sie Start, um zu sehen, wie der Algorithmus die Knoten nacheinander färbt, ziehen Sie Knoten zum Umordnen des Layouts und nutzen Sie Zurück / Vor, um den Trace manuell zu durchlaufen.

Praktische Anwendungen der Graphfärbung

Prüfungsplanung

Lasse jede Prüfung ein Knoten sein und zeichne eine Kante zwischen Prüfungen, die mindestens einen gemeinsamen Studenten haben. Eine ordnungsgemäße Färbung mit k Farben ergibt einen Zeitplan mit k Zeitfenstern, sodass kein Student einen Konflikt hat. Die chromatische Zahl ist die minimale Anzahl an Zeitfenstern.

Funkfrequenzzuweisung

Sender, die sich in Interferenzreichweite voneinander befinden, müssen auf unterschiedlichen Frequenzen senden. Die chromatische Zahl des Interferenzgraphen ist die minimale Anzahl der benötigten Frequenzen.

Registerallokation

In Compilern sind die Lebensdauerbereiche von Variablen Knoten; wenn sich zwei Bereiche zeitlich überschneiden, gibt es eine Kante zwischen ihnen. Eine k-Färbung weist Variablen k CPU-Registern ohne Kollisionen zu.

Kartenfärbung

Länder, die eine gemeinsame Grenze haben, müssen unterschiedliche Farben erhalten. Der Vier-Farben-Satz (Appel-Haken, 1976) beweist, dass vier Farben für jede planare Karte immer ausreichen.

Sudoku und Rätsel

Ein ausgefülltes Sudoku ist eine 9-Färbung eines Graphen, dessen Knoten die 81 Zellen sind und dessen Kanten Zellen in derselben Zeile, Spalte oder demselben 3×3-Block verbinden. Graphfärbung ist der mathematische Kern vieler Constraint-Satisfaction-Rätsel.

Interessante Spezialfälle

• Vollständiger Graph K_n: χ(K_n) = n. Jedes Knotenpaar ist benachbart, daher müssen alle Farben unterschiedlich sein.
• Zyklus C_n: χ(C_n) = 2, wenn n gerade ist, 3, wenn n ungerade ist.
• Baum: Jeder Baum mit ≥ 2 Knoten hat χ = 2 (Bäume sind bipartit).
• Bipartiter Graph: χ = 2, wenn der Graph mindestens eine Kante hat.
• Petersen-Graph: Ein berühmter 3-regulärer Graph mit χ = 3.
• Rad-Graph W_n: Ein Mittelknoten, der mit einem n-Zyklus verbunden ist. χ = 3, wenn n gerade ist, 4, wenn n ungerade ist.

Häufig gestellte Fragen

Was ist die chromatische Zahl eines Graphen?

Die chromatische Zahl χ(G) ist die kleinste Anzahl an Farben, die benötigt wird, um die Knoten eines Graphen so zu färben, dass keine zwei benachbarten Knoten die gleiche Farbe teilen. Bipartite Graphen haben eine chromatische Zahl von höchstens 2; jeder Graph, der ein Dreieck enthält, hat mindestens 3; und nach dem Satz von Brooks übersteigt die chromatische Zahl nie den maximalen Grad, außer bei vollständigen Graphen und ungeraden Zyklen.

Welchen Algorithmus verwendet dieser Rechner?

Für kleine Graphen führt der Rechner eine exakte Backtracking-Suche aus, um die wahre chromatische Zahl zu finden. Für größere Graphen verwendet er die DSATUR-Heuristik, die wiederholt den ungefärbten Knoten mit den meisten bereits gefärbten Nachbarn färbt. Sie können auch Welsh-Powell oder einfaches Greedy wählen.

Wie soll ich meinen Graphen eingeben?

Nutzen Sie den Kantenlisten-Modus für eine Kante pro Zeile wie A-B oder kommagetrennt. Nutzen Sie den Adjazenzlisten-Modus für jeden Knoten gefolgt von einem Doppelpunkt und seinen Nachbarn, wie A: B, C. Selbstschleifen sind nicht erlaubt.

Warum findet DSATUR nicht immer die wahre chromatische Zahl?

Graphfärbung ist NP-schwer, daher findet kein bekannter schneller Algorithmus immer das Minimum. DSATUR ist eine exzellente Heuristik und oft präzise, kann aber bei speziellen Graphen mehr Farben als nötig verwenden. Der Rechner gibt zur Orientierung auch eine untere Schranke (Clique) an.

Was ist eine reale Anwendung der Graphfärbung?

Modelle für Prüfungspläne, Frequenzzuweisungen bei Mobilfunkmasten, Registerverwaltung in Prozessoren, Kartografie und das Lösen von Sudokus basieren alle auf Graphfärbung.

Ist die chromatische Zahl immer gleich der größten Clique?

Nein. Die Cliquenzahl ω(G) ist eine untere Schranke. Bei perfekten Graphen sind sie gleich, aber bei Graphen wie den Mycielski-Graphen kann die chromatische Zahl viel höher sein, selbst ohne große Cliquen.

Was ist der größte Graph, den dieser Rechner verarbeiten kann?

Der Rechner unterstützt bis zu 60 Knoten und 600 Kanten. Bei mehr als ca. 18 Knoten wechselt der exakte Algorithmus eventuell zu DSATUR, da Backtracking sonst zu langsam würde. Das deckt die meisten akademischen und kleineren praktischen Beispiele ab.

Weiterführende Literatur

• Knotenfärbung — Wikipedia
• DSATUR-Algorithmus — Wikipedia (Englisch)
• Chromatisches Polynom — Wikipedia
• Vier-Farben-Satz — Wikipedia
• Satz von Brooks — Wikipedia

Erweiterte Rechenoperationen:

• Antilogarithmus Rechner
• Betafunktion-Rechner
• Binomialkoeffizient-Rechner
• Binomialverteilungsrechner
• Binär-Rechner
• Zentraler Grenzwertsatz Rechner
• Kombinatorik-Rechner Empfohlen
• Rechner für komplementäre Fehlerfunktion
• Komplexe Zahlen Rechner
• Entropie-Rechner
• Fehlerfunktion berechnen
• Rechner für exponentiellen Zerfall
• Exponentielle Zunahme Rechner
• Exponentielles Integral Rechner
• exponenten-rechner-hohe-präzision
• Fakultätsrechner
• Gammafunktion-Rechner
• Goldener Schnitt Rechner
• Halbwertszeit berechnen
• Prozentuale Wachstumsrate Rechner Empfohlen
• permutationsrechner
• Poisson-Verteilungsrechner
• Polynom Wurzeln Rechner mit detaillierten Schritten
• Wahrscheinlichkeitsrechner
• Wahrscheinlichkeitsverteilung Rechner
• Anteil-Rechner
• Mitternachtsformel Rechner
• Wissenschaftlicher Taschenrechner
• Wissenschaftliche Schreibweise Rechner
• Signifikante Stellen Rechner Neu
• Summe von Kuben Rechner
• Summe von positiven Ganzzahlen Rechner
• Summe von Quadratzahlen Rechner
• Wahrheitstabellen-Generator
• Mengenlehre-Rechner
• Venn-Diagramm-Generator (3 Mengen)
• Chinesischer Restsatz Rechner
• Euler Totient Funktion Rechner
• Erweiterter Euklidischer Algorithmus Rechner Empfohlen
• Modularer Multiplikativer Inverser Rechner
• Kettenbruch-Rechner Empfohlen
• Dijkstra Kürzester Weg Rechner
• Minimaler Spannbaum Rechner
• Graph Gradfolgen-Validator
• Derangement Subfaktorielle Rechner
• Stirling-Zahlen-Rechner
• Schubfachprinzip-Rechner
• Markov-Ketten Stationäre Verteilung Rechner
• rundungsrechner Neu
• Negativer Binomialverteilungsrechner Neu
• Permutationen mit Wiederholung Rechner Neu
• Modulare Exponentiationsrechner Neu
• Primitivwurzel-Rechner
• Boolesche Algebra Vereinfacher Neu
• Karnaugh-Diagramm (K-Map) Löser Neu
• Graphfärbung Rechner Neu
• Topologische Sortierung Rechner Neu
• Adjazenzmatrix-Rechner Neu
• Inklusions-Exklusions-Rechner Neu
• Solver für lineare Programmierung Neu
• Traveling Salesman Solver (TSP) Neu
• Hamilton-Pfad-Prüfer Neu
• Planarer Graph Prüfer Neu
• Netzwerkfluss-Rechner (Maximaler Fluss) Neu
• Stable Marriage Problem Löser Neu
• Gruppentheorie-Ordnungsrechner Neu
• Ring und Körperrechner Neu