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:24] – [Pseudocode] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:36] – [Beschreibung] Frank Schiebel | ||
---|---|---|---|
Zeile 24: | Zeile 24: | ||
* Ist es möglich, den Graphen mit k Farben zu färben? | * Ist es möglich, den Graphen mit k Farben zu färben? | ||
- | ===== Algorithmus | + | ===== Weiterführende Fragen & Aufgaben |
+ | <WRAP center round tip 95%> | ||
+ | Für die Kolorierung von Graphen gelten folgende Sätze: | ||
+ | * Graphen, die sich mit einer Farbe färben lassen, haben keine Kante außer Schleifen. | ||
+ | * Ein bipartiter((https:// | ||
+ | * Ein vollständiger Graph mit n Knoten benötigt n Farben. | ||
+ | * Ein Graph mit einer Clique(([[https:// | ||
- | ==== Beschreibung ==== | + | </ |
+ | ---- | ||
+ | {{: | ||
+ | === (A2) === | ||
- | 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, | + | Begründe |
- | Zunächst wird eine Reihenfolge festgelegt, in der die Farben verwendet werden sollen. | + | ++++ Lösung | |
- | z.B. Rot - Blau - Grün - Gelb - Lila - Orange - Braun (es müssen ausreichend viele Farben sein) | + | * Sobald eine Kante vorhanden ist, sind zwei Knoten verbunden. Wenn dies verschiedene Knoten sind (also keine Schleife), dann dürfen diese nicht die selbe Farbe haben und es werden mindestens zwei Farben benötigt. |
- | {{: | + | * Wenn der Graph bipartit ist, dann zerfällt er in zwei Teilmenge der Knoten, die untereinander überhaupt nicht verbunden sind. Damit kann jede Teilmenge in einer einzigen Farbe eingefärbt werden. |
- | Dann betrachtet man der Reihe nach alle Knoten. | + | * Bei einem vollständigen Graphen ist jeder Knoten mit allen anderen verbunden. Daher muss jeder Knoten eine eigene Farbe haben. |
+ | * In einer Clique sind alle Knoten untereinander verbunden. Daher muss jeder Knoten der Clique eine eigene Farbe bekommen. | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (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 | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{:aufgabe.png? | ||
+ | === (A4) === | ||
+ | |||
+ | Landkarten lassen | ||
+ | |||
+ | ++++ 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 ===== | ||
- | 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 ==== |