Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- 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:26] – [Weiterführende Fragen & Aufgaben] Frank Schiebel
@@ Zeile 23: / Zeile 23: @@
   * Verwende dabei möglichst wenige Farben.
   * 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((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 aus m Knoten benötigt mindestens m Farben.
+</WRAP>
 ===== Algorithmus =====