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 durchArthur Cayley
(1857)
Definitionen
Ein Baum ist ein zusammenhängender kreisfreier ungerichteter Graph. Die Knoten mit Grad 1 heißen Blätter, die übrigen Knoten heißen innere Knoten.
Ungerichteter Baum mit vier inneren Knoten (schwarz) und fünf Blättern (weiß)
Gewurzelter Baum (hier: Out-Tree) mit einer Wurzel (umrandet), vier inneren Knoten (schwarz) und fünf Blättern (weiß)
Ein gerichteter Baum ist ein gerichteter Graph, der ein ungerichteter Baum ist, wenn man die Richtungen der Kanten ignoriert. Er ist also ein gerichteter schwach zusammenhängender kreisfreier Graph. Bei vielen Autoren müssen die Richtungen einheitlich von einem Knoten weg oder auf einen Knoten zu orientiert sein. Dafür gibt es aber auch den schärferen Begriff des gewurzelten Baums.
Ein gewurzelter Baum ist ein gerichteter von einem Knoten {\displaystyle w} aus stark zusammenhängender kreisfreier Graph. Der den starken Zusammenhang definierende Knoten {\displaystyle w} wird Wurzel genannt. Er hat Eingangsgrad 0 und ist der einzige Knoten mit dieser Eigenschaft. Alle Knoten mit Ausgangsgrad 0 heißen Blätter. Alle Knoten mit positivem Ausgangsgrad heißen innere Knoten. So geht die Definition eines Out-Trees.
Werden die Richtungen aller Kanten eines solchen Graphen invertiert, so wird er zu einem In-Tree. Dieser wird ebenfalls als gewurzelter Baum angesehen.
Man kann jeden ungerichteten Baum an einem beliebigen Knoten {\displaystyle w} fassen und „schütteln“ – die Schwerkraft gibt allen Kanten eine definierte Richtung von {\displaystyle w} weg, die aus dem ursprünglich ungerichteten Baum einen gewurzelten machen mit {\displaystyle w} als Wurzel.
Den {\displaystyle m} Kanten eines ungerichteten Baums kann man 2𝓂 verschiedene Richtungen geben und so 2𝓂 gerichtete Bäume ableiten. Genau 𝓃 = 𝓂 + 1 davon sind Out-Trees und ebenso viele sind In-Trees. Entfernt man umgekehrt bei einem gerichteten Baum die Orientierung der Kanten, so erhält man einen ungerichteten Baum.