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

Kantenfärbung

Die chromatische Zahl

NP-Vollständigkeit

Vier-Farben-Satz

chromatisches Polynom