Graphentheorie, chromatische Knotenzahl, Färbung

Neue Frage »

knoten Auf diesen Beitrag antworten »
Graphentheorie, chromatische Knotenzahl, Färbung
Wie beweise ich folgendes:
Für jeden Graphen G gilt:
Xv(G) ist kleiner gleich 1/2 + Wurzel aus: 1/2 + 2|K|
wobei |K| die Anzahl der Kanten des Graphen ist und
die Xv(G) die chromatische Knotenzahl des Graphen G ist, es gilt:
Xv(G) = min{n aus den nat. Zahlen | G ist n-knotenfärbbar}
AD Auf diesen Beitrag antworten »
RE: Graphentheorie, chromatische Knotenzahl, Färbung
Als Hinweis: Zwischen n Knoten gibt es maximal



Kanten. Das Maximum wird erreicht, wenn jeder Knoten mit jedem anderen verbunden ist.
knoten Auf diesen Beitrag antworten »
RE: Graphentheorie, chromatische Knotenzahl, Färbung
sorry, unter der Wurzel muss stehen:1/4+...
AD Auf diesen Beitrag antworten »
RE: Graphentheorie, chromatische Knotenzahl, Färbung
Hab ich gemerkt, aber mit 1/2 stimmt's natürlich auch (da wird ja die rechte Seite der <=Ungleichung nur größer). Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »