Eine Kantenfärbung ist eine Abbildung in der Graphentheorie, die jeder Kante eines Graphen eine (abstrakte) Farbe zuordnet. Eine Kantenfärbung heißt gültig oder zulässig, wenn für jeden Knoten des Graphen gilt: Alle am Knoten anliegenden Kanten haben unterschiedliche Farben.
Der Begriff ist eng verwandt mit der Knotenfärbung.
Definition Bearbeiten
Für einen ungerichteten Multigraphen nennt man eine Abbildung der Kantenmenge in die Menge der natürlichen Zahlen eine Kantenfärbung von . Die Elemente aus werden in diesem Zusammenhang Farben genannt. Man nennt gültig oder zulässig, falls für je zwei beliebige benachbarte Kanten und gilt, dass . Besitzt eine gültige Kantenfärbung , so dass höchstens Farben im Bildbereich von auftreten, nennt man -kantenfärbbar.
Das kleinste , für das ein Graph -kantenfärbbar ist, heißt chromatischer Index, Kantenfärbungszahl oder auch kantenchromatische Zahl des Graphen und wird meist mit bezeichnet.
Eigenschaften Bearbeiten
Nach dem Satz von Vizing ist der chromatische Index eines einfachen Graphen mindestens so groß wie sein Maximalgrad, aber höchstens eins größer als dieser, also formal:
Graphen mit nennt man Klasse-1-Graphen, Graphen mit nennt man Klasse-2-Graphen, da die Abschätzung des Satzes nicht für Multigraphen gilt, werden Multigraphen Klasse-2-Graphen genannt, wenn gilt. Zu entscheiden, ob ein Graph Klasse 1 oder Klasse 2 ist (Klassifizierungsproblem), ist NP-vollständig. Das heißt, 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, NP-schwer.
Für bipartite Graphen ist . Damit sind alle bipartiten Graphen Klasse-1-Graphen.
Beispiel Bearbeiten
Bei einem zyklischen Graphen können die Kanten mit zwei Farben gefärbt sein, wenn die Länge des Zyklus gerade ist. Wenn die Länge jedoch ungerade ist, werden drei Farben benötigt.
Ein vollständiger Graph mit Knoten ist mit Farben kantenfärbbar, wenn eine gerade Zahl ist. Dies ist ein Sonderfall des Satz von Baranyai. Wenn , so ist nämlich durch und () eine zulässige Färbung mit den Farben gegeben. Soifer liefert hierfür die folgende geometrische Konstruktion: Es werden Knoten an den Ecken und in der Mitte eines regelmäßigen Polygons mit Ecken betrachtet. Färben Sie für jede Farbklasse jeweils eine Kante von der Mitte zu einen der übrigen Knoten und alle zu dieser Kante senkrecht stehenden Kanten ein. Wenn jedoch ungerade ist, werden Farben benötigt: Jede Farbe kann nur für Kanten verwendet werden, ein der Gesamtmenge.
Mehrere Autoren haben Kantenfärbungen der ungeraden Graphen untersucht, -reguläre Graphen, in denen die Knoten Teams von Spielern darstellen, die aus einem Menge von Spielern ausgewählt wurden, und in denen die Kanten mögliche Begegnungen dieser Teams darstellen, mit einem Spieler als "ungerader Mann", der das Spiel leitet. Der Fall ergibt den bekannten Petersen-Graphen. Biggs erklärt das Problem für . Die Spieler möchten einen Zeitplan für diese Begegnungen finden, so dass jedes Team jedes seiner 6 Spiele an verschiedenen Wochentagen spielt, wobei alle Teams sonntags frei haben. Das heißt, sie formalisieren das Problem mathematisch und möchten eine 6-Kantenfärbung des 6-regulären ungeraden Graphen finden. Wenn gleich 3, 4 oder 8 ist, erfordert eine Kantenfärbung von genau Farben, aber wenn gleich 5, 6 oder 7 ist, werden nur Farben benötigt.
Zusammenhang mit Matchings Bearbeiten
Ein Matching in einem Graphen ist eine Menge von Kanten, von denen keine zwei benachbart sind. Ein perfektes Matching ist ein Matching, das Kanten enthält, die alle Knoten des Graphen berühren, und ein maximales Matching ist ein Matching, das so viele Kanten wie möglich enthält. Bei einer Kantenfärbung darf die Menge von Kanten mit einer Farbe nicht benachbart sein, damit sie ein Matching bilden. Das heißt, eine gültige Kantenfärbung ist dasselbe wie eine Aufteilung des Graphen in disjunkte Matchings.
Wenn die Größe eines maximalen Matching in einem bestimmten Graphen klein ist, sind viele Matchings erforderlich, um alle Kanten des Graphen abzudecken. Anders ausgedrückt bedeutet das, dass jede Kantenfärbung des Graphen mindestens verschiedene Farben verwenden muss, wenn ein Graph insgesamt Kanten hat und höchstens Kanten zu einer maximalen Übereinstimmung gehören können. Beispielsweise hat der in der Abbildung gezeigte 3-reguläre planare Graph 16 Knoten und Kanten. In diesem Graphen kann es kein perfektes Matching geben. Wenn der mittlere Knoten in einem Matching enthalten ist, können die verbleibenden Knoten in drei verschiedenen Zusammenhangskomponenten mit vier, fünf und fünf Knoten gruppiert werden, und die Komponenten mit einer ungeraden Anzahl von Knoten können keine perfekten Matchings enthalten. Der Graph hat jedoch maximale Matchings mit Kanten. Daher ist die Anzahl der Farben, die für eine Kantenfärbung des Graphen benötigt werden, mindestens , und weil die Anzahl der Farben eine ganze Zahl sein muss, sind es mindestens 4 Farben.
Für einen regulären Graphen mit Knotengrad , der kein perfektes Matching hat, kann diese Untergrenze verwendet werden, um zu zeigen, dass mindestens Farben benötigt werden. Dies gilt insbesondere für einen regulären Graphen mit einer ungeraden Anzahl von Knoten, zum Beispiel die ungeraden vollständigen Graphen. Für solche Graphen muss nach dem Handschlaglemma selbst gerade sein. Die Ungleichung erklärt jedoch nicht vollständig den chromatischen Index jedes regulären Graphen, weil es reguläre Graphen gibt, die perfekte Matchings haben, aber nicht k-kantenfärbbar sind. Zum Beispiel ist der Petersen-Graph regulär mit Kanten und hat ein perfektes Matching mit Kanten, aber er hat keine Kantenfärbung mit Farben.
Dualität zur Eckenfärbung Bearbeiten
Die Bestimmung einer Kantenfärbung ist zur Bestimmung einer Knotenfärbung in der Weise dual, dass eine Kantenfärbung eines Graphen genau eine Knotenfärbung des Kantengraphen ist. Daraus folgt, dass gilt. Die kantenchromatische Zahl eines Graphen ist also genau die chromatische Zahl des Kantengraphen. Trotz dieses engen Zusammenhangs sind die Probleme unterschiedlich schwer zu lösen und die verfügbaren Abschätzungen unterscheiden sich deutlich.
Verallgemeinerungen Bearbeiten
Eine wesentliche Verallgemeinerung der Kantenfärbung ist der Begriff der Listenfärbung. Hier wird für jede Kante (oder jeden Knoten) eine Liste mit verfügbaren Farben vorgegeben und der Graph soll nun eine gültige Kantenfärbung aus diesen Listen erhalten. Des Weiteren gibt es die Totalfärbung, bei der sowohl Knoten als auch Kanten gefärbt werden sollen.
Literatur Bearbeiten
- Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S., diestel-graph-theory.com).
Weblinks Bearbeiten
Einzelnachweise Bearbeiten
- ↑ Alexander Soifer: The Mathematical Coloring Book. In: Springer-Verlag. 2008.
- Norman Biggs: An edge-colouring problem. In: American Mathematical Monthly. 79. Jahrgang, Nr. 9, 1972, S. 1018–1020, doi:10.2307/2318076.