+1 Daumen
7,4k Aufrufe

Ich weiß nicht wie ich das mit Induktion beweisen soll:

Ein Baum mit n Knoten hat mindestens n-1 Kanten.

Für den Induktionsanfang habe ich n=1 -> Ein Baum mit einem Knoten hat 1-1=0 Kanten. Das stimmt ja so. Aber ich weiß nicht wie ich sinnvoll weiter machen soll... da man ja eigentlich n+1 als Induktionsschritt nehmen müsste und das ja mit dem n-1 nen bisschen in die quere kommt. Ich bin total verwirrt. :-(

von

1 Antwort

0 Daumen

Die Verankerung hast du ja schon selbst gemacht. Hier nur:

Induktionsschritt n---> n+1

Induktionsvoraussetzung: Ein Baum mit n Knoten hat n-1 Kanten.

Induktionsbehauptung: Ein Baum mit n+1 Knoten hat n Kanten.

Beweis:

Ein Baum mit n+1 Knoten ist ein Baum mit n Knoten, an den ein Knote angebaut wird.

Dazu braucht es eine Kante.

Nach Induktionsvoraussetzung besitzt der Baum schon n-1 Kanten. Der neue hat eine Kante mehr. Also (n-1) + 1 = n Kanten. qed Induktionsschritt.

von 162 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community