folgende Aufgabe:
Es ist zu zeigen, dass es in einem Binärbaum keinen gerichteten Kreis gibt.
Ich wollte es über einen indirekten Beweis versuchen.
Sei also T=(V,E) ein Binärbaum mit Knoten v' ∈ V.
Annahme: Es gibt einen gerichteten Kreis in T, so dass es einen Weg gibt (v', v1, v2, ..., vk, v').
Dann kann v' nicht die Wurzel von T sein, da dies nach Def. von Binärbäumen nicht möglich ist (darf keine eingehenden Kanten besitzen). Ebenso kann die Wurzel r von T nicht auf dem Pfad liegen.
Es muss allerdings einen Weg von der Wurzel r von v' geben (r, w1, w2, ..., wl, v'), da T nach Def. zusammenhängend ist.
Fall 1: vk != wl
Dann hat v' zwei eingehende Kanten, was nach Def. nicht möglich ist
Fall 2: vk = wl
Dann gehe beide Weg rückwärts, bis vk-i != wl-j gefunden ist.
Dieses Paar muss existieren, da r nicht auf dem Kreis von v' liegen kann.
Dann hat der Knoten vk-i+1 bzw. wl-j+1 zwei eingehende Kanten, was nicht möglich ist.
Also gilt die Behauptung, dass es in einem Binärbaum keinen gerichteten Kreis gibt.
Ist der Beweis so richtig?
