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:35] – [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.
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (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<sup>20</sup> = ca. 1 Billion Möglichkeiten, wenn man die Bedingung nicht beachtet, dass zwei Nachbarländer verschieden gefärbt sein müssen.
+++++
 ===== Algorithmus =====