 Beweis Baumstruktur |
|
|
a) angenommen v ist kein Blatt. Es gibt einen Knoten w mit maximalem Abstand zu v. Wenn wir jetzt aber von w aus den am weitesten entfernten Knoten suchen, können wir weiter gehen als bis v (da v kein Blatt).
c) das Gegenbeispiel würde ich gerne mal sehen (mir fällt keines ein).
Das Gegenteil wäre ja ![[latex]\forall_{v\in V}rg(v)=1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\forall_{v\in V}rg(v)=1) . Das geht nur, wenn jeder Knoten mit jedem verbunden ist (Clique bzw. vollständiger Graph). Für mehr als 2 Knoten gibt das aber einen Kreis, also keinen Baum.
Weil ich die c) erst falsch gelesen habe und der Beweis so schön ist: Warum es einen Knoten mit deg(v)>=2 geben muss:
Ein Baum mit n Knoten hat (n-1) Kanten. Jede Kante verbindet 2 Knoten, also ist ![[latex]\sum_{v\in V}deg(v)=2(n-1)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\sum_{v\in V}deg(v)=2(n-1)) .
Der durchschnittliche Rang eines Knoten ist daher ![[latex]\frac{2(n-1)}{n}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\frac{2(n-1)}{n}) . Für n=3 ist das 4/3, also größer 1. Weil die Zahlen alle ganzzahlig sind, muss es auch einen Knoten geben, der ![[latex]\left\lceil \frac{4}{3}\right\rceil=2[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\left\lceil \frac{4}{3}\right\rceil=2) Nachbarn hat.
__________________
Syntax Highlighting fürs Board (Link)
|
|
11.02.2017 07:17 |
|
|
otf
unregistriert
 |
|
Mir ist zu a) was ausgefallen sei wie angegeben rg(v)= max d(v,w), da aber nach Aufgabenstellung für alle u,w Konten gilt d(u,w)=d(w,u), gilt auch
rg(v) = max d(v,w) = max d(w,v) = rg(w) .
Sei v ein Blatt dann ist w kein blatt und dennoch mit maximalen Rang.
Ich hatte den Beweis genauso, wie du es hast, aber ich glaube die def. vom Abstand muss noch sauberer in der Angabe definiert werden.
b) Zeichne einen vollständig balanciertern Baum. Füge zu einem Blatt einen weiteren Knoten X hinzu, dadurch ist X selbst ein Blatt und hat den größten Rang, alle andere sind Blätter, aber dennoch haben sie nicht den maximalen Rang.
zu c) ist meins Lösung falsch?
|
|
|
11.02.2017 10:07 |
|
|
otf
unregistriert
|
|
b) ja mache Blätter schon aber eben nicht alle
c) Hier könnte man auch mit vollständiger Induktion arbeiten.
Für den Fall n= 3 Knoten kann man leicht zeigen dass die Aussage gilt.
Induktionschritt n+1:
Sein ein Baum mit n+1 Knoten gegeben --> wir entfernen ein Blatt, dann haben wir noch
n Knoten im Baum und es gilt die Aussage, dass es ein Knoten V mit rg(V)>=2 gilt(Induktionannhame).
Durch die Hinzunahme des entfernten Blatt erhalten wir den ursprünglichen Baum wieder und es gilt weiterhin rg(v)>=2
|
|
|
11.02.2017 11:19 |
|
|
|
