Färbung (Graphentheorie)

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 wenigen 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.

Knotenfärbungen

Eine gültige 4-Knotenfärbung eines Graphen. Mathematisch werden die unterschiedlichen Farben durch verschiedene natürliche Zahlen dargestellt

Ist $G=(V,E)$ ein ungerichteter Graph ohne Mehrfachkanten und $f\colon V\rightarrow C\subseteq \mathbb {N} _{0}$ eine Abbildung der Knotenmenge in die Menge der natürlichen Zahlen, so nennt man $f$ eine Knotenfärbung von $G$ . Die Elemente aus $C$ werden Farben genannt. Teils werden auch Abbildungen in beliebige abzählbare Mengen und nicht in die natürlichen Zahlen betrachtet. Dies ist aber nicht wichtig, notwendig ist bloß die Unterscheidbarkeit der Farben. 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)\neq f(w)\,,

wobei $\Gamma (v)$ die Menge der Nachbarn von $v$ bezeichnet.

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 $\left|C\right|=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.

Bei einer vollständigen Knotenfärbung existiert für jedes Paar $\{i,j\}$ von Farben eine Kante $\{x,y\}\in E(G)$ , sodass $x$ mit $i$ und $y$ mit $j$ gefärbt ist. Das heißt, für jedes Farbenpaar existieren benachbarte Knoten, die mit diesen Farben gefärbt sind.

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 chromatische Zahl oder Knotenfärbungszahl des Graphen genannt und meist mit $\chi$ $(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 $k$ -Färbungen an.

Bandbreite

Ist $(V,E)$ ein einfacher Graph mit $n$ Knoten und $f\colon V\to \{1,\ldots ,n\}$ eine eineindeutige Färbung der Knoten, dann bezeichnet

\max _{\{x,y\}\in E}|f(x)-f(y)|

die Bandbreite (englisch bandwidth) des Graphen bezüglich $f$ und

\min _{f}\max _{\{x,y\}\in E}|f(x)-f(y)|

die Bandbreite des Graphen. Die Ermittlung der Bandbreite ist eines der wenigen graphentheoretischen Probleme, das auch für Bäume NP-vollständig ist.

Eigenschaften der chromatischen Zahl

Das Zuweisen unterschiedlicher Farben zu unterschiedlichen Knoten ergibt immer eine korrekte Färbung, also gilt

1\leq \chi (G)\leq n

Die einzigen Graphen, die 1-färbbar sind, sind kantenlose Graphen. Ein vollständiger Graph $K_{n}$ mit $n$ Knoten erfordert $\chi (K_{n})=n$ Farben. Bei einer optimalen Färbung muss zwischen jedem Paar von Farbklassen mindestens eine der $m$ Kanten des Graphen vorhanden sein, also gilt

\chi (G)(\chi (G)-1)\leq 2m

\chi (G)\leq {\frac {1}{2}}+{\sqrt {2m+{\frac {1}{4}}}}

Wenn $G$ eine Clique der Größe $k$ enthält, werden mindestens $k$ Farben benötigt, um diese Clique zu färben, das heißt, die chromatische Zahl ist mindesten so groß wie die Cliquenzahl:

\chi (G)\geq \omega (G)

Jeder $k$ -partite Graph ist $k$ -knotenfärbbar, die Partitionsklassen entsprechen hier genau den Farben. Insbesondere sind alle bipartiten Graphen 2-färbbar. Jeder 2-färbbare Graph ist jedoch auch bipartit. Da man einen Graph in Polynomialzeit auf Bipartitheit testen kann, ist demnach auch das 2-Färbbarkeitsproblem in Polynomialzeit lösbar.

Nach dem Vier-Farben-Satz ist jeder planare Graph 4-färbbar.

Eine gierige Färbung zeigt, dass jeder Graph mit einer Farbe mehr als dem maximalen Knotengrad gefärbt werden kann:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi(G) \le \Delta(G) + 1 }

Vollständige Graphen haben Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi(G) = n } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta(G) = n - 1 } , und ungerade Zyklen haben Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi(G) = 3 } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta(G) = 2 } , daher ist diese Grenze für diese Graphen die bestmögliche. In allen anderen Fällen kann die Grenze leicht verbessert werden. Der Satz von Brooks zeigt, dass dies auch die einzigen Beispiele sind: Für jeden zusammenhängenden Graphen, der weder vollständig noch ein Zyklus ungerader Länge ist, ist seine chromatische Zahl stets kleiner oder gleich dem Maximalgrad des Graphen.

Grenzen für die chromatische Zahl

Hoffmans Grenze

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W } eine reelle symmetrische Matrix, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_{i,j} = 0 } ist, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (i, j) } keine Kante von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist. Definiert man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi_W(G) = 1 - \tfrac{\lambda_{\max}(W)}{\lambda_{\min}(W)}} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda_{\max}(W)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda_{\min}(W)} die größten und kleinsten Eigenwerte von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W } sind. Definiert man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi_H(G) = \max_W \chi_W(G)} , dann gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi_H(G)\leq \chi(G) }

Vektorchromatische Zahl

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W } eine positive semidefinitive Matrix, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_{i,j} = 0 } , wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (i, j) } eine Kante von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist. Definiert man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi_V(G)} als das kleinste Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} , für das eine solche Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W } existiert. Dann gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi_V(G)\leq \chi(G) }

Lovász-Zahl

Die Lovász-Zahl eines komplementären Graphen ist auch eine Untergrenze für die chromatische Zahl:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \vartheta(\bar{G}) \leq \chi(G) }

Gebrochene chromatische Zahl

Die gebrochene chromatische Zahl eines Graphen ist auch eine Untergrenze für die chromatische Zahl:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi_f(G) \leq \chi(G) }

Diese Grenzen sind wie folgt geordnet:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi_H(G) \leq \chi_V(G) \leq \vartheta(\bar{G}) \leq \chi_f(G) \leq \chi(G) }

Topologische untere Schranken

Es gibt diverse topologische untere Schranken an die chromatische Zahl. Die wahrscheinlich bekannteste stammt von Lovász.

Grenzen für den chromatischen Index

Eine Kantenfärbung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G } ist eine Knotenfärbung seines Kantengraphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(G)} und umgekehrt, also gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi'(G)=\chi(L(G)) }

Es besteht eine starke Beziehung zwischen der Kantenfärbbarkeit und dem maximalen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta(G)} des Graphen. Da alle Kanten, die mit demselben Knoten verbunden sind, ihre eigene Farbe benötigen, gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi'(G) \ge \Delta(G)}

Außerdem gelten folgende Sätze:

Satz von König: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi'(G) = \Delta(G)} , wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G } bipartit ist.

Satz von Vizing: Ein Graph mit maximalem Grad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta} hat die kantenchromatische Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta+1} .

Knotenfärbungen planarer Graphen

Darstellung einer kartographischen Färbung als Graph. Jedem Land wird ein Knoten zugewiesen, die Knoten werden durch Kanten verbunden genau dann wenn die beiden Länder benachbart sind.

Eines der klassischen Probleme der Graphentheorie ist die Frage, wie viele Farben man minimal braucht, um eine Landkarte so zu färben, dass je zwei aneinandergrenzende Länder nicht dieselbe Farbe haben. Dieses Problem lässt sich leicht in ein Knotenfärbungsproblem überführen (siehe Abbildung). Die graphentheoretisch äquivalente Frage lautet also: Was ist die chromatische Zahl eines planaren Graphen? Der Vier-Farben-Satz besagt, dass die chromatische Zahl eines planaren Graphen höchstens 4 ist. Enthält der Graph kein Dreieck, so ist er sogar 3-Knoten-färbbar. Trotzdem ist auch für planare Graphen das Bestimmen der chromatischen Zahl NP-schwer.

Algorithmen

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. Die Bestimmung der chromatischen Zahl ist auch eines der Probleme von Karps 21 NP-vollständigen Problemen und damit eines der ersten Probleme, für die die NP-Vollständigkeit gezeigt wurde. Ausnahmen sind bipartite Graphen und perfekte Graphen. Das Entscheidungsproblem, ob ein gegebener Graph bipartit ist, besitzt lineare Zeitkomplexität, und ist zum Beispiel mit Tiefensuche lösbar. Bei perfekten Graphen existieren Polynomialzeitalgorithmen zur Berechnung der chromatischen Zahl.

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

Der zurzeit praktisch beste Algorithmus zur Bestimmung einer Knotenfärbung 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.

Anwendungen

Stundenplanprobleme lassen sich als Graphenfä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.

Der Rot-Schwarz-Baum wird durch Knotenfärbung balanciert.

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

Verallgemeinerungen

Eine Verallgemeinerung der Knotenfärbung ist der Begriff der Listenfärbung. Hierbei wird jedem Knoten eine „Liste“ von verfügbaren Farben zugeteilt und der Graph soll nun eine gültige Färbung aus diesen Listen erhalten. Des Weiteren gibt es die Totalfärbung, bei der sowohl Knoten als auch Kanten gefärbt werden sollen.

Literatur

Reinhard Diestel: Graphentheorie. Springer-Verlag, Heidelberg, Deutschland 2000, ISBN 3-540-67656-2. http://diestel-graph-theory.com/german/index.html
Anuj Mehrotra, Michael A. Trick: A column generation approach for graph coloring. In: INFORMS Journal on Computing. 8, Nr. 4, 1996, S. 344–354. doi:10.1287/ijoc.8.4.344.

Einzelnachweise

↑ 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

Andy Theiler: PHP-Implementierung des Kantenfärbungs Algorithmus (Spielplan generieren)

[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.

[1]

Anonym

Suche

Färbung (Graphentheorie)

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis