Gewurzelter Baum

Ein gewurzelter Baum (auch Wurzelbaum) ist in der Graphentheorie ein Baum, der einen ausgezeichneten Knoten, die Wurzel, enthält, von dem aus sämtliche anderen Knoten erreichbar sind oder der seinerseits von jedem anderen Knoten aus erreicht werden kann. Wurzelbäume zählen somit zu den Klassen der Wurzelgraphen und der Bäume und vereinen daher die Eigenschaften beider Graphenklassen.

Beim ungerichteten Baum kann jeder Knoten die Wurzel sein. Beim gerichteten Wurzelbaum lassen sich unterscheiden:

• Out-Trees (auch Arboreszenz), bei denen die Kanten von der Wurzel ausgehen (alle Knoten sind durch genau einen Pfad von diesem aus erreichbar), und
• In-Trees (auch Anti-Arboreszenz), bei denen die Kanten in Richtung Wurzel zeigen (die Wurzel ist durch genau einen Pfad von diesem aus erreichbar).

Beim gerichteten Wurzelbaum bildet die Wurzel den starken Zusammenhang zu allen anderen Knoten.