Beweis Baum mehr Knoten als Blätter |
| 13.07.2012, 12:03 | ADM_Lerner | Auf diesen Beitrag antworten » | ||
| Beweis Baum mehr Knoten als Blätter Hallo, bei der Klausurvorbereitung sind wir nun schon zum zweiten Mal auf folgende Aufgabenstellung gestoßen und kommen einfach nicht drauf. Auch unsere Tutoren scheitern. Folgende Aufgabe: Beweise, dass ein Baum ohne Knoten vom Grad 2 mindestens so viele Blätter wie innere Knoten (Knoten vomm Grad > 1) hat. Ich hoffe, ihr könnt uns helfen! Meine Ideen: Wir waren darauf gekommen, es über die Formel zu beweisen, wobei b = Anzahl Blätter, n = Anzahl innere Knoten und n = Anzahl aller Knoten im Baum ist. Nur beim Beweis sind wir beim dritten Fall der Induktion hängen geblieben. Sei der Knoten k, an den wir einen neuen anhängen (n+1) vom Grad 2. Die anderen beiden Fälle, k war en Blatt und k war vom Grad > 2 sind annähernd trivial. |
||||
| 13.07.2012, 13:47 | Mystic | Auf diesen Beitrag antworten » | ||
| RE: Beweis Baum mehr Knoten als Blätter Eure Tutoren schaffen das auch nicht? Sagst du das nur so, oder sind die wirklich so schwach? 
Jedenfalls folgt das sofort durch flüchtiges Hinschauen auf die Gradformel wobei die die Knotengrade sind... |
||||
| 13.07.2012, 14:17 | Flora | Auf diesen Beitrag antworten » | ||
| RE: Beweis Baum mehr Knoten als Blätter Hey Mystic, zumindest ist einer gestern nach absoluter Vollverwirrung gescheitert und die andere brauchen wir da erst gar nicht fragen.... Vielleicht kannst du uns noch einmal auf die Sprünge helfen, die Gradformel ist so bekannt und ja auch logisch. Nur was hat das mit unserer Aufgabenstellung zu tun? Wir können daraus nicht erkennen, warum es immer mindestens so viele Blätter wie innere Knoten geben soll..... Danke schon einmal. Die ADM_Lerner PS Sorry, für die Verwirrung mit dem Alias. |
||||
| 13.07.2012, 14:38 | Mystic | Auf diesen Beitrag antworten » | ||
| RE: Beweis Baum mehr Knoten als Blätter Naja, Blätter haben ja per definitionem den Grad 1... Und Knoten vom Grad 2 gibt es laut Voraussetzung nicht, d.h., innere Knoten haben mindestens den Grad 3... Ist es da nicht klar, dass es nicht zuviele von letzeren bzw. zuwenige von ersteren geben kann? Diesen Teil der Aufgabe solltest du nun aber wirklich selbst herausfinden, denn es ist ja auch so schon bedenkich nahe an einer Komplettllösung... 
|
||||
| 13.07.2012, 14:45 | Flora | Auf diesen Beitrag antworten » | ||
| RE: Beweis Baum mehr Knoten als Blätter Hey Mystic, die Logik dahinter ist uns schon bewusst. Nur kann ich in keinen Beweis etwas schreiben wie es darf "nicht zuviele von letzeren bzw. zuwenige von ersteren geben". Die Beweisidee ist uns halt nicht klar. Induktion, Wiederspruch und wenn, wie soll es gehen? Das es so sein muss, ist uns klar. Sorry, hoffe du wirst uns trotzdem nochmal schubsen! |
||||
| 13.07.2012, 15:04 | Mystic | Auf diesen Beitrag antworten » | ||
RE: Beweis Baum mehr Knoten als Blätter
Ui, ui, das tut doppelt weh... 
Einmal wegen deiner Schreibweise von Widerspruch, andererseits dass dir nicht einmal das Beweisschema noch klar ist und du sogar einen Induktionsbeweis nicht einmal ausschließen kannst, obwohl davon nirgendwo die Rede war... 
Nimm einfach mal an, es gäbe k Blätter, d.h., Knoten vom Grad 1 und daher n-k Knoten vom Grad mindestens 3... Welche Ungleichung folgt dann für k aus der Gradformel?... |
||||
| Anzeige | ||||
|
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
