Graphen |
14.01.2013, 20:26 | Mathenord | Auf diesen Beitrag antworten » |
Graphen Hallo, kann mir bitte wer zeigen, wie man so eine Aufgabe löst? Bestimme die Graphen mit n größer, gleich 2 Knoten, die n-1 verschiedene Grade besitzen. Wär toll, wenn's mir wer zeigen könnt. Meine Ideen: Danke |
||
15.01.2013, 15:02 | Huggy | Auf diesen Beitrag antworten » |
RE: Graphen Zunächst erhebt sich die Frage, ob Knoten vom Grad 0 zugelassen sind oder nicht? Wenn Knoten vom Grad 0 zugelassen sind, kann es offensichtlich nur einen Knoten vom Grad 0 geben und es kann dann keinen Knoten vom Grad n - 1 geben. Betrachtet man dann den Restgraphen ohne den Knoten vom Grad 0, so erfüllt dieser die ursprüngliche Bedingung ohne Zulassung eines Knotens vom Grad 0. Das Problem reduziert sich also auf die Bestimmung der Graphen ohne Knoten vom Grad 0. Für diese gibt es - bis auf Isomorphie - für jedes n nur eine Möglichkeit: Man nummeriere die Knoten von 1 bis n. Man verbinde für den Knoten i durch Kanten mit allen Knoten j mit . Der Beweis kann durch vollständig Induktion geführt werden. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|