Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [30.11.2022 21:20] – Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [30.11.2022 21:26] – [Modellierung] Frank Schiebel
@@ Zeile 6: / Zeile 6: @@
 {{:aufgabe.png?nolink  |}}
 === (A1) ===
+Färbe die Karte der Bundesländer nach der beschriebenen Regel.
 {{ :faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:deutschland.png |}}((Bundesländer in Deutschland, Stefan-Xp via Wikimedia Commons (Lizenz: CC BY-SA 3.0): https://de.wikipedia.org/wiki/Datei:Germany_blank_map.svg))
+===== Modellierung =====
+Die Ausgangssituation soll nun als Graph modelliert werden. Dabei stehen die Knoten für die Gebiete der Landkarte, zwei Knoten haben eine gemeinsame Kante, wenn Sie auf der Karte eine gemeinsame Grenzlinie haben.
+<WRAP center round box 90%>
+**Graphenfärbe-Problem**: Geben ist ein Graph. Färbe die Knoten des Graphen so, dass keine durch eine Kante verbundene Knoten die gleiche Farbe haben.
+</WRAP>
+**Varianten:**
+  * Verwende dabei möglichst wenige Farben.
+  * Ist es möglich, den Graphen mit k Farben zu färben?
+===== Algorithmus =====