imported>D3rT!m: sodass

2025-05-25T10:04:41Z

sodass

Neue Seite

[[Datei:Directed-tree.svg|miniatur|Arboreszenz mit einer Wurzel (umrandet), vier inneren Knoten (schwarz) und fünf Blättern (weiß)]]
Ein '''Out-Tree''' oder auch '''Arboreszenz''' ist in der [[Graphentheorie]] ein spezieller [[Graph (Graphentheorie)|Graph]], genauer ein [[gewurzelter Baum]], bei dem die Kanten von der Wurzel ausgehen. Der Gegensatz dazu ist der sogenannte [[In-Tree]].

== Definition ==
Eine Arboreszenz ist ein [[gerichteter Graph|gerichteter]] Graph mit einem ausgezeichneten Knoten, der so genannten [[Wurzel (Graphentheorie)|Wurzel]], sodass jeder Knoten durch genau einen [[gerichteter Pfad|gerichteten Pfad]] von der Wurzel aus erreichbar ist.<ref>{{Literatur |Autor=Willibald Dörfler, Jörg Mühlbacher |Titel=Graphentheorie für Informatiker |Verlag=Walter de Gruyter |Datum=2011-04-20 |ISBN=978-3-11-083572-4 |Seiten=49 f. |Online=https://www.google.de/books/edition/Graphentheorie_f%C3%BCr_Informatiker/5gOHuT6orEQC?hl=de&gbpv=1&pg=PA49&printsec=frontcover |Abruf=2024-12-31}}</ref>

== Weitere Begriffe ==
Der maximale [[Ausgangsgrad]] wird als ''Ordnung'' eines Out-Trees bezeichnet und alle Knoten mit Ausgangsgrad 0 bezeichnet man als [[Blatt (Graphentheorie)|Blätter]]. Als [[Tiefe (Graphentheorie)|Tiefe]] eines Knotens bezeichnet man die Länge des Pfades von der Wurzel zu ihm und als [[Höhe (Graphentheorie)|Höhe]] des Out-Trees die Länge eines längsten Pfades.

Wie bei [[ungerichteter Baum|ungerichteten Bäumen]] bezeichnet man auch in gewurzelten Bäumen alle Knoten, die kein Blatt sind, als [[innerer Knoten|innere Knoten]]. Manchmal schließt man die Wurzel dabei aber aus.

Bei einem [[(a,b)-Baum]] haben alle Teilbäume die gleiche Tiefe.

{{Anker|Vorfahr}}Für einen von der Wurzel verschiedenen Knoten ''v'' bezeichnet man den Knoten, durch den er mit einer eingehenden Kante verbunden ist als ''Vater'', ''Vaterknoten'', [[Gewurzelter Baum#Weitere Begriffe|Elternknoten]] oder ''Vorgänger'' von ''v''. Als ''Vorfahren'' von ''v'' bezeichnet man alle Knoten, die entweder Vater von ''v'' oder Vorgänger des Vaters sind.

Umgekehrt bezeichnet man alle Knoten, die von einem beliebigen Knoten ''v'' aus durch eine ausgehende Kante verbunden sind als ''Kinder'', [[Gewurzelter Baum#Weitere Begriffe|Kindknoten]], ''Sohn'' oder ''Nachfolger'' von ''v''. Als ''Nachfahren'' von ''v'' bezeichnet man Kinder von ''v'' oder deren Nachfahren. Als ''Geschwister'' oder ''Geschwisterknoten'' werden in einer Arboreszenz Knoten bezeichnet, die denselben ''Vater'' besitzen.

== Alternative Definition ==
Out-Trees lassen sich auch [[Rekursion|rekursiv]] definieren. Sie bestehen aus einem [[Knoten (Graphentheorie)|Knoten]] ''w'', der die Wurzel des Baumes darstellt, welcher ausschließlich mit den Wurzeln knotendisjunkter Out-Trees ''T''1, ''T''2, ..., ''T''''n'' verbunden ist, und zwar in Richtung der Wurzeln von ''T''1, ''T''2, ..., ''T''''n''.

== Siehe auch ==

* Der [[Lowest Common Ancestor|letzte gemeinsame Vorfahr]] als Ermittlungskonzept in der Graphentheorie

== Literatur ==

* {{Literatur |Autor=Bernhard Korte, Jens Vygen |Titel=Aufspannende Bäume und Arboreszenzen |Sammelwerk=Kombinatorische Optimierung: Theorie und Algorithmen |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2018 |ISBN=978-3-662-57691-5 |DOI=10.1007/978-3-662-57691-5_6 |Seiten=141–166 |Online=https://link.springer.com/chapter/10.1007/978-3-662-57691-5_6}}

== Einzelnachweise ==
<references />
[[Kategorie:Bäume und Wälder]]
[[Kategorie:Gerichteter Graph]]

Out-Tree - Versionsgeschichte

imported>D3rT!m: sodass