Keine gerichteten Kreise in einem Binärbaum

Question

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', v₁, v_{2, ...}, v_k, 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, w₁, w₂, ..., w_l, v'), da T nach Def. zusammenhängend ist.

Fall 1: v_k != w_l

Dann hat v' zwei eingehende Kanten, was nach Def. nicht möglich ist

Fall 2: v_k = w_l

Dann gehe beide Weg rückwärts, bis v_k-i != w_l-j gefunden ist.

Dieses Paar muss existieren, da r nicht auf dem Kreis von v' liegen kann.

Dann hat der Knoten v_k-i+1 bzw. w_l-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?

Answer 1

Ich finde es ganz gut so.

Comments

Danke fürs Draufschauen