Direkt zum Inhalt

Lexikon der Mathematik: Baum

ein zusammenhängender Graph ohne Kreise.

Die Ecken eines Baumes vom Grad 1 sind seine Blätter. Jeder Baum T der Ordnung |E(T)| ≥ 2 besitzt mindestens zwei Blätter – etwa die Endecken eines längsten Weges in T. Dies kann bei Induktionsbeweisen für Bäume nützlich sein, denn entfernt man aus einem Baum ein Blatt, so entsteht wieder ein Baum. Die Zusammenhangskomponenten eines Waldes sind Bäume.

Folgende Charakterisierungen von Bäumen lassen sich recht einfach nachweisen. Ein Graph ist genau dann ein Baum, wenn je zwei verschiedene Ecken durch genau einen Weg verbunden sind. Ein zusammenhängender Graph mit n Ecken ist genau dann ein Baum, wenn er (n − 1) Kanten besitzt.

Auch die nächste Eigenschaft von Bäumen ist leicht einzusehen. Verbindet man zwei verschiedene Ecken eines Baumes durch eine zusätzliche Kante, so entsteht ein Graph mit genau einem Kreis.

Ein zusammenhängender gerichteter Graph D, dessen untergeordneter Multigraph keinen Kreis besitzt, heißt gerichteter Baum.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos