Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:36] – [Modellierung] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:46] – [Weiterführende Fragen & Aufgaben] Frank Schiebel
@@ Zeile 24: / Zeile 24: @@
   * Ist es möglich, den Graphen mit k Farben zu färben?
-==== Beschreibung eines Greedy-Algorithmus =====
+===== Beschreibung eines Greedy-Algorithmus ======
@@ Zeile 92: / Zeile 92: @@
 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.
-===== Algorithmus =====
+++++ 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) ===
+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  |}}
+=== (A7) ===
+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?
+++++
+===== Algorithmus: Pseudocode & Implementation =====