Bäume

Baum & Blätter

Ein Baum ist ein zusammenhängender Graph ohne Kreis.

Die Ecken vom Grad $1$ heißen Blätter.

• Jeder Baum mit mehr als einer Ecke, hat (mindestens) ein Blatt
• Jeder zusammenhängende Graph $G$ mit $n$ Ecken ist genau dann ein Baum, wenn er $n-1$ Kanten hat.

aufspannender Baum

Sei $G=\left(E,K\right)$ ein Graph. Ein Teilgraph von G heißt aufspannender Baum von $G$, falls es ein Baum ist, der alle Ecken von $G$ enthält.

• jeder zusammenhängende Graph besitzt einen aufspannenden Baum