Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDonnerstag, 27. Juni 2019 

Färbung von Graphen


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

Inhaltsverzeichnis

Definitionen

Eine Knotenfärbung bzw. einfach Färbung eines ungerichteten Graphen G =( V E ) ordnet jedem Knoten aus V eine natürliche Zahl zu die auch genannt wird. Eine Färbung heißt zulässig falls je zwei benachbarten Knoten eine unterschiedliche Farbe zugewiesen wird.

Anders formuliert ist also eine zulässige eines Graphen eine Partition seiner Knotenmenge in unabhängige Mengen (eine der Knotenmenge V eines Graphen heißt unabhängig falls sie zwei benachbarten Knoten enthält).

Eine Färbung die k verschiedene Farben verwendet heißt k -Färbung. Das kleinste k heißt chromatische Zahl .

Ein Graph der 2-färbbar ist heißt bipartit .

Der allgemeine Fall

Das Problem zu entscheiden ob ein G k -färbbar ist ist NP-schwer d.h. die Bestimmung der chromatischen Zahl Graphen ist im Allgemeinen ein hartes Problem. zur Zeit praktisch beste Algorithmus beruht auf Spalten-Generierungs-Ansatz (siehe Literatur). Weiterhin gibt es viele die nach bestimmten Methoden gute Färbungen suchen somit im Erfolgsfall eine obere Schranke für chromatische Zahl liefern.

Spezialfälle

Der Vier-Farbensatz besagt dass die chromatische Zahl eines planaren Graphen höchstens 4 ist. Trotzdem ist auch planare Graphen das Entscheidungsproblem ob er k -färbbar ist NP-schwer .

Das Entscheidungsproblem ob ein gegebener Graph bipartit ist besitzt lineare Zeitkomplexität und ist zum Beispiel mit Tiefensuche lösbar.

Für bestimmte Spezialfälle (z.B. Wälder ) liefern bestimmte Färbungsheuristiken (z.B. der Greedy-Algorithmen) Färbungen.

Weitere Sätze

Der Greedy-Algorithmus liefert als obere Schranke die chromatische Zahl eines Graphen den Maximalgrad des Graphen plus 1. Beispiele die dass diese Abschätzung bestmöglich ist sind Graphen Kreisen ungerader Länge und vollständige Graphen . Der Satz von Brooks zeigt aber dies auch die einzigen Beispiele sind. Für zusammenhängenden Graphen der keine Kreise ungerader Länge enthält nicht vollständig ist ist seine chromatische Zahl stets oder gleich dem Maximalgrad des Graphen.

Anwendungen

Stundenplanprobleme lassen sich als Graphfärbungsprobleme formulieren: Die des Graphen sind dabei die zu platzierenden und eine Kante wird zwischen zwei Veranstaltungen die nicht gleichzeitig stattfinden können (in der wären das z.B. Stunden die von demselben unterrichtet werden sowie Stunden in derselben Klasse). möglichen Farben entsprechen den zuteilbaren Zeitfenstern.

In gleicher Weise können beispielsweise Register-Zuweisungs-Probleme Prozessoren Bandbreiten-Zuweisung-Probleme und auch viele andere Probleme der Mathematik als Graphenfärbungsprobleme formuliert werden.

Kantenfärbungen

Ist G =( V E ) ein ungerichteter Graph ohne Mehrfachkanten und f eine Abbildung von E in die Menge der natürlichen Zahlen nennt man f eine Kantenfärbung von G . Man nennt f gültig falls für je zwei beliebige benachbarte Kanten e 1 und e 2 gilt f ( e 1 )≠ f ( e 2 ) und sagt G ist k-kantenfärbbar falls es eine gültige Kantenfärbung von G gibt so dass für alle e aus E gilt f ( e )< k also <math>\forall e \in E 0\leq < k</math>. Das kleinste k für das G k -kantenfärbbar ist nennt man den chromatischer Index oder die Kantenfärbungszahl des Graphen G .

Der Satz von Vizing besagt dass chromatische Index eines Graphen mindestens so groß wie Maximalgrad aber höchstens eins größer als dieser also formal:

<math>GRAD_{max}(G) \leq \textit{CHROMATISCHERINDEX}(G) \leq GRAD_{max}(G) + 1</math>
Obwohl der Maximalgrad leicht zu bestimmen und der chromatische Index nur einen von möglichen Werten annehmen kann ist das Problem einen gegebenen Graphen genau diesen einen Wert bestimmen ebenfalls NP-schwer .

Literatur

  1. Anuj Mehrotra Michael A. Trick: A column generation approach for graph coloring . INFORMS Journal on Computing Vol. 8 4 (1996) Seiten 344-354. Online: http://mat.gsia.cmu.edu/trick/color.ps



Bücher zum Thema Färbung von Graphen

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Knotenf%E4rbung.html">Färbung von Graphen </a>