imported>Sokonbud: form

2017-04-27T11:57:19Z

form

Neue Seite

[[Datei:Directed tree graph.png|mini|Gewurzelter Baum als In-Tree mit Knoten 2 als Wurzel.]]
Ein '''In-Tree''' ist in der [[Graphentheorie]] ein spezieller [[Graph (Graphentheorie)|Graph]], genauer ein [[gewurzelter Baum]].

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

== Weitere Begriffe ==
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 [[ungerichteter Baum|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 ==
In-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 In-Trees ''T''1, ''T''2, …, ''T''''n'' in Richtung von ''w'' verbunden ist.

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

In-Tree - Versionsgeschichte

imported>Sokonbud: form