Rooted tree

The articles tree_ (data structure) and rooted tree overlap thematically. Help me to better differentiate or merge the articles (→  instructions ) . To do this, take part in the relevant redundancy discussion . Please remove this module only after the redundancy has been completely processed and do not forget to include the relevant entry on the redundancy discussion page{{ Done | 1 = ~~~~}}to mark. Wizard in Training ( discussion ) 12:49, 25 Sep 2019 (CEST)

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

A rooted tree (also root tree ) is in graph theory a tree that contains a distinct node, the root , from which all other nodes can be reached or which in turn can be reached from any other node. Root trees thus belong to the classes of root graphs and trees and therefore combine the properties of both graph classes.

In the undirected tree , any node can be the root. A distinction can be made in the directional root tree:

• Out-Trees (also arborescence ), in which the edges start from the root (all nodes can be reached by exactly one path from this), and
• In-trees (also anti-arborescence ), in which the edges point in the direction of the root (the root can be reached by exactly one path from this).

In the directed root tree, the root forms the strong connection to all other nodes.

More terms

In the case of out-trees, the maximum output degree is called the order of the 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 tree is the length of the longest path that must always run from the root to a leaf. In the case of in-trees, the maximum degree of entry of the tree is called its order and all nodes with degree of entry 0 are called leaves. As a height of the tree is also called the length of a longest path from a leaf to the root (or vice versa).

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

There are a number of other terms for out-trees. For a node that is different from the root , the node through which it is connected to an incoming edge is called father , father node , mother , mother node , parent , parent node (also parent node ) or predecessor of . As ancestor of all nodes are referred to on the path to the root. ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$

Conversely, it refers to all nodes from any node are connected by one outgoing edge as children , children nodes , son or successor of . As descendants of is any node to those of exists from a path so all nodes of the sub-tree that has as its root. In an out-tree, nodes that have the same predecessor node are referred to as siblings or sibling nodes. ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$

A root tree in which a linear order is defined for the sons of each node is called an ordered tree or planar tree . The order clearly defines the way in which the successors of a node are displayed in the graphical representation of the tree (e.g. from left to right according to the order criterion). Formally, the order defines the order in which the nodes are traversed for different traversal procedures (preorder, inorder, postorder).

Spanning trees are root trees with the starting node of the traversal as the root.

Alternative definition

Rooted trees can also be defined recursively . They consist of a node that represents the root of the tree, which is exclusively connected to the roots of node-disjoint trees , for out-trees in the direction of the roots of , which are themselves out-trees, and for in-trees in the direction of , where themselves are in-trees. ${\displaystyle w}$ ${\displaystyle T_{1},T_{2},\ldots ,T_{n}}$ ${\displaystyle T_{1},T_{2},\ldots ,T_{n}}$ ${\displaystyle w}$ ${\displaystyle T_{1},T_{2},\ldots ,T_{n}}$

See also

• Comparability graph

Individual evidence

1. ↑ Tittmann, Peter: Graph Theory An application-oriented introduction . 3rd, updated edition. Hanser, Munich 2019, ISBN 978-3-446-46052-2 , pp. 112 .