# Induktionsbeweis



## julia1997 (2. Apr 2017)

Kann mir jemand diesen Induktionsbeweis erklären? Man soll zeigen, dass jeder Wurzelbaum zyklenfrei ist. 

·  Ein Baum mit e Ecken (corners)  hat e − 1 Kanten (edges)

·      Ein Wald (Ein Graph, dessen (Zusammenhangs-) Komponenten jeweils Bäume sind) mit e Ecken hat mindestens 0 Kanten und maximal e−1 Kanten (dann ist er ein Baum).

·       Ein Wald mit e Ecken und k Kanten hat e−k Zusammenhangskomponenten (connection components).

·       Wir beweisen dies mittels vollständiger Induktion (complete induction) über die Anzahl der Kanten.

o  Sei e beliebig. Im *Basisfall (base clause)* ist k = 0 und somit die Anzahl der Zusammenhangskomponenten e = e − 0.

o  Im *Induktionsschritt (induction step)* betrachten wir einen Wald mit k + 1 Kanten.

o  Wir müssen zeigen, dass der Wald e − (k + 1) = e − k − 1 Zusammenhangskomponenten besitzt.

o  Die *Induktionshypothese* besagt, dass ein Wald mit e Ecken und k Kanten e − k Zusammenhangskomponenten besitzt.

o  Durch Zugabe einer zusätzlichen Kante wird aus zwei Bäumen ein neuer Baum, wodurch die Anzahl der Zusammenhangskomponenten um eins abnimmt.


----------



## julia1997 (2. Apr 2017)

Habs grad gelöst, trotzdem Danke!


----------

