Graphentheorie: Anzahl Ecken

Neue Frage »

*Sonnenschein* Auf diesen Beitrag antworten »
Graphentheorie: Anzahl Ecken
Hallo,

wie kann ich zeigen das es in einen binären Baum n+1/2 Endecken gibt.

Ich habe bewiesen das es in einen binären Baum eine ungerade Anzahl von Ecken gibt.
Von jeder Ecke kann ja nur eine bzw 3 Kanten *abgehen*
Bis auf eine Ecke die vom Grad zwei sein darf.

Angenommen meine *Startecke* hat den Grad zwei. Also gibt es 3 Ecken und 2 Endecken. Von den zwei neuen Ecken dürfte ja entweder keine Ecke mehr abgehen oder zwei. Angenommen es gehen zwei neue Kanten davon ab. Dann entsteht eine grade Anzahl an neuen Ecken (in diesen Fall 4). Somit muss die Anzahl der Endecken ja immer gerade sein. Und die Anzahl der Endecken müssen sich ja demnach immer verdoppeln.
Aber da die Gesamtzahl der Ecken (wegen der Startecke) ja ungerade ist, muss man die Anzahl der Ecken + eine Ecke (Startecke) rechnen und das ganze durch zwei teilen...

Das sind so meine Gedanken. Vielleicht kann mir ja jemand helfen. Ich bin mir nicht ganz schlüßig warum man durch zwei teilen muss.
Abakus Auf diesen Beitrag antworten »
RE: Graphentheorie: Anzahl Ecken
Hallo!

Erstmal - richtige Klammersetzung macht deine Behauptung erst sinnvoll.

Zur Beweisidee würde ich bei einem Baum mit n Knoten, n genügend groß, einfach die Wurzel wegnehmen und die 2 entstehenden Teilbäume betrachten (allgemeine Induktion über n).

Grüße Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »