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 [06.12.2022 12:24] – [Pseudocode] 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 =====
+==== Beschreibung ====
+Der hier beschriebene Algorithmus findet nicht die perfekte Lösung, d.h. die minimale Anzahl an Farben, aber eine gute Näherungslösung. Er arbeitet dabei nach dem Greedy-Verfahren, er wählt für ein Land die momentan am besten erscheinende Lösung.
+Zunächst wird eine Reihenfolge festgelegt, in der die Farben verwendet werden sollen.
+z.B. Rot - Blau - Grün - Gelb - Lila - Orange - Braun (es müssen ausreichend viele Farben sein)
+{{:faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:karte.png |}}
+Dann betrachtet man der Reihe nach alle Knoten. Für jeden Knoten wird dann Folgendes gemacht: Man schaut jeden der Nachbarknoten an und merkt sich, dass seine Farbe schon verwendet wurde. Dann wählt man aus der Liste der Farben die erste noch nicht benutzte Farbe aus und färbt den Knoten in dieser Farbe.
+z.B. Der rot umrandete Knoten ist aktuell an der Reihe. Alle Nachbarknoten werden betrachtet und ihre Farben ermittelt.
+{{ :faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:auswahl_416.png|}}
+Die erste noch nicht benutzte Farbe ist grün. Daher wird der Knoten grün gefärbt.
+==== Pseudocode ====
+++++ Pseudocode |
+<code>
+Kartenfärbung:
+Wiederhole für jeden Knoten k des Graphen
+  Wiederhole für jede Farbe der Farbliste
+     Setze die Farbe auf "unbenutzt"
+  Ende-Wiederhole
+  Wiederhole für jeden Nachbarknoten n von k
+     Betrachte die Farbe des Knoten n
+     Setze diese Farbe auf "benutzt"
+  Ende-Wiederhole
+  Wiederhole für jede Farbe der Farbliste
+     Falls die Farbe "unbenutzt" ist
+       Färbe den Knoten k mit dieser Farbe
+       Brich die Schleife ab
+     Ende-Falls
+  Ende-Wiederhole
+Ende-Wiederhole
+</code>
+++++
+==== Beispielimplementation im Graphentester ====
+++++ Beispielimplementation |
+<code java>
+List<Knoten> knoten = g.getAlleKnoten();
+for (Knoten aktuellerKnoten: knoten) {
+  boolean[] farbenliste = new boolean[g.getAnzahlKnoten()+1];
+  for (int i=0; i < farbenliste.length; i++){
+    farbenliste[i]=false;
+  }
+  List<Knoten> nachbarn = g.getNachbarknoten(aktuellerKnoten);
+  for (Knoten k : nachbarn){
+    farbenliste[k.getFarbe()]=true;
+  }
+  for (int i=1; i<farbenliste.length; i++){
+    if (!farbenliste[i]) {
+      aktuellerKnoten.setFarbe(i);
+      break;
+    }
+  }
+}
+</code>
+++++