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 31: | Zeile 31: | ||
* Ein bipartiter((https:// | * Ein bipartiter((https:// | ||
* Ein vollständiger Graph mit n Knoten benötigt n Farben. | * Ein vollständiger Graph mit n Knoten benötigt n Farben. | ||
- | * Ein Graph mit einer Clique(([[https:// | + | * Ein Graph mit einer Clique(([[https:// |
</ | </ | ||
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< | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A5) === | ||
+ | |||
+ | 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 ===== | ===== Algorithmus ===== | ||