Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung | Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:25] – [Modellierung] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:26] – [Weiterführende Fragen & Aufgaben] Frank Schiebel | ||
---|---|---|---|
Zeile 29: | Zeile 29: | ||
Für die Kolorierung von Graphen gelten folgende Sätze: | 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. | * 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 bipartiter((https:// |
* Ein vollständiger Graph mit n Knoten benötigt n Farben. | * Ein vollständiger Graph mit n Knoten benötigt n Farben. | ||
* Ein Graph mit einer Clique aus m Knoten benötigt mindestens m Farben. | * Ein Graph mit einer Clique aus m Knoten benötigt mindestens m Farben. |