Out tree

Out-tree with one root (bordered), four inner nodes (black) and five leaves (white)

In graph theory, an out-tree is a special graph , more precisely a rooted tree , in which the edges start from the root.

definition

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

More terms

The maximum output degree is called the order of an out-tree and all nodes with output degree 0 are called leaves . The depth of a node is the length of the path from the root to it and the height of the out tree is the length of a longest path.

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

In an (a, b) -tree , all subtrees have the same depth.

For a node v different from the root , the node through which it is connected to an incoming edge is called the father , father node , parent node or predecessor of v . As ancestors of v is any node that either father of v are the father or predecessor.

Conversely, it refers to all nodes from any node v are connected by one outgoing edge as children , the child nodes , son or successors of v . As descendants of v are called children of v , or their descendants. In an out-tree, nodes that have the same father are referred to as siblings or sibling nodes .

Alternative definition

Out-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 out-trees T ₁ , T ₂ , ..., T _n , in the direction of the roots of T ₁ , T ₂ , ..., T _n .