Beweis Baumstruktur |
| 10.02.2017, 18:49 | Auf diesen Beitrag antworten » | ||
| 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...? |
||
|
|
|||
| 11.02.2017, 07:17 | Auf diesen Beitrag antworten » | ||
| 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 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 Der durchschnittliche Rang eines Knoten ist daher |
||
| 11.02.2017, 10:07 | Auf diesen Beitrag antworten » | ||
| 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? |
||
| 11.02.2017, 10:17 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | a)
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. |
||
| Anzeige | |||
|
|
|||
| 11.02.2017, 11:19 | Auf diesen Beitrag antworten » | ||
| 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 |
||
|
|
