Autor |
Beitrag |
Sandra (Sandra24)
| Veröffentlicht am Mittwoch, den 25. April, 2001 - 13:41: |
|
Sei G=(v,E) ein Baum, fuer den |V| eine gerade Zahl und der maximale Knotengrad (d(x)<=3) ist. Zu zeigen, dass G hoechstens (|V| / 2 ) +1 Knoten vom Grad 1 hat. Da G Baum gilt: |E|= |V|-1 Also |E|= 2k-1 Da G Baum: Summe deg(x) für alle x = 2* (2k-1) Es soll also gelten: höchstens 2k/2 +1 Knoten haben Grad 1 (k+1) + (Restliche Knoten mit Grad != 1 )< 2(2k-1) (k+1) + (Restliche Knoten mit Grad != 1 )<= k+1 + (2k - (k+1)) *3 <=2(2k-1) k+1+3k-3 <=2(2k-1) 4k-2= 4k-2 q.e.d. |
Matroid (Matroid)
| Veröffentlicht am Mittwoch, den 25. April, 2001 - 22:25: |
|
Willst Du wissen, ob Dein Beweis stimmt? Die ersten Argumente sind ok, aber die Abschätzung ist nicht ok. Dass die Aussage für k+1 Ecken mit Grad 1 nicht auf einen Widerspruch führt, hast Du gezeigt. Aber Du mußt zeigen, daß man für angenommen mehr als k+1 Ecken mit Valenz 1 einen Widerspruch bekommt. Wenn es k+1+c Ecken mit Grad 1 gibt (c>0), dann bleiben noch maximal 2k-k-1-c = k-1-c Ecken mit Grad >1. Der maximale Grad ist nach Voraussetzung aber 3. Folglich wäre die Summe alle Eckengrade kleiner oder gleich k+1+c + 3(k -1 -c) = 4k -2 -3c Wenn aber c>0 ist, dann wäre ja S deg(x) < 4k-2 Gruß Matroid |
|