Graphentheorie, chromatische Knotenzahl, Färbung |
05.02.2005, 11:23 | knoten | Auf diesen Beitrag antworten » |
Graphentheorie, chromatische Knotenzahl, Färbung 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} |
||
05.02.2005, 11:46 | 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. |
||
05.02.2005, 14:43 | knoten | Auf diesen Beitrag antworten » |
RE: Graphentheorie, chromatische Knotenzahl, Färbung sorry, unter der Wurzel muss stehen:1/4+... |
||
05.02.2005, 15:00 | 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). |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|