Färbung von Graphen

Table of contents

1 Definitionen 2 Anwendungen 3 wichtige Aussagen und Sätze

Definitionen

Ist G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und P={V₁,...,V_k} eine Partition von V, so dass für jedes i aus {1,...,k} gilt, dass je zwei beliebige verschiedene Knoten v und w von V_i nicht benachbart sind, d.h. v und w sind durch keine Kante verbunden, so nennt man P eine Partition von G. Enthält P genau zwei Elemente, so nennt man P auch Bipartition. Ein Graph G=(V,E), der eine Partition P={V₁,...,V_k} besitzt nennt man k-partit. Die Partition mit genau |V| Elementen (d.h. die Partition, die nur einelementige Teilmengen enthält} ist eindeutig und man nennt sie trivial. Sie existiert offensichtlich in jedem ungerichteten Graphen ohne Mehrfachkanten, d.h. jeder Graph ist |V|-partit. Einen 2-partiten Graph, d.h. einen Graphen, der eine Bipartition besitzt, nennt man auch bipartit oder paar (siehe hierzu auch bipartiter Graph).

Ist P={V₁,...,V_k} eine Partition von G und ist für jedes i jeder Knoten aus V_i mit jedem Knoten aus V\\V_i benachbart, so nennt man G vollständig k-partit. Ist k=|V|, d.h. P ist trivial, so nennt man G auch einfach nur vollständig. Offensichtlich ist dies genau dann der Fall, wenn jeder Knoten mit jedem anderen Knoten benachbart ist.

Ist G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und f eine Abbildung von V in die Menge der natürlichen Zahlen, so nennt man f eine Knotenfärbung von G. Statt Knotenfärbung sagt man häufig auch einfach nur Färbung. Man nennt f gültig, falls für je zwei beliebige benachbarte Knoten v und w gilt, dass f(v)≠f(w) und sagt G ist k-knotenfärbbar, falls es eine gültige Knotenfärbung von G gibt, so dass für alle v aus V gilt f(v)<k, d.h. f(v) ist Element der k-elementigen Menge {0,...,k-1}. Statt k-knotenfärbbar sagt man häufig auch einfach nur k-färbbar oder k-chromatisch. Das kleinste k, für das G k-färbbar ist, nennt man chromatische Zahl, Knotenfärbungszahl, Färbungszahl oder Farbzahl.

Ein Graph ist offenbar genau dann k-partit, wenn er k-färbbar ist. Man bezeichnet daher oft auch eine Partition eines Graphen als Färbung und sagt, dass ein Graph G eindeutig k-färbbar ist, wenn es nur eine Partition von G mit k-Farben gibt.

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 e₁ und e₂ gilt f(e₁)≠f(e₂) 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.

Gerichtete Graphen und solche mit Mehrfachkanten sind nicht Gegenstand der Betrachtungen, da es nicht auf die Richtung der Kanten bzw. ihrer Vielfachheit ankommt.

Anwendungen

Stundenplanprobleme lassen sich als Graphfärbungsprobleme formulieren: der Graph entspricht der zu allozierenden Ressource, die möglichen Färbungen entsprechen den zuteilbaren Zeitfenstern.

wichtige Aussagen und Sätze

Mittels Tiefensuche lässt sich leicht ein linearer Algorithmus implementieren, der entscheiden kann, ob ein Graph bipartit ist oder nicht.

Das Problem, zu einem gegebenen Graphen seine chromatische Zahl zu bestimmen ist NP-schwer, d.h. es gibt aus Sicht der Komplexitätstheorie vermutlich keinen effizienten Algorithmus, der dieses Problem löst. Auch sind keine vernünftigen Approximationsalgorithmen bekannt. Im Gegenteil, es konnte gezeigt werden, dass unter gewissen Annahmen kein Approximationsalgorithmen existiert, der besser als irgend eine nichttriviale Funktion approximiert. Das Problem einen Graphen zu färben zählt damit zu den schwersten NP-Problemen überhaupt.

Für planare Graphen wurde gezeigt, dass ihre chromatische Zahl höchstens 4 ist. Dies ist auch als der Vier-Farbensatz bekannt. Auch für planare Graphen ist es NP-schwer die chromatische Zahl zu bestimmen.

Effizient entscheiden lässt sich dagegen die Frage, ob ein Graph bipartit ist. Ein einfacher Algorithmus, der auf Tiefensuche basiert, löst dieses Problem in Linerarzeit.

Es gibt verschiedene Greedy-Algorithmen die wenigstens für bestimmte Spezialfälle (Wälder oder bipartite Graphen) bestmöglich sind.

Der einfachste 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.

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.