Arborescence (graph theory)

A Rooted tree (including the root tree or arborescence ) is in Graph theory, a tree, the edges of which have a preferred direction, so that in contrast to the non-directional tree, a node can be identified as the root. It can be out- Trees, in which the edges emanating from the root, and in- Trees, which show the edge towards the root differ.

Definition

Rooted trees are directed graphs with an excellent node, called the root, for the rule is that in the case of out -trees, each node is reachable by exactly one directed path from this point or that, in the case of in- Trees that of each node by a directed path can be reached exactly.

Other terms

In the case of out -trees, the maximum out-degree is called the order of the tree and all nodes with out-degree 0 are called leaves. As the depth of a node is defined as the length of the path from the root to it and as the height of the tree, the length of a longest path that must always be run from the root to a leaf. In the case of in -trees is defined as the maximum input level of the tree as its order and all nodes with in-degree 0 as leaves. As height of the tree is also referred to here, the length of a longest path that must always run from one leaf to the root.

As with undirected trees is also called in rooted trees, all nodes that are not a leaf, as internal nodes. Sometimes you close your root it out though.

For out -trees, there are a number of other terms. For a different from the root node v is called the node through which it is connected with an incoming edge as a father, parent node, parent, parent node, the parent node or predecessor of v. The ancestors of v, all nodes designated on the path to the root.

Conversely, consists of all the nodes that are connected by an arbitrary node v by an outgoing edge as children, children nodes, son or successor of v. As descendants of v is any node to those of v exists from a path, ie all nodes the sub-tree which has a root v. As a sibling or sibling nodes are referred to in an out -tree that have the same parent node.

A rooted tree in which each node for the sons of an order relation is defined is called ordered tree. Clearly defines the order in which way the successor of a node are displayed in the graphical representation of the tree (eg, from left to right according to classification criterion ). Formal is defined by the order, the order in which the nodes are traversed at different Traversierungsverfahren ( preorder, inorder, postorder ).

Alternative definition

Rooted trees can also be defined recursively. They consist of a node w, which represents the root of the tree, which knotendisjunkter exclusively with the roots of trees T1, T2, ..., Tn is connected, at Out - Trees toward the roots of T1, T2, ..., Tn, which are self- Out - Trees, and in - Trees in the direction of w, where T1, T2, ..., Tn are self- in- Trees.