Beweis Ungleichung Graph |
13.01.2013, 20:59 | Knotenpunkt | Auf diesen Beitrag antworten » |
Beweis Ungleichung Graph fuchsc.sbg.ac.at/ws1213/dm_serie12.pdf Nun, ich soll offenbar die Anzahl der Kanten betrachten, zwischen den ersten Knoten. Habe ich k Knoten, dann gibt es entweder k Kanten oder k-1 .. oder k-k Kanten. also bei k Knoten höchstens k Kanten. Nun zur Ungleichung: Es wird summiert die Grade bei n verschiedenen Graden vom Grad des ersten Knoten bis zum Grad des k.-Knotens. Diese Zahl ist entweder gleich 2*|E|, wenn k = n, oder kleiner als 2*|E|, falls k < n. Auf der 'rechten' Seite der Ungleichung: ? Bin ich denn mit meiner Idee wenigstens auf der richtigen Fährte? |
||
13.01.2013, 22:50 | Knotenpunkt | Auf diesen Beitrag antworten » |
Bei k Knoten höchstens k*(k-1) / 2 Kanten.. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|