Baum (Graphentheorie)

Ein Baum ist in der Graphentheorie ein spezieller Typ von Graph, der zusammenhängend ist und keine geschlossenen Pfade enthält, d. h. damit lässt sich eine Monohierarchie modellieren. Je nachdem, ob die Kanten des Baums eine ausgezeichnete und einheitliche Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in ungerichtete Bäume und gewurzelte Bäume, und für gewurzelte Bäume in Out-Trees, bei denen die Kanten von der Wurzel ausgehen, und In-Trees, bei denen Kanten in Richtung Wurzel zeigen.

Ein Baum ist ein Wald mit genau einer Zusammenhangskomponente.^[1]

Darstellung aller Bäume^{[Anm. 1]} mit einer, zwei oder drei Kanten bei der ersten mathematischen Modellierung von Bäumen durch Arthur Cayley (1857)

↑ Reinhard Diestel: Graphentheorie. 3., neu bearb. und erw. Auflage. Springer, Berlin 2006, ISBN 3-540-21391-0, S. 14.

Referenzfehler: <ref>-Tags existieren für die Gruppe Anm., jedoch wurde kein dazugehöriges <references group="Anm." />-Tag gefunden.

[:0-1] Reinhard Diestel: Graphentheorie. 3., neu bearb. und erw. Auflage. Springer, Berlin 2006, ISBN 3-540-21391-0, S. 14.

[1]

[Anm. 1]