Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- 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:33] – [Weiterführende Fragen & Aufgaben] Frank Schiebel
@@ Zeile 31: / Zeile 31: @@
   * Ein bipartiter((https://de.wikipedia.org/wiki/Bipartiter_Graph)) 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(([[https://de.wikipedia.org/wiki/Clique_(Graphentheorie|Wikipedia: Clique]] )) aus m Knoten benötigt mindestens m Farben.
+  * Ein Graph mit einer Clique(([[https://de.wikipedia.org/wiki/Clique_(Graphentheorie)|Wikipedia: Clique]] )) aus m Knoten benötigt mindestens m Farben.
 </WRAP>
@@ Zeile 49: / Zeile 49: @@
 ++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A3) ===
+Beschreibe eine Situation (Landkarte incl. Reihenfolge der Länder), in der der Greedy-Algorithmus mehr als 4 Farben erfordert.
+++++ Lösungsvorschlag |
+{{ :faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:karteii.png?300 |}}
+Werden die Knoten in der angegebenen Reihenfolge bearbeitet, findet der Greedy-Algorithmus (Farbreihenfolge: blau-rot-grün-gelb-lila) die gezeigte Lösung mit 5 Farben, da das Land 2 ungeschickterweise mit rot statt grün gefärbt wurden.
+++++
 ===== Algorithmus =====