Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:50] – [Weiterführende Fragen & Aufgaben] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:56] (aktuell) – [Weiterführende Fragen & Aufgaben] Frank Schiebel | ||
---|---|---|---|
Zeile 110: | Zeile 110: | ||
=== (A7) === | === (A7) === | ||
- | Eine Variante des Kartefärberoblems ist das **Kolonialproblem**: | + | **(A)** |
++++ Tipp: | | ++++ Tipp: | | ||
Zeile 125: | Zeile 125: | ||
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. | 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, | ||
+ | * 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 | | ||
+ | {{ : | ||
+ | |||
+ | Der Graph ist nicht mehr planar, also reichen 4 Farben nicht mehr aus. | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A8) === | ||
+ | |||
+ | Notiere den beschriebenen Algorithmus als Pseudocode und implementiere ihn selbst im Graphentester. Hinweise und Lösungsvorschläge findest du unten. | ||
===== Algorithmus: | ===== Algorithmus: | ||