Ein Out-Tree oder auch Arboreszenz ist in der Graphentheorie ein spezieller 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 mit einem ausgezeichneten Knoten, der so genannten Wurzel, sodass jeder Knoten durch genau einen gerichteten Pfad von der Wurzel aus erreichbar ist.[1]
Weitere Begriffe
Der maximale Ausgangsgrad wird als Ordnung eines Out-Trees 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 Out-Trees die Länge eines längsten Pfades.
Wie bei ungerichteten 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.
Bei einem (a,b)-Baum haben alle Teilbäume die gleiche Tiefe.
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, 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, 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 rekursiv definieren. Sie bestehen aus einem Knoten w, der die Wurzel des Baumes darstellt, welcher ausschließlich mit den Wurzeln knotendisjunkter Out-Trees T1, T2, ..., Tn verbunden ist, und zwar in Richtung der Wurzeln von T1, T2, ..., Tn.
Siehe auch
- Der letzte gemeinsame Vorfahr als Ermittlungskonzept in der Graphentheorie
Literatur
- Bernhard Korte, Jens Vygen: Aufspannende Bäume und Arboreszenzen. In: Kombinatorische Optimierung: Theorie und Algorithmen. Springer, Berlin, Heidelberg 2018, ISBN 978-3-662-57691-5, S. 141–166, doi:10.1007/978-3-662-57691-5_6 (springer.com).
Einzelnachweise
- ↑ Willibald Dörfler, Jörg Mühlbacher: Graphentheorie für Informatiker. Walter de Gruyter, 2011, ISBN 978-3-11-083572-4, S. 49 f. (google.de [abgerufen am 31. Dezember 2024]).