| |
|
| Table of contents |
|
2 Der allgemeine Fall 3 Spezialfälle 4 Weitere Sätze 5 Anwendungen 6 Kantenfärbungen 7 Literatur |
Definitionen
Eine Knotenfärbung bzw. einfach Färbung eines ungerichteten Graphen G=(V,E) ordnet jedem Knoten aus V eine natürliche Zahl zu, die auch Farbe genannt wird. Eine Färbung heißt zulässig, falls je zwei benachbarten Knoten eine unterschiedliche Farbe zugewiesen wird.
Anders formuliert ist also eine zulässige Färbung eines Graphen eine Partition seiner Knotenmenge in unabhängige Mengen (eine Teilmenge der Knotenmenge V eines Graphen heißt unabhängig, falls sie keine zwei benachbarten Knoten enthält).
Eine Färbung, die k verschiedene Farben verwendet, heißt k-Färbung. Die chromatische Zahl eines Graphen ist das kleinste k, für das der Graph eine zulässige k-Färbung besitzt (sie wird manchmal auch Knotenfärbungszahl, Färbungszahl oder Farbzahl genannt).
Ein Graph, der 2-färbbar ist, heißt bipartit.
Der allgemeine Fall
Das Problem, zu entscheiden, ob ein Graph G k-färbbar ist, ist NP-schwer, d.h. die Bestimmung der chromatischen Zahl eines Graphen ist im Allgemeinen ein hartes Problem. Der zur Zeit praktisch bester Algorithmus beruht auf einem Spalten-Generierungs-Ansatz (siehe Literatur). Weiterhin gibt es viele
Färbungsheuristiken, die nach bestimmten Methoden gute Färbungen suchen und somit im Erfolgsfall eine obene Schranke für die chromatische Zahl liefern.
Spezialfälle
Der Vier-Farbensatz besagt, dass die chromatische Zahl eines
planaren Graphen höchstens 4 ist. Trotzdem ist auch für planare Graphen die Entscheidungsfrage, ob er k-färbbar ist, NP-schwer.
Die Frage, ob ein Graph bipartit ist, läßt sich in Linearzeit entscheiden (z.B. reicht dazu eine Tiefensuche aus).
Für bestimmte Spezialfälle (z.B. Wälder) liefern bestimmte Färbungsheuristiken (z.B. der Greedy-Algorithmen) optimale Färbungen.
Weitere Sätze
Der Greedy-Algorithmus zeigt, dass die chromatische Zahl eines Graphen höchstens eins größer als sein Maximalgrad ist. Beispiele, die zeigen, dass diese Abschätzung bestmöglich ist, sind Kreise ungerader Länge und vollständige Graphen. Der Satz von Brooks zeigt aber, dass dies auch die einzigen Beispiele sind. Für jeden zusammenhängenden Graphen, der kein Kreis ungerader Länge oder vollständig ist, ist seine chromatische Zahl höchstens so groß wie sein Maximalgrad.
Aber auch viele Probleme aus anderen Bereichen der Mathematik selber lassen sich als Graphenfärbungsprobleme formulieren.
Der Satz von Vizing besagt, dass der chromatische Index eines Graphen mindestens so groß wie sein Maximalgrad aber höchstens eins größer als dieser ist. Obwohl der Maximalgrad leicht bestimmbar ist und somit nur zwei mögliche Werte für den chromatischen Index eines Graphen in Frage kommen, ist das Problem zu einem gegebenen Graphen seinen chromatischen Index zu bestimmen ebenfalls NP-schwer.
Anwendungen
In der selben Weise können Register-Zuweisungs-Probleme in Prozessoren,
Bandbreiten-Zuweisung-Probleme und viele weitere Probleme als Graphenfärbungsprobleme formuliert werden.Kantenfärbungen
Ist G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und f eine Abbildung von E in die Menge der natürlichen Zahlen, so nennt man f eine Kantenfärbung von G. Man nennt f gültig, falls für je zwei beliebige benachbarte Kanten e1 und e2 gilt f(e1)≠f(e2) und sagt G ist k-kantenfärbbar, falls es eine gültige Kantenfärbung von G gibt, so dass für alle e aus E gilt f(e)<k, d.h. f(e) ist Element der k-elementigen Menge {0,...,k-1}. Das kleinste k, für das G k-kantenfärbbar ist, nennt man chromatischer Index oder Kantenfärbungszahl.Literatur