In-Tree

Rooted tree as in-tree with node 2 as the root.

An in-Tree is in graph theory , a special graph , specifically a Rooted tree .

definition

An in-tree is a directed graph with a marked node, the so-called root , for which, in contrast to out-trees , the root can be reached from each node through exactly one directed path .

More terms

The maximum degree of entry of an in-tree is called its order , and all nodes with degree of entry 0 are called leaves. The height of the in-tree is the length of the longest path.

As with undirected trees , all nodes in rooted trees that are not leaves are called inner nodes . Sometimes you exclude the root.

Alternative definition

In-trees can also be defined recursively . They consist of a node w , which represents the root of the tree, which is exclusively connected to the roots of node-disjoint in-trees T ₁ , T ₂ , ..., T _n in the direction of w .