imported>Boehm: fix

2025-09-15T10:01:13Z

fix

Neue Seite

Eine '''Kantenfärbung''' ist eine Abbildung in der [[Graphentheorie]], die jeder [[Kante (Graphentheorie)|Kante]] eines [[Graph (Graphentheorie)|Graphen]] eine (symbolische) Farbe zuordnet. Je nach Kontext nennt man eine Kantenfärbung dann ''gültig'' oder ''zulässig'', wenn für jeden Knoten des Graphen gilt: Alle an einem Knoten anliegenden Kanten haben unterschiedliche Farben.

Der Begriff ist eng verwandt mit der [[Knotenfärbung]].

== Definition ==
[[Datei:Multigraph-edge-coloring.svg|mini|Ein [[Multigraph]] mit einer 9-Kantenfärbung.]]
[[Datei:Complete-edge-coloring.svg|mini|Eine Kantenfärbung des <math> K_8 </math> mit 7 Farben.]]
Für einen ungerichteten [[Graph (Graphentheorie)#Multigraph|Multigraphen]] <math>G=(V,E)</math> nennt man eine Abbildung <math>f\colon E \rightarrow C \subseteq \N</math> der Kantenmenge in die [[Natürliche Zahl|Menge der natürlichen Zahlen]] eine ''Kantenfärbung'' von <math>G</math>. Die Elemente aus <math>C</math> werden in diesem Zusammenhang ''Farben'' genannt. Man nennt <math>f</math> ''gültig'' oder ''zulässig'', falls für je zwei beliebige [[Nachbarschaft (Graphentheorie)|benachbarte]] (am gleichen Knoten [[Inzidenzmatrix|anliegende]]) Kanten <math>e_1</math> und <math>e_2</math> gilt, dass <math>f(e_1)\ne f(e_2)</math>. Besitzt <math>G</math> eine gültige Kantenfärbung <math>f</math>, so dass höchstens <math>k</math> Farben im [[Bild (Mathematik)|Bildbereich]] von <math>f</math> auftreten, nennt man <math>G</math> <math>k</math>-''kantenfärbbar''.

Das kleinste <math>k</math>, für das ein Graph <math>k</math>-kantenfärbbar ist, heißt '''chromatischer Index''', '''Kantenfärbungszahl''' oder auch '''kantenchromatische Zahl''' des Graphen <math>G</math> und wird meist mit <math>\chi'(G)</math> bezeichnet.

== Eigenschaften ==
Nach dem [[Satz von Vizing]] ist der [[Chromatischer Index|chromatische Index]] eines [[Einfacher Graph|einfachen Graphen]] <math>G</math> mindestens so groß wie sein [[Maximalgrad]], aber höchstens eins größer als dieser, also formal:

:<math>\Delta(G) \;\leq\; \chi^{\prime}(G) \;\leq\; \Delta(G) + 1</math>

[[Graph (Graphentheorie)|Graphen]] mit <math>\chi'(G)=\Delta\left(G\right)</math> nennt man '''Klasse-1-Graphen''', Graphen mit <math>\chi'\left(G\right)=\Delta\left(G\right)+1</math> nennt man '''Klasse-2-Graphen''', da die Abschätzung des Satzes nicht für [[Multigraph]]en gilt, werden Multigraphen Klasse-2-Graphen genannt, wenn <math>\chi'\left(G\right)>\Delta\left(G\right)</math> gilt. Zu entscheiden, ob ein Graph Klasse 1 oder Klasse 2 ist ([[Klassifizierungsproblem]]), ist [[NP-Vollständigkeit|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 [[Bipartiter Graph|bipartite Graphen]] ist <math> \chi'\left(G\right)=\Delta\left(G\right)</math>. Damit sind alle [[Bipartiter Graph|bipartiten Graphen]] Klasse-1-Graphen.

== Beispiel ==
Bei einem [[Zyklischer Graph|zyklischen Graphen]] können die [[Kante (Graphentheorie)|Kanten]] mit zwei Farben gefärbt sein, wenn die Länge des [[Zyklus (Graphentheorie)|Zyklus]] gerade ist. Wenn die Länge jedoch ungerade ist, werden drei Farben benötigt.

Ein [[vollständiger Graph]] <math>K_n</math> mit <math>n</math> Knoten ist mit <math>n - 1</math> Farben kantenfärbbar, wenn <math>n</math> eine gerade Zahl ist. Dies ist ein Sonderfall des [[Satz von Baranyai]]. Wenn <math>V(K_n)=\{0,\ldots,n-1\}</math>, so ist nämlich durch <math>f(\{k,n-1\})=k</math> und <math>f(\{i,j\})=k\iff i+j\equiv 2k\mod n-1</math> (<math>i,j\in\{0,\ldots,n-2\}\setminus\{k\}</math>) eine zulässige Färbung mit den Farben <math>0,\ldots,n-2</math> gegeben. Soifer liefert hierfür die folgende geometrische Konstruktion: Es werden <math>n</math> [[Knoten (Graphentheorie)|Knoten]] an den Ecken und in der Mitte eines [[Regelmäßiges Polygon|regelmäßigen Polygons]] mit <math>n - 1</math> Ecken betrachtet. Färben Sie für jede Farbklasse jeweils eine Kante von der Mitte zu einem der übrigen Knoten und alle zu dieser Kante senkrecht stehenden Kanten ein. Wenn <math>n</math> jedoch ungerade ist, werden <math>n</math> Farben benötigt: Jede Farbe kann nur für <math> \tfrac{n-1}{2}</math> Kanten verwendet werden, ein <math> \tfrac{1}{n}</math> der Gesamtmenge.<ref name=":0">{{cite journal
| last = Soifer | first = Alexander
| journal = Springer-Verlag
| title = The Mathematical Coloring Book
| year = 2008}}</ref>

Mehrere Autoren haben Kantenfärbungen der ungeraden Graphen untersucht, <math> n</math>-[[Regulärer Graph|reguläre Graphen]], in denen die [[Knoten (Graphentheorie)|Knoten]] Teams von <math> n - 1</math> Spielern darstellen, die aus einem Menge von <math> 2 \cdot n - 1</math> Spielern ausgewählt wurden, und in denen die [[Kante (Graphentheorie)|Kanten]] mögliche Begegnungen dieser Teams darstellen, mit einem Spieler als "ungerader Mann", der das Spiel leitet. Der Fall <math> n = 3</math> ergibt den bekannten [[Petersen-Graph]]en. Biggs erklärt das Problem für <math> n = 6</math>. 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 <math> O_n</math> finden. Wenn <math> n</math> gleich 3, 4 oder 8 ist, erfordert eine Kantenfärbung von <math> O_n</math> genau <math> n + 1</math> Farben, aber wenn <math> n</math> gleich 5, 6 oder 7 ist, werden nur <math> n</math> Farben benötigt.<ref>{{cite journal
| last = Biggs | first = Norman
| title = An edge-colouring problem
| journal = American Mathematical Monthly
| pages = 1018–1020
| volume = 79
| year = 1972
| issue = 9
| doi = 10.2307/2318076}}</ref>

== Zusammenhang mit Matchings ==
[[Datei:Class-2-planar-3-regular.svg|mini|Dieser 3-[[Regulärer Graph|reguläre]] [[Planarer Graph|planare Graph]] hat 16 [[Knoten (Graphentheorie)|Knoten]] und 24 [[Kante (Graphentheorie)|Kanten]], aber ein [[maximales Matching]] mit nur 7 Kanten. Daher sind 4 Farben für jede Kantenfärbung erforderlich.]]
Ein [[Matching (Graphentheorie)|Matching]] in einem [[Graph (Graphentheorie)|Graphen]] ist eine Menge von [[Kante (Graphentheorie)|Kanten]], von denen keine zwei [[benachbart]] sind. Ein [[perfektes Matching]] ist ein Matching, das Kanten enthält, die alle [[Knoten (Graphentheorie)|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 <math> \tfrac{m}{b}</math> verschiedene Farben verwenden muss, wenn ein Graph insgesamt <math> m</math> Kanten hat und höchstens <math> b</math> Kanten zu einer maximalen Übereinstimmung gehören können. Beispielsweise hat der in der Abbildung gezeigte 3-[[Regulärer Graph|reguläre]] [[Planarer Graph|planare Graph]] 16 Knoten und <math> m = 24</math> 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 <math> b = 7</math> Kanten. Daher ist die Anzahl der Farben, die für eine Kantenfärbung des Graphen benötigt werden, mindestens <math> \tfrac{m}{b} = \tfrac{24}{7}</math>, und weil die Anzahl der Farben eine [[ganze Zahl]] sein muss, sind es mindestens 4 Farben.

Für einen [[Regulärer Graph|regulären Graphen]] mit [[Knotengrad]] <math> k</math>, der kein [[perfektes Matching]] hat, kann diese Untergrenze verwendet werden, um zu zeigen, dass mindestens <math> k + 1</math> Farben benötigt werden. Dies gilt insbesondere für einen regulären Graphen mit einer ungeraden Anzahl von Knoten, zum Beispiel die ungeraden [[Vollständiger Graph|vollständigen Graphen]]. Für solche Graphen muss <math> k</math> nach dem [[Handschlaglemma]] selbst gerade sein. Die [[Ungleichung]] <math> \chi'\left(G\right) \geq \tfrac{m}{b}</math> 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 <math> m = 15</math> Kanten und hat ein perfektes Matching mit <math> b = 5</math> Kanten, aber er hat keine Kantenfärbung mit <math> \tfrac{m}{b} = \tfrac{15}{5} = 3</math> Farben.<ref name=":0" />

== Dualität zur Eckenfärbung ==
Die Bestimmung einer Kantenfärbung ist zur Bestimmung einer Knotenfärbung in der Weise dual, dass eine Kantenfärbung eines Graphen <math> G </math> genau eine [[Knotenfärbung]] des [[Kantengraph]]en <math>L(G)</math> ist. Daraus folgt, dass <math>\chi'(G) = \chi(L(G))</math> gilt. Die kantenchromatische Zahl eines [[Graph (Graphentheorie)|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 ==
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 ==
* {{Literatur
|Autor=[[Reinhard Diestel]]
|Titel=Graphentheorie
|Auflage=4.
|Verlag=Springer
|Ort=Berlin
|Datum=2010
|ISBN=978-3-642-14911-5
|Online=https://diestel-graph-theory.com/
|Umfang=354}}

== Weblinks ==
* [https://mathworld.wolfram.com/EdgeChromaticNumber.html Wolfram Mathworld: "Edge Chromatic Number"]
* [https://mathworld.wolfram.com/EdgeColoring.html Wolfram Mathworld: "Edge Coloring"]

== Einzelnachweise ==
<references />

{{SORTIERUNG:Kantenfarbung}}
[[Kategorie:Grundbegriff (Graphentheorie)]]

Kantenfärbung - Versionsgeschichte

imported>Boehm: fix