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:26] – [Weiterführende Fragen & Aufgaben] Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:kartenfaerben:start [06.12.2022 12:29] – [Weiterführende Fragen & Aufgaben] Frank Schiebel | ||
---|---|---|---|
Zeile 31: | Zeile 31: | ||
* Ein bipartiter((https:// | * 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(([[https:// |
</ | </ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A2) === | ||
+ | |||
+ | Begründe die obigen Aussagen. | ||
+ | |||
+ | ++++ Lösung | | ||
+ | |||
+ | * Sobald eine Kante vorhanden ist, sind zwei Knoten verbunden. Wenn dies verschiedene Knoten sind (also keine Schleife), dann dürfen diese nicht die selbe Farbe haben und es werden mindestens zwei Farben benötigt. | ||
+ | * Wenn der Graph bipartit ist, dann zerfällt er in zwei Teilmenge der Knoten, die untereinander überhaupt nicht verbunden sind. Damit kann jede Teilmenge in einer einzigen Farbe eingefärbt werden. | ||
+ | * Bei einem vollständigen Graphen ist jeder Knoten mit allen anderen verbunden. Daher muss jeder Knoten eine eigene Farbe haben. | ||
+ | * In einer Clique sind alle Knoten untereinander verbunden. Daher muss jeder Knoten der Clique eine eigene Farbe bekommen. | ||
+ | ++++ | ||
===== Algorithmus ===== | ===== Algorithmus ===== |