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 Bä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.
· Ein Baum mit e Ecken (corners) hat e − 1 Kanten (edges)
· Ein Wald (Ein Graph, dessen (Zusammenhangs-) Komponenten jeweils Bä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.
