imported>PerfektesChaos: tk k

2025-05-27T18:47:40Z

tk k

Neue Seite

[[Datei:Directed tree graph.png|rechts|gerahmt|Gewurzelter Baum als In-Tree mit Knoten 2 als Wurzel]]
Ein '''gewurzelter Baum''' (auch '''Wurzelbaum''') ist in der [[Graphentheorie]] ein [[Baum (Graphentheorie)|Baum]], der einen ausgezeichneten Knoten, die [[Wurzel (Graphentheorie)|Wurzel]], enthält, von dem aus sämtliche anderen [[Knoten (Graphentheorie)|Knoten]] erreichbar sind oder der seinerseits von jedem anderen Knoten aus erreicht werden kann.<ref>{{Literatur |Autor=Peter Tittmann |Titel=Graphentheorie Eine anwendungsorientierte Einführung |Auflage=3., aktualisierte |Verlag=Hanser |Ort=München |Datum=2019 |ISBN=978-3-446-46052-2 |Seiten=112}}</ref> Wurzelbäume zählen somit zu den Klassen der [[Wurzelgraph|Wurzelgraphen]] und der Bäume und vereinen daher die Eigenschaften beider Graphenklassen.

Beim [[Ungerichteter Baum|ungerichteten Baum]] kann jeder Knoten die Wurzel sein. Beim gerichteten Wurzelbaum lassen sich unterscheiden:
* [[Out-Tree]]s (auch '''Arboreszenz'''), bei denen die Kanten von der Wurzel ausgehen (alle Knoten sind durch genau einen Pfad von diesem aus erreichbar), und
* [[In-Tree]]s (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.

== Weitere Begriffe ==
Im Falle von Out-Trees wird der maximale [[Ausgangsgrad]] als ''Ordnung'' des Baumes bezeichnet und alle Knoten mit Ausgangsgrad 0 bezeichnet man als ''Blätter''. Als ''Tiefe'' eines Knotens bezeichnet man die Länge des Pfades von der Wurzel zu ihm und als ''Höhe'' des Baumes die Länge eines längsten Pfades, der immer von der Wurzel zu einem Blatt laufen muss. Im Falle von In-Trees bezeichnet man den maximalen [[Eingangsgrad]] des Baumes als seine ''Ordnung'' und alle Knoten mit Eingangsgrad 0 als Blätter. Als ''Höhe'' des Baumes bezeichnet man hier analog die Länge eines längsten Pfades von einem Blatt zur Wurzel.

Wie bei allen Bäumen bezeichnet man auch in gewurzelten Bäumen alle Knoten, die kein Blatt sind, als ''innere Knoten''. Manchmal schließt man die Wurzel dabei aber aus.

Für Out-Trees gibt es noch eine ganze Reihe weiterer Begriffe. Für einen von der Wurzel verschiedenen Knoten <math>v</math> bezeichnet man den Knoten, durch den er mit einer eingehenden Kante verbunden ist als ''Vater'', ''Vaterknoten'', ''Mutter'', ''Mutterknoten'', [[wikt:Elter|''Elter'']], ''Elterknoten'' (auch ''Elternknoten'') oder ''Vorgänger'' von <math>v</math>. Als ''Vorfahren'' von <math>v</math> werden alle Knoten auf dem Pfad zur Wurzel bezeichnet.

Umgekehrt bezeichnet man alle Knoten, die von einem beliebigen Knoten <math>v</math> aus durch eine ausgehende Kante verbunden sind als ''Kinder'', ''Kinderknoten'', ''Sohn'' oder ''Nachfolger'' von <math>v</math>. Als ''Nachfahren'' von <math>v</math> bezeichnet man alle Knoten zu denen von <math>v</math> aus ein Pfad existiert, also alle Knoten des Unterbaums, der <math>v</math> als Wurzel hat. Als ''Geschwister'' oder ''Geschwisterknoten'' werden in einem Out-Tree Knoten bezeichnet, die denselben Vorgängerknoten besitzen.

Ein Wurzelbaum, in dem für die Söhne jedes Knotens eine [[lineare Ordnung]] definiert ist, heißt ''geordneter Baum'' oder ''planarer Baum''. Anschaulich legt die Ordnung fest, in welcher Weise die Nachfolger eines Knotens in der grafischen Darstellung des Baumes angezeigt werden (z. B. von links nach rechts gemäß Ordnungskriterium). Formal wird durch die Ordnung festgelegt, in welcher Reihenfolge die Knoten bei unterschiedlichen Traversierungsverfahren (preorder, inorder, postorder) durchlaufen werden.

Spannbäume sind Wurzelbäume mit dem Startknoten der Traversierung als Wurzel.

== Alternative Definition ==
Gewurzelte Bäume lassen sich auch [[Rekursion|rekursiv]] definieren. Sie bestehen aus einem [[Knoten (Graphentheorie)|Knoten]] <math>w</math>, der die Wurzel des Baumes darstellt, welcher ausschließlich mit den Wurzeln knotendisjunkter Bäume <math>T_1,T_2,\ldots,T_n</math> verbunden ist, bei Out-Trees in Richtung der Wurzeln von <math>T_1,T_2,\ldots,T_n</math>, wobei diese selbst Out-Trees sind, und bei In-Trees in Richtung von <math>w</math>, wobei <math>T_1,T_2,\ldots,T_n</math> selbst In-Trees sind.

== Siehe auch ==
* [[Vergleichbarkeitsgraph]]

== Einzelnachweise ==
<references />

[[Kategorie:Bäume und Wälder]]

Gewurzelter Baum - Versionsgeschichte

imported>PerfektesChaos: tk k