Induktion bei Bäumen |
26.11.2010, 16:52 | bgZ | Auf diesen Beitrag antworten » | ||||
Induktion bei Bäumen 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 |
||||||
26.11.2010, 17:04 | René Gruber | Auf diesen Beitrag antworten » | ||||
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. 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. |
||||||
26.11.2010, 18:20 | bgZ | Auf diesen Beitrag antworten » | ||||
Tach, erstmal Dankeschön für deine Antwort.
Scheint wohl so zu sein... vielleicht
Ist mir klar, aber das ist ja genau mein Problem, diesen Sachverhalt formal im Sinne der vollständigen Induktion darzustellen. Greetz bgZ |
||||||
26.11.2010, 18:24 | 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. |
||||||
26.11.2010, 18:40 | 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 |
||||||
26.11.2010, 18:57 | René Gruber | Auf diesen Beitrag antworten » | ||||
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. 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. |
||||||
Anzeige | ||||||
|
||||||
26.11.2010, 20:26 | bgZ | Auf diesen Beitrag antworten » | ||||
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.
Danke, sehr gändig... dann mach ich das auch Schönes Wochenende! Greetz bgZ |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|