Färbungsprobleme

Wiki-Quelltext dieser Seite.

= 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

[[Bild:Bothe_deutschland_vier_farben.gif]]

== Grundlegende Definitionen ==

==== 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 \larr C$ die Färbung dieses Graphen.

=== Knotenfärbung ===

<!-- definitiv Unterscheidung notwendig, evtl. Konzentration auf Knotenfärbung im restlichen Vortrag (TODO: Eigenschaften Knotenfärbung, Anwendungsbeispiel, Algorithmus zum Färben eines Graphen, daher logischerweise auch Beispiel, Bebilderung)-->

=== Kantenfärbung ===

<!-- s.o. (TODO: Unterschiede zur Knotenfärbung hervorheben, Bebilderung) -->

== Die chromatische Zahl ==

<!-- WICHTIG! gibt an, wie viele Farben ich mindestens brauche, um einen Graphen zu färben aka: jedem Knoten ne andere Farbe geben ist billig! (TODO: Erklärung, Hinweis auf NP-Vollständigkeit und natürlich Bebilderung)-->

=== NP-Vollständigkeit ===

<!-- Und unsere Zuhörer im Chor: "was is des nu wieder"? Also: (TODO: Definition mit verständlicher Erklärung, Bebilderung [es gibt schöne Sachen auf der Wikipedia dazu], definitiv auf Abgrenzung zu P - und NP-Klassen hinweisen) -->

=== Vier-Farben-Satz ===

<!-- Eigentlich selbsterklärend an diesem Punkt (TODO: Definition, kleiner Hinweis das der Beweis eigentlich kacke ist ;) [siehe Wikipedia], Belandkartung, ein Beispiel mit neu gewonnenem Wissen) -->

== chromatisches Polynom ==

<!-- klingt nach Mathe, ist auch Mathe (TODO: Definition mit Formel, mal rechnen lassen, KEINE BEBILDERUNG, es gibt nämlich keine!) -->