| 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 |
|
