Färbungsprobleme

Wiki-Quelltext dieser Seite.

== Motivation ==

* Einfärben einer Karte mit so wenig Farben wie möglich, wobei zwei einander angrenzende Länder nie dieselbe Farbe haben dürfen

[[Bild:Bothe_deutschland_vier_farben.gif]]

== Färbungstheorie ==

==== Farbe ====

    Ein Element $c$ heißt Farbe, wenn gilt: $c \in C$und $c$ ist von jedem beliebigen Element $c' \in C$unterscheidbar.

Aus mathematischer sowie programmiertechnischer Sicht ist es daher sinnvoll, Farben als Zahlen festzulegen. In graphischen Darstellungen sind hingegen
tatsächliche Farben wesentlich geeigneter. Theoretisch jedoch ist alles als Farbe zugelassen.

==== Färbung ====

Eine Färbung ist ein Zuordnung einer Farbe zu Elementen eines Graphen. Eine Knotenfärbung zum Beispiel ordnet jedem Knoten eine Farbe zu. Insgesamt
gibt es drei hauptsächliche Arten der Färbung eines Graphen:

* Knotenfärbung: jedem <b>Knoten</b> des Graphen wird eine Farbe zugeordnet
* Kantenfärbung: jeder <b>Kante</b> des Graphen wird eine Farbe zugeordnet
* Totalfärbung: sowohl jedem Knoten als auch jeder Kante wird eine Farbe zugeordnet

Desweiteren wird ausschließlich auf Knotenfärbung eingegangen. Definiert wird die Knotenfärbung (im folgenden nur Färbung) folgendermaßen:

    Wenn $G(V,E)$ ein ungerichteter Graph ohne Schleifen und Mehrfachkanten ist, dann ist $f: V \to C$ die <i>Färbung</i> dieses Graphen.

===== Übung =====
Sind die folgenden Graphen nach dieser Definition korrekt gefärbt?

[[Bild:Eichhorn_colored_graph_1]][[Bild:Eichhorn_colored_graph_2]][[Bild:Eichhorn_colored_graph_3]]

$C = \{$[[Bild:Bothe_red_32]]$, $[[Bild:Bothe_blue_32]]$, $[[Bild:Bothe_green_32]]$\}$

<popup name="Lösung">
* Graph 1: Ja
* Graph 2: Nein
* Graph 3: Ja
</popup>

Das Färben eines Graphen ist jedoch nicht beliebig möglich, wenn die Färbung <i>gültig</i> sein soll.

    Wenn je zwei beliebige benachbarte Knoten nicht dieselbe Farbe haben, dann heißt die dazugehörige Färbung <i>gültig</i>.
    $\forall v  \in V : \forall w \in \Gamma (v) : f(v) \ne f(w)$, wenn $\Gamma(v)$ die Menge aller Nachbarn von v bezeichnet.

Daraus ergibt sich auch die Notwendigkeit zu definieren, ob ich einen Graphen überhaupt gültig färben kann. Diese kann abgeleitet werden
aus dem Wissen über die Gültigkeit einer Färbung.

    Wenn es eine gültige Färbung $f$ gibt, die eine Anzahl $k$ an Farben verwendet, dann heißt der so gefärbte Graph $G$ <i>k-färbbar</i>.
    
===== Übung =====

Finden sie eine gültige Färbung für den nachstehenden Graphen. Schätzen sie auch, wie viele Farben sie mindestens brauchen werden.

[[Bild:Eichhorn_petersen_graph]]

<popup name="Lösung">
Eine Möglichkeit:
[[Bild:Eichhorn_petersen_colored]]
<br>
Für diesen Graphen existieren 120 Färbungen mit 3 Farben.
</popup>

==== Greedy-Algorithmus zum Färben eines Graphen ====

Um einen Graphen $G$ effizient gültig einzufärben, genügt ein "gieriger" Algorithmus. Dieser wird stets eine gültige Färbung zurückgeben, garantiert jedoch nicht, dass die Färbung mit der geringstmöglichen Anzahl an Farben auskommt.

<div style="background-color:#86DFFF" padding="8px">
* 0.
* 1.
* 2.
* 3.
* 4.
* 5.
</div>

==== Die chromatische Zahl ====

Für Anwendungsfälle sollten Färbungen mit möglichst wenig Farben auskommen. Die Mindestanzahl an benötigten Farben heißt chromatische Zahl.

    Die <i>chromatische Zahl</i> $\chi (G)$ ist die kleinste natürliche Zahl, für die der Graph $G$ eine gültige Färbung mit ebensovielen Farben besitzt.
    Gibt es für keine Anzahl an Farben eine gültige Färbung, so ist $\chi (G) = \infty$

Die höchste Anzahl an benötigten Farben, um einen beliebigen, schleifenfreien Graphen einzufärben, entspricht der Anzahl der vorhandenen Knoten.
Die Problem der Bestimmung der chromatischen Zahl ist jedoch Element der Menge der NP-Probleme, also wahrscheinlich nicht effizient zu lösen.

===== Spezialfälle =====

<!-- chrom. Zahl = 1 wenn keine Kanten -->
<!-- chrom. Zahl = 2 wenn bipartit -->
<!-- Best. chrom. Zahl = Best. k-partität --> 
<!-- planare Graphen mit max. 4 Farben (können weniger !!!!!) -->

==== Das chromatische Polynom ====

Das chromatische Polynom gibt an, wieviele Färbungen eines Graphen es für eine gegebene Menge an Farben gibt.

    Das <i>chromatische Polynom</i> $\chi (G,k)$ ist eine Formel, die die Menge an gültigen Färbungen des Graphen $G$ mit $k$ Farben berechnet.

Die chromatische Zahl ist das kleinste $k$, für dass das chromatische Polynom einen Wert $\ne$ 0 liefert.
<br>
<br>
Sowohl die chromatische Zahl als auch das chromatische Polynoms sind nicht besonders effektiv zu ermitteln.
Beide sind sogenannte NP-vollständige Probleme.

==== NP-schwere und NP-vollständige Probleme ====

<!-- Wir brauchen hier: Erklärung und Definition NP-schwer / NP-vollständig, Reduktion, Verweis auf Erfüllbarkeitsproblem der Aussagenlogik, P-NP-Problem, theoretische Ableitung, dass chrom. Zahl, chrom. Polyn und 3-Färbung eines Graphen mind. expotentiellen Aufwand haben, -->

== Anwendungen ==

<!-- Landkartenfärbung -->
<!-- Raid-Systeme -->
<!-- Scheduling -->