Kantenfärbung - de.LinkFang.org

Kantenfärbung

In der Graphentheorie ist eine Kantenfärbung eine Abbildung, 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.

Inhaltsverzeichnis

Definition


Für einen ungerichteten Multigraph G=(V,E) nennt man eine Abbildung {\displaystyle f\colon E\rightarrow C\subseteq \mathbb {N} _{0}} der Kantenmenge in die Menge der natürlichen Zahlen eine Kantenfärbung von G. Die Elemente aus C werden in diesem Zusammenhang Farben genannt. Man nennt f gültig oder zulässig, falls für je zwei beliebige benachbarte Kanten e_{1} und e_{2} gilt, dass {\displaystyle f(e_{1})\neq f(e_{2})}. Besitzt G eine Kantenfärbung f, so dass höchstens k Farben im Bildbereich von f auftreten, nennt man G k-kantenfärbbar.

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

Eigenschaften


Nach dem Satz von Vizing ist der chromatische Index eines einfachen Graphen G mindestens so groß wie sein Maximalgrad, aber höchstens eins größer als dieser, also formal:

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

Graphen mit {\displaystyle \chi '(G)=\Delta \left(G\right)} nennt man Klasse‑1-Graphen, Graphen mit {\displaystyle \chi '\left(G\right)=\Delta \left(G\right)+1} nennt man Klasse‑2-Graphen (da die Abschätzung des Satzes nicht für Multigraphen gilt, werden Multigraphen Klasse‑2-Graphen genannt, wenn {\displaystyle \chi '\left(G\right)>\Delta \left(G\right)} 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 {\displaystyle \chi '\left(G\right)=\Delta \left(G\right)}. 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 G genau eine Knotenfärbung des Kantengraphen L(G) ist. Daraus folgt, dass {\displaystyle \chi '(G)=\chi (L(G))} 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.

Literatur


Weblinks





Kategorien: Grundbegriff (Graphentheorie)



Quelle: Wikipedia - https://de.wikipedia.org/wiki/Kantenfärbung (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 19.10.2019 10:22:56 CEST - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.