In-Tree

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 27. April 2017 um 12:57 Uhr durch Sokonbud (Diskussion | Beiträge) (form).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen
Eine gesichtete Version dieser Seite, die am 27. April 2017 freigegeben wurde, basiert auf dieser Version.
Gewurzelter Baum als In-Tree mit Knoten 2 als Wurzel.

Ein In-Tree ist in der Graphentheorie ein spezieller Graph, genauer ein gewurzelter Baum.

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

Weitere Begriffe

[Bearbeiten | Quelltext bearbeiten ]

Der maximale Eingangsgrad eines In-Trees wird als seine Ordnung bezeichnet, und alle Knoten mit Eingangsgrad 0 nennt man Blätter. Als Höhe des In-Trees bezeichnet man 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.

Alternative Definition

[Bearbeiten | Quelltext bearbeiten ]

In-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 In-Trees T1, T2, ..., Tn in Richtung von w verbunden ist.

Abgerufen von „https://de.wikipedia.org/w/index.php?title=In-Tree&oldid=164960898"