Graphentheorie. T sie Wurzelbaum mit Wurzel u und Knoten v, mit v≠u. Zeige: es gibt genau 1 Pfad von u nach v.

Question

Hallo an alle. Ich bräuchte Hilfe bei dieser Aufgabe. Wäre jemand so nett mir zu einem Ansatz oder einer Lösung zu verhelfen?


Sei T ein Wurzelbaum mit Wurzel u sowie v ein Knoten von T, mit v≠u. Beweisen Sie, dass es
in T genau einen Pfad von u nach v gibt.

Answer 1

Da T ein Wurzelbaum und v ein Knoten von T ist, muss es mindestens einen Pfad von u nach v geben.

Da in einem Wurzelbaum jeder Knoten (bis auf die Wurzel) genau einen unmittelbaren Vorgänger hat (jeder Knoten hat Eingangsgrad 1), kann es auch nur höchstens einen Pfad von v nach u geben. Dieser Pfad ist dann aber auch der einzige, der von u nach v führt.

Wenn es aber mindestens und höchstens einen Pfad von u nach v gibt, dann gibt es genau einen solchen Pfad.

 

Ob das wohl genügt?
Zumindest ist es ja ein Ansatz für einen formalen Beweis.