Eigenschaften von Bäumen

Beziehung zwischen Anzahl der Knoten und Kanten?

Jeder Baum ist

• minimal zusammenhängend

  (durch Löschen einer beliebigen Kante zerfällt der Graph)

• maximal kreisfrei

  (durch Einfügen einer beliebigen weiteren Kante entsteht ein Kreis)

in jedem Baum gibt es zwischen je zwei Knoten genau einen Pfad.

Pfadlänge = Anzahl der Kanten (Verbindungen)

Höhe eines Baumes: maximale Pfadlänge.