Out-Tree - LinkFang.de





Out-Tree


Ein Out-Tree ist in der Graphentheorie ein spezieller Graph, genauer ein gewurzelter Baum, bei dem die Kanten von der Wurzel ausgehen.

Definition

Ein Out-Tree ist ein gerichteter Graph mit einem ausgezeichneten Knoten, der so genannten Wurzel, für den im Gegensatz zu In-Trees gilt, dass jeder Knoten durch genau einen gerichteten Pfad von der Wurzel aus erreichbar ist.

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.

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 einem Out-Tree Knoten bezeichnet, die den gleichen 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.


Kategorien: Gerichteter Graph | Bäume und Wälder

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Out-Tree (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.