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 paarweise von jedem beliebigen Element $c' \in C$ unterscheidbar.

=== 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!) -->