Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [14.09.2024 10:41] – [Kartenfärben] Marco Kuemmel
+++ 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))
-Auf [[https://www.matheprisma.uni-wuppertal.de/Module/4FP/pages/node3.htm|dieser Internetseite]] lässt sich die Deutschlandkarte auch online einfärben.
 ===== Modellierung =====
@@ Zeile 41: / Zeile 42: @@
 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 55: / Zeile 61: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A2) ===
+=== (A3) ===
 Begründe die obigen Aussagen.
@@ Zeile 69: / Zeile 75: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A3) ===
+=== (A4) ===
 Beschreibe eine Situation (Landkarte incl. Reihenfolge der Länder), in der der Greedy-Algorithmus mehr als 4 Farben erfordert.
@@ Zeile 80: / Zeile 86: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A4) ===
+=== (A5) ===
-Landkarten lassen sich immer mit vier Farben einfärben. 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.
+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.
 ++++ Lösung |
@@ Zeile 90: / Zeile 96: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A5) ===
+=== (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.
+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  |}}
-=== (A6) ===
+=== (A7) ===
 Erläutere, durch welche besondere Eigenschaft ein Graph, der eine Landkarte repräsentiert, die Beschränkung auf 4 Farben ermöglicht.
@@ Zeile 109: / Zeile 115: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A7) ===
+=== (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.
@@ Zeile 144: / Zeile 150: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A8) ===
+=== (A9) ===
 Notiere den beschriebenen Algorithmus als Pseudocode und implementiere ihn selbst im Graphentester. Hinweise und Lösungsvorschläge findest du unten.