Färbungsprobleme

Wiki-Quelltext dieser Seite.

== Färbung ==

<!-- was ist überhaupt eine Färbung? (TODO: mathematische Definition, Bebilderung) -->

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