| Die letzten 5 Beiträge |
| otf |
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 |
| eulerscheZahl |
a)
| Zitat: |
| rg(v) = max d(v,w) = max d(w,v) = rg(w) . |
Aber von w aus gibt es einen Knoten v', der weiter als v entfernt ist.
Ich habe nur grob angedeutet, wie ich die Aufgabe angehen würde. Das ist kein vollständiger Beweis.
b) manche Blätter haben trotzdem den maximalen Rang. Nur nicht alle die, die von der Wurzel aus am selben Ast hängen wie der neue Knoten.
c) du denkst an das im Anhang?
Der Anstand von v nach w ist 2, also ist rg(v)=rg(w)=2.
eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:
|
| otf |
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? |
| eulerscheZahl |
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. |
| otf |
Beweis Baumstruktur
Hallo Leute,
ich bereite mich auf die Klausur vor und komme gerade nicht weiter..
a)beweisen b) leicht ein gegenbeispiel zufinden c) leicht ein gegenbeispiel zufinden, irgendwie kann das nicht sein denn hierrauf gibt es 4p
zu c) Sei die Anzahl an Knoten 3 und der Wurzelknoten habe ein deg von =2 dann ist der
rg(v) für alle v kleiner als 2...?
otf hat dieses Bild (verkleinerte Version) angehängt:
|
|
|
