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:25] – [Modellierung] 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? | ||
| + | |||
| + | ===== 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 Graph lässt sich mit zwei Farben färben. | ||
| + | * Ein vollständiger Graph mit n Knoten benötigt n Farben. | ||
| + | * Ein Graph mit einer Clique aus m Knoten benötigt mindestens m Farben. | ||
| + | |||
| + | </ | ||
| ===== Algorithmus ===== | ===== Algorithmus ===== | ||
| Zeile 46: | Zeile 57: | ||
| ==== Pseudocode ==== | ==== Pseudocode ==== | ||
| - | 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, | + | |
| + | |||
| + | ++++ Pseudocode | | ||
| < | < | ||
| Zeile 70: | Zeile 83: | ||
| Ende-Wiederhole | Ende-Wiederhole | ||
| </ | </ | ||
| + | ++++ | ||
| ==== Beispielimplementation im Graphentester ==== | ==== Beispielimplementation im Graphentester ==== | ||
| Zeile 96: | Zeile 109: | ||
| </ | </ | ||
| ++++ | ++++ | ||
| - | ==== Implementation in Java ==== | + | |