Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 11:28] – Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [27.09.2024 12:32] (aktuell) – Marco Kuemmel
@@ Zeile 7: / Zeile 7: @@
 === (A1) ===
-Färbe die Karte der Bundesländer nach der beschriebenen Regel.
+Färbe die Karte der Bundesländer nach der beschriebenen Regel.\\
+Auf [[https://www.matheprisma.uni-wuppertal.de/Module/4FP/pages/node3.htm|dieser Internetseite]] lässt sich die Deutschlandkarte auch online einfärben.
 {{ :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 =====
@@ Zeile 23: / Zeile 25: @@
   * Verwende dabei möglichst wenige Farben.
   * Ist es möglich, den Graphen mit k Farben zu färben?
+===== Beschreibung eines Greedy-Algorithmus ======
+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.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A2) ===
+Teste das eben beschriebene Greedy-Verfahren an den Karten [[https://www.kippenbergs.de/de/mint-fourcolors|dieser Internetseite]].
 ===== Weiterführende Fragen & Aufgaben =====
@@ Zeile 31: / Zeile 55: @@
   * Ein bipartiter((https://de.wikipedia.org/wiki/Bipartiter_Graph)) Graph lässt sich mit zwei Farben färben.
   * Ein vollständiger Graph mit n Knoten benötigt n Farben.
-  * Ein Graph mit einer Clique((https://de.wikipedia.org/wiki/Clique_(Graphentheorie) )) aus m Knoten benötigt mindestens m Farben.
+  * Ein Graph mit einer Clique(([[https://de.wikipedia.org/wiki/Clique_(Graphentheorie)|Wikipedia: Clique]] )) aus m Knoten benötigt mindestens m Farben.
 </WRAP>
@@ Zeile 37: / Zeile 61: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A2) ===
+=== (A3) ===
 Begründe die obigen Aussagen.
@@ Zeile 49: / Zeile 73: @@
 ++++
-===== Algorithmus =====
+----
+{{:aufgabe.png?nolink  |}}
+=== (A4) ===
+Beschreibe eine Situation (Landkarte incl. Reihenfolge der Länder), in der der Greedy-Algorithmus mehr als 4 Farben erfordert.
-==== Beschreibung ====
+++++ Lösungsvorschlag |
+{{ :faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:karteii.png?300 |}}
+Werden die Knoten in der angegebenen Reihenfolge bearbeitet, findet der Greedy-Algorithmus (Farbreihenfolge: blau-rot-grün-gelb-lila) die gezeigte Lösung mit 5 Farben, da das Land 2 ungeschickterweise mit rot statt grün gefärbt wurden.
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A5) ===
-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.
+Landkarten lassen sich immer mit vier Farben einfärben((Die Wissenschaft hat lange nach einem Beweis für diese Aussage gesucht. 1852 wurde die Vermutung dieser Aussage aufgestellt. Bis heute gibt es keinen "einfachen", nachvollziehbaren Beweis. 1976 wurde die Aussage aber bewiesen, indem Computer zahlreiche knifflige Karten-Färbe-Probleme durchgerechnet haben.)). Bestimme die Anzahl der möglichen Färbungen (ohne Beachtung der Regel, dass Nachbarländer nicht die gleiche Farbe haben dürfen) einer Landkarte aus 20 Ländern mit 4 Farben.
-Zunächst wird eine Reihenfolge festgelegt, in der die Farben verwendet werden sollen.
+++++ Lösung |
+Es gibt 4<sup>20</sup> = ca. 1 Billion Möglichkeiten, wenn man die Bedingung nicht beachtet, dass zwei Nachbarländer verschieden gefärbt sein müssen.
+++++
-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 |}}
+{{:aufgabe.png?nolink  |}}
-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.
+=== (A6) ===
+Für das Kartenfärbeproblem ist kein Algorithmus bekannt, der eine optimale Lösung bestimmt, ohne dabei alle Möglichkeiten auszuprobieren. Begründe die Notwendigkeit eines Näherungsalgorithmus.
+++++ Lösung |
+Die Anzahl der Möglichkeiten steigt mit der Anzahl der Knoten **exponentiell**. Damit wird der Zeitbedarf schon bei relativ wenigen Knoten zu groß. Ein Näherungsalgorithmus arbeitet mit polynomieller Zeitbedart, liefert dafür allerdings nicht die optimale Lösung.
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A7) ===
+Erläutere, durch welche besondere Eigenschaft ein Graph, der eine Landkarte repräsentiert, die Beschränkung auf 4 Farben ermöglicht.
+++++ Lösung |
+Der Graph eine Landkarte ist planar((https://de.wikipedia.org/wiki/Planarer_Graph)). Durch die besondere Situation kann es keine nicht auflösbaren Kreuzungen der Kanten geben, da dies bedeuten würde, dass zwei verschiedene Ländergrenzen über Kreuz liegen.
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A8) ===
+**(A)** Eine Variante des Kartefärberoblems ist das **Kolonialproblem**: Einige Länder haben Kolonien, die nicht direkt mit dem Mutterland verbunden sind. Dabei sollen das Mutterland und seine Kolonien in der gleichen Farbe eingefärbt werden. Weiterhin soll gelten, dass benachbarte Länder bzw. Kolonien nicht in der gleichen Farbe eingefärbt werden dürfen. Es ist nicht bekannt, ob es eine Obergrenze der Anzahl der benötigten Farben gibt.
+++++ Tipp: |
+Stell dir folgende Situation vor:
+{{ :faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:kolonien_tipp.png?600 |}}
+  * Können die Mutterländer mit 4 Farben gefärbt werden?
+  * Wie könnten eine Aufteilung der Insel aussehen, die zu Problemen führen kann?
+++++
+++++ Lösung |
+{{ :faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:kolonien_lsg.png?600 |}}
+E kann nicht die Farbe von A,B oder D haben, da dies bei den Mutterländern nicht zulässig ist. Die Farbe von C ist auch nicht zulässig, da dies bei den Kolonien nicht erlaubt ist. Keines dieser vier Länder kann die gleiche Farbe haben, da sie oder ihre Kolonien untereinander benachbart sind. Daher wird eine 5. Farbe benötigt.
+++++
+**(B) Modellierung **
+  * Überführe die Karte in den dazugehörigen Graphen. Erläutere, wie Du die Forderung modellierst, dass das Mutterland und seine Kolonien in der gleichen Farbe gefärbt werden sollen.
+  * Begründe anhand des Graphen, warum die Obergrenze von vier Farben für eine Landkarte nicht mehr gilt.
+++++ Tipp |
+Die Mutterländer und ihre Kolonien werden durch einen einzigen Knoten repräsentiert.
+++++
+++++ Lösung |
+{{ :faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:kolonie_graph.png |}}
+Der Graph ist nicht mehr planar, also reichen 4 Farben nicht mehr aus.
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A9) ===
+Notiere den beschriebenen Algorithmus als Pseudocode und implementiere ihn selbst im Graphentester. Hinweise und Lösungsvorschläge findest du unten.
+===== Algorithmus: Pseudocode & Implementation =====
-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 ====