Kantenfärbung - LinkFang.de





Kantenfärbung


In der Graphentheorie ist eine Kantenfärbung eine Abbildung, die jeder Kante eines Graphen eine (abstrakte) Farbe zuordnet. Der Begriff ist eng verwandt mit der Knotenfärbung.

Definition

Für einen ungerichteten Multigraph [math]G=(V,E)[/math] nennt man eine Abbildung [math]f\colon E \rightarrow C \subseteq \mathbb{N}_0[/math] der Kantenmenge in die 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 benachbarte 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 Kantenfärbung [math]f[/math], so dass höchstens k Farben im Bildbereich von [math]f[/math] auftreten, nennt man G k-kantenfärbbar.

Das kleinste k, für das [math]G[/math] k-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 chromatische Index eines 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]

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 Multigraphen gilt, werden Multigraphen Klasse‑2-Graphen genannt, wenn [math]\chi'\left(G\right)\gt\Delta\left(G\right)[/math] 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 [math] \chi'\left(G\right)=\Delta\left(G\right)[/math]. Damit sind alle bipartiten Graphen Klasse‑1-Graphen.

Dualität zur Eckenfärbung

Die Bestimmung einer Kantenfärbung ist zur Bestimmung einer Eckenfärbung in der Weise dual, dass eine Kantenfärbung eines Graphen [math] G [/math] genau eine Knotenfärbung des Kantengraphen [math]L(G)[/math] ist. Daraus folgt, dass [math]\chi'(G) = \chi(L(G))[/math] 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

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.

Weblinks

Literatur


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Kantenfärbung (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.