Induktion bei Bäumen

Neue Frage »

bgZ Auf diesen Beitrag antworten »
Induktion bei Bäumen
Hi,

ich soll mittels Induktion zeigen, dass ein Baum mit n Knoten immer n-1 Kanten hat. Dies ist eine Zusatzaufgabe auf meinem Übungsblatt und das hatten wir nicht in der Vorlesung. Im Internet hab ich auch nichts gescheites gefunden.

Prinzipiell verstehe ich das, da es immer einen Wurzelknoten gibt, aber wie ich das sinnvoll beweisen soll, weiß ich nicht.

Wenn ich nun wie bei der vollständigen Induktion anfange:

IA: n=1 => Ein Baum der aus 1 Knoten besteht (nur Wurzel) hat 1-1 = 0 Kanten. Das ist richtig.

IH: nun mach ich die Annahme dass die o. g. Aussage für ein Baum mit einem bestimmten n gilt.

IS: Aber was soll ich hier zeigen. Ich meine wenn ich zeige dass das auch für n+1 gilt also ein Baum mit n+1 hat n+1-1 also n Kanten hab ich ja auch nichts gewonnen, oder?

Das muss doch irgendwie anders gehen.


Greetz
bgZ
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von bgZ
Ich meine wenn ich zeige dass das auch für n+1 gilt also ein Baum mit n+1 hat n+1-1 also n Kanten hab ich ja auch nichts gewonnen, oder?

Es kommt darauf an, ob du in deinem Baum mit n+1 Knoten einen Baum mit nur n Knoten findest, auf den du die Induktionsvoraussetzung anwenden kannst - zweckmäßigerweise, indem du einen Knoten (gedanklich) entfernst. Dabei hast du die freie Wahl, welcher Knoten das ist, d.h., du solltest so einen wählen, dass der Rest immer noch ein Baum ist. Augenzwinkern

P.S.: Es liegt wohl daran, dass du wie so viele das Wesen und die Macht der Vollständigen Induktion nicht sehr erfasst hast - in bloßen Summen- oder Ungleichungsbeweisen wie in der Schule erschließt sich das auch nicht so ganz. Augenzwinkern
bgZ Auf diesen Beitrag antworten »

Tach,

erstmal Dankeschön für deine Antwort.

Zitat:
P.S.: Es liegt wohl daran, dass du wie so viele das Wesen und die Macht der Vollständigen Induktion nicht sehr erfasst hast - in bloßen Summen- oder Ungleichungsbeweisen wie in der Schule erschließt sich das auch nicht so ganz.


Scheint wohl so zu sein... vielleicht

Zitat:
Es kommt darauf an, ob du in deinem Baum mit n+1 Knoten einen Baum mit nur n Knoten findest, auf den du die Induktionsvoraussetzung anwenden kannst - zweckmäßigerweise, indem du einen Knoten (gedanklich) entfernst. Dabei hast du die freie Wahl, welcher Knoten das ist.


Ist mir klar, aber das ist ja genau mein Problem, diesen Sachverhalt formal im Sinne der vollständigen Induktion darzustellen.


Greetz
bgZ
René Gruber Auf diesen Beitrag antworten »

Ich weiß nicht, wo es bei dir "hängt": Entferne einen Endknoten (d.h. einen ohne Kinder) sowie die Kante, die ihn mit seinem Vaterknoten verbindet. Der Rest ist ein Baum, auf den du die Induktionsvoraussetzung anwenden kannst - das ist im Prinzip schon das Wesentliche des Induktionsschrittes.
bgZ Auf diesen Beitrag antworten »

Kann ich das so stehen lassen. Ich meine es ist mir klar, dass ich ein Blatt vom Baum entfernen muss, also ein Knoten ohne Kinder, damit ich wieder einen Baum mit n Knoten habe.

Aber wie kann ich das darstellen "mathematischer" Schreibweise darstellen? Oder kann ich das im Induktionsschrit auch "verbal" beispielsweise wie in deiner Antwort beschreiben?

Danke & Greetz
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von bgZ
Aber wie kann ich das darstellen "mathematischer" Schreibweise darstellen?

Ein mathematischer Beweis sollte in erster Linie verständlich sein. Sehr oft helfen Formeln dabei, weil man die Rechenoperationen nicht gerade alle verbal beschreiben will. Big Laugh

Manchmal ist es aber auch andersherum: Da dient krampfhaftes Hervorwürgen von Formeln nur um der Formeln Willen nicht unbedingt der Verständlichkeit. Aber mach, wie du denkst. smile
 
 
bgZ Auf diesen Beitrag antworten »

Zitat:
Manchmal ist es aber auch andersherum: Da dient krampfhaftes Hervorwürgen von Formeln nur um der Formeln Willen nicht unbedingt der Verständlichkeit.


OK, dann möchte ich mich zunächst für Deinen Tipp bedanken; Sonst wär's mir heute abend vor lauter krampfhaten würgen womöglich noch kotzübel geworden.

Zitat:
Aber mach, wie du denkst. smile

Danke, sehr gändig... dann mach ich das auch smile

Schönes Wochenende!

Greetz
bgZ
Neue Frage »
Antworten »



Verwandte Themen

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