Färbung (Graphentheorie)

Färbung (Graphentheorie)
Darstellung einer kartographischen Färbung als Graph

Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu.

In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder „gültigen“ Färbungen (siehe unten), und versucht, Algorithmen zu entwickeln, die für einen vorgegebenen Graphen eine gültige Färbung mit möglichst wenig Farben finden. Probleme aus der diskreten Mathematik, aber auch außermathematische Fragestellungen lassen sich manchmal in ein Färbungsproblem übersetzen, daher ist die Existenz oder Nichtexistenz solcher Algorithmen auch außerhalb der Graphentheorie von Interesse.

Inhaltsverzeichnis

Knotenfärbungen

Ist G = (V,E) ein ungerichteter Graph ohne Mehrfachkanten und f: V \rightarrow \mathbb{N}_0 eine Abbildung der Kontenmenge in die Menge der natürlichen Zahlen, so nennt man f eine Knotenfärbung von G. Man nennt f gültig oder zulässig, falls je zwei beliebige benachbarte Knoten nicht dieselbe Farbe besitzen:

\forall v \in V: \forall w \in \Gamma (v): f(v)\ne f(w) \quad \text{(}\Gamma(v)\text{ bezeichnet die Menge der Nachbarn von }v\text{)}

In diesem Fall heißt G k-knotenfärbbar, falls es eine gültige Knotenfärbung von G gibt, so dass nur k Farben verwendet werden, also \forall v \in V: f(v) < k.

Eine zulässige Knotenfärbung eines Graphen ist 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).

Anzahl der Färbungen

Wenn ein Graph färbbar ist, gibt es eine kleinste Zahl k, sodass der Graph k-knotenfärbbar ist. Diese Zahl wird die chromatische Zahl oder Knotenfärbungszahl des Graphen genannt und meist mit χ(G) bezeichnet. Existiert für noch so viele Farben keine Färbung setzt man symbolisch \chi(G)=\infty.

Das chromatische Polynom eines Graphen gibt für jede Zahl k die Anzahl der zulässigen Färbungen an.

Kantenfärbungen

Ist G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und f eine Abbildung von E in die Menge der natürlichen Zahlen \mathbb{N}_0, so nennt man f eine Kantenfärbung von G. Man nennt f gültig' oder zulässig, 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. Das kleinste k, für das G k-kantenfärbbar ist, nennt man den chromatischen Index oder die Kantenfärbungszahl des Graphen G und wird meist mit χ'(G) bezeichnet.

Die Kantenfärbung eines Graphen G lässt sich als Knotenfärbung des Kantengraphen L(G) betrachten. Daraus folgt dass χ'(G) = χ(L(G)).

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, also formal:

\Delta(G) \;\leq\; \chi^{\prime}(G) \;\leq\; \Delta(G) + 1

Obwohl der Maximalgrad leicht zu bestimmen ist und der chromatische Index nur einen von zwei möglichen Werten annehmen kann, ist das Problem, für einen gegebenen Graphen genau diesen einen Wert zu bestimmen, ebenfalls NP-schwer.

Der allgemeine Fall

Die Bestimmung der chromatischen Zahl eines Graphen ist NP-schwer, das heißt, dass es – aus Sicht der Komplexitätstheorie – vermutlich keinen Algorithmus gibt, der dieses Problem effizient löst.

Das Knotenfärbungsproblem ist NP-vollständig.[1]

Der zurzeit praktisch beste 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 obere Schranke für die chromatische Zahl liefern.

Spezialfälle

Der Vier-Farben-Satz besagt, dass die chromatische Zahl eines planaren Graphen höchstens 4 ist. Trotzdem ist auch für planare Graphen das Bestimmen der chromatischen Zahl NP-schwer.

Das Entscheidungsproblem, ob ein gegebener Graph bipartit ist, besitzt lineare Zeitkomplexität, und ist zum Beispiel mit Tiefensuche lösbar. (Bipartite Graphen sind genau die Graphen mit chromatischer Zahl höchstens 2.)

Für perfekte Graphen existieren Polynomialzeitalgorithmen zur Berechnung der chromatischen Zahl.

Weitere Sätze

Der Greedy-Algorithmus liefert als obere Schranke für die chromatische Zahl eines Graphen den Maximalgrad des Graphen plus 1. Beispiele, die zeigen, dass diese Abschätzung bestmöglich ist, sind Kreise ungerader Länge und vollständige Graphen. Der Satz von Brooks zeigt, dass dies auch die einzigen Beispiele sind. Für jeden zusammenhängenden Graphen, der weder vollständig noch ein Kreis ungerader Länge ist, ist seine chromatische Zahl stets kleiner oder gleich dem Maximalgrad des Graphen.

Anwendungen

Stundenplanprobleme lassen sich als Graphfärbungsprobleme formulieren: Die Knoten des Graphen sind dabei die zu platzierenden Veranstaltungen, und eine Kante wird zwischen zwei Veranstaltungen eingefügt, die nicht gleichzeitig stattfinden können. In der Schule wären das z. B. Stunden, die von demselben Lehrer unterrichtet werden sowie Stunden in derselben Klasse. Die möglichen Farben entsprechen den zuteilbaren Zeitfenstern.

In gleicher Weise können beispielsweise Register-Zuweisungsprobleme in Prozessoren, Bandbreiten-Zuweisungsprobleme und auch viele Probleme aus der Mathematik als Graphenfärbungsprobleme formuliert werden.

Literatur

Einzelnachweise

  1. Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley. ISBN 8178083477, Seite 474.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Färbung — besteht für: Farbton Farbveränderung Färben, Farbe einbringen Färbelung, farbliche Gestaltung Zeichnung (Biologie), die natürliche, in einem bestimmten Muster verteilte Färbung bei Tieren und Pflanzen Färben eines histologischen Präparats; siehe… …   Deutsch Wikipedia

  • Färbung von Graphen — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Graphentheorie — Ungerichteter Graph mit sechs Knoten. Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht. Dadurch, dass einerseits viele algorithmische Probleme auf Graphen… …   Deutsch Wikipedia

  • Abstand (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Benachbart (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Inzidenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Schlinge (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Tiefe (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Valenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”