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:28] – Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:37] – [Algorithmus] 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 31: | Zeile 48: | ||
* 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 66: | ||
++++ | ++++ | ||
- | ===== Algorithmus ===== | + | ---- |
+ | {{: | ||
+ | === (A3) === | ||
+ | Beschreibe eine Situation (Landkarte incl. Reihenfolge der Länder), in der der Greedy-Algorithmus mehr als 4 Farben erfordert. | ||
- | ==== Beschreibung ==== | + | ++++ Lösungsvorschlag | |
+ | {{ : | ||
+ | Werden die Knoten in der angegebenen Reihenfolge bearbeitet, findet der Greedy-Algorithmus (Farbreihenfolge: | ||
+ | ++++ | ||
+ | ---- | ||
+ | {{: | ||
+ | === (A4) === | ||
- | Der hier beschriebene Algorithmus findet nicht die perfekte Lösung, d.h. die minimale | + | Landkarten lassen sich immer mit vier Farben einfärben. Bestimme |
- | Zunächst wird eine Reihenfolge festgelegt, in der die Farben verwendet werden sollen. | + | ++++ Lösung | |
+ | Es gibt 4< | ||
+ | ++++ | ||
- | z.B. Rot - Blau - Grün - Gelb - Lila - Orange - Braun (es müssen ausreichend viele Farben sein) | + | ---- |
- | {{:faecher: | + | {{:aufgabe.png? |
- | Dann betrachtet man der Reihe nach alle Knoten. | + | === (A5) === |
+ | |||
+ | Für das Kartenfärbeproblem ist kein Algorithmus bekannt, | ||
+ | ===== 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 ==== |