Färbungsprobleme

Motivation

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

Grundlegende Definitionen

Farbe

   Ein Element c heißt Farbe, wenn gilt: c \in Cund c ist von jedem beliebigen Element c' \in Cunterscheidbar.

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 Knoten des Graphen wird eine Farbe zugeordnet
• Kantenfärbung: jeder Kante 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 Färbung dieses Graphen.

Übung

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

Eichhorn_colored_graph_1Eichhorn_colored_graph_2Eichhorn_colored_graph_3

C = \{Bothe_red_32, Bothe_blue_32, Bothe_green_32\}

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

   Wenn je zwei beliebige benachbarte Knoten nicht dieselbe Farbe haben, dann heißt die dazugehörige Färbung gültig.
   \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 k-färbbar.
   

Übung

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

Eichhorn_petersen_graph

Die chromatische Zahl

NP-Vollständigkeit

Vier-Farben-Satz

chromatisches Polynom