Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:33] – [Weiterführende Fragen & Aufgaben] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:54] – [Weiterführende Fragen & Aufgaben] Frank Schiebel | ||
---|---|---|---|
Zeile 23: | Zeile 23: | ||
* Verwende dabei möglichst wenige Farben. | * Verwende dabei möglichst wenige Farben. | ||
* Ist es möglich, den Graphen mit k Farben zu färben? | * 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, | ||
+ | |||
+ | 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) | ||
+ | {{: | ||
+ | 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. | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | Die erste noch nicht benutzte Farbe ist grün. Daher wird der Knoten grün gefärbt. | ||
===== Weiterführende Fragen & Aufgaben ===== | ===== Weiterführende Fragen & Aufgaben ===== | ||
Zeile 59: | Zeile 76: | ||
Werden die Knoten in der angegebenen Reihenfolge bearbeitet, findet der Greedy-Algorithmus (Farbreihenfolge: | Werden die Knoten in der angegebenen Reihenfolge bearbeitet, findet der Greedy-Algorithmus (Farbreihenfolge: | ||
++++ | ++++ | ||
- | ===== Algorithmus ===== | ||
+ | ---- | ||
+ | {{: | ||
+ | === (A4) === | ||
- | ==== Beschreibung ==== | + | 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. |
+ | ++++ Lösung | | ||
+ | Es gibt 4< | ||
+ | ++++ | ||
- | 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. | + | ---- |
+ | {{:aufgabe.png? | ||
+ | === (A5) === | ||
- | Zunächst wird eine Reihenfolge festgelegt, in der die Farben verwendet werden sollen. | + | Für das Kartenfärbeproblem ist kein Algorithmus bekannt, der eine optimale Lösung bestimmt, ohne dabei alle Möglichkeiten auszuprobieren. Begründe |
- | z.B. Rot - Blau - Grün - Gelb - Lila - Orange | + | ++++ 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. |
- | Dann betrachtet man der Reihe nach alle Knoten. Für jeden Knoten | + | ++++ |
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A6) === | ||
+ | Erläutere, durch welche besondere Eigenschaft ein Graph, der eine Landkarte repräsentiert, | ||
+ | |||
+ | ++++ Lösung | | ||
+ | Der Graph eine Landkarte ist planar((https:// | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A7) === | ||
+ | |||
+ | **(A)** Eine Variante des Kartefärberoblems ist das **Kolonialproblem**: | ||
+ | |||
+ | ++++ Tipp: | | ||
+ | Stell dir folgende Situation vor: | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | * Können die Mutterländer mit 4 Farben gefärbt werden? | ||
+ | * Wie könnten eine Aufteilung | ||
+ | ++++ | ||
+ | |||
+ | ++++ Lösung | | ||
+ | {{ : | ||
+ | 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 | ||
+ | * Begründe anhand des Graphen, warum die Obergrenze von vier Farben | ||
+ | |||
+ | ++++ Tipp | | ||
+ | Die Mutterländer | ||
+ | ++++ | ||
+ | |||
+ | ++++ Lösung | | ||
+ | {{ : | ||
+ | |||
+ | Der Graph ist nicht mehr planar, also reichen 4 Farben nicht mehr aus. | ||
+ | ++++ | ||
+ | ===== Algorithmus: | ||
- | z.B. Der rot umrandete Knoten ist aktuell an der Reihe. Alle Nachbarknoten werden betrachtet und ihre Farben ermittelt. | ||
- | {{ : | ||
- | Die erste noch nicht benutzte Farbe ist grün. Daher wird der Knoten grün gefärbt. | ||
==== Pseudocode ==== | ==== Pseudocode ==== |