vollständiger Graph
-
Hey!
Ich bin bei dieser Aufgabe voll im Dunkel und würde mich freuen, wenn jemand helfen kann.
Zeigen Sie (unter Verwendung diesen Satztes: Seien G=(V,E), V={x1,x2,...,xn}, E={e1,e2,...,em}. Dann gilt: [n]sum[i=1]d(xi)=2*|E|=2*m), dass der volständige Graph Kn (n=Anzahl der Knoten) 1/2n(n-1) Kanten besitzt.
MfG Ohne_Ahnung
-
Eigentlich sieht man 1/2 n (n-1) einfacher:
Jeder Knoten ist mit jedem anderen durch eine Kante verbunden. -> n*(n-1) Jetzt haben wir aber Hin- und Rückrichtung gezählt. Deshalb nochmal durch 2.
Der Weg den Du wohl nehmen sollst ist folgender:
Mit wievielen Knoten ist der 1. Knoten verbunden? Mit wievielen der zweite? (Achtung, keine doppelten mitzählen... die Verbindung mit dem ersten Knoten zählt nicht mehr). Usw.
Dann über alles Summieren. Fertig!