Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:29] – [Weiterführende Fragen & Aufgaben] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:35] – [Weiterführende Fragen & Aufgaben] Frank Schiebel | ||
---|---|---|---|
Zeile 49: | Zeile 49: | ||
++++ | ++++ | ||
+ | ---- | ||
+ | {{: | ||
+ | === (A3) === | ||
+ | |||
+ | Beschreibe eine Situation (Landkarte incl. Reihenfolge der Länder), in der der Greedy-Algorithmus mehr als 4 Farben erfordert. | ||
+ | |||
+ | ++++ Lösungsvorschlag | | ||
+ | {{ : | ||
+ | Werden die Knoten in der angegebenen Reihenfolge bearbeitet, findet der Greedy-Algorithmus (Farbreihenfolge: | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A4) === | ||
+ | |||
+ | 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< | ||
+ | ++++ | ||
===== Algorithmus ===== | ===== Algorithmus ===== | ||