Tree (graph theory)

A tree is in graph theory, a special graph with a single hierarchy can be modeled. Depending on whether the edges of the tree have an excellent ( and uniform) direction, graph-theoretic trees can be divided into undirected trees and rooted trees, and rooted trees in Out - Trees, which runs out of edges from the root, and in- Trees, where edges point towards the root.

In computer science, trees are often used as a data structure. In this case, however, they are represented as different general graphs. By removing an edge breaks down a tree into two subtrees, thus forming a so-called forest.

Definitions

An ( undirected ) tree is a connected cycle-free undirected graph. The nodes with degree one are called leaves, the remaining nodes are called inner nodes.

A directed tree is a directed graph, which is a ( non-directional ) tree, ignoring the direction of the edges. So he is a directed weakly continuous cycle-free graph. For many authors, the directions must be uniform from one node away or on a node -oriented. There is also the ( sharper ) concept of rooted tree.

A Rooted tree is a directed from a node strongly connected cycle-free graph. The strong connection defining node is called root. He has in-degree 0 and is the only node with this property. All nodes with out-degree 0 are called leaves. All nodes with out-degree > 0 are called inner nodes. So goes the definition of an out- tree. If the directions of all the edges of such a graph is inverted, so it becomes an in -tree. This is also considered Rooted Tree.

One can grasp and shake every undirected tree at any node - the force of gravity are all edges of a defined direction of away, which makes a rooted from the original undirected tree with as root. The m edges of an undirected tree can give 2m different directions and thus derive 2m -looking trees. Exactly n = m 1 of them are out -trees and just as many are in- Trees. If one removes reversed in a directed tree, the orientation of the edges, we obtain a ( undirected ) tree.

Special trees

There are a number of terms that specify the trees closer. There are, for example,

• Empty trees ( they do not contain nodes and edges ),
• Binary trees,
• Binomial trees,
• Balanced trees and
• Complete binary trees.

Equivalent characterizations of trees

A graph with nodes and edges can be defined by the following equivalent statements as a tree:

• Between each pair of nodes of there is exactly one path.
• Is connected and contains no cycle
• Is continuous and it is. ( There is always an edge less than nodes. )
• Contains no cycle and it is.
• Is minimally coherent, i.e. is connected, but not connected, as soon as one removed from an arbitrary edge.
• Is maximum acyclic, that is, is circular- free, but each additional edge between any two nodes generate a circle.

Trees as a data structure

Rooted trees, particularly out- Trees are frequently used as a data structure. In order limited this can be implemented so that each node has a fixed set of variables or an array of references to his children. Often, the nodes also have a reference to its parent node (back pointer). A tree unlimited order can be implemented by using dynamic arrays instead of lists. In programming languages ​​without dynamic lists is also a method has been proven, in which a general tree is implemented by a binary tree:

The reddish line shows the realized general tree, while the arrows represent the actual pointer structures. The basic principle is that a pointer points each to the leftmost child, while the other on the right sibling node points. Although in this case a direct access to individual specific child node is no longer possible, since you have to progress work on the siblings. For this implementation is very memory efficient.

Drawing of trees

The graphical output of a tree is a non-trivial problem. The general rule is that each tree planar, ie without overlapping the edges can be drawn. Depending on the application, there are more requests to the type of output:

• All edges are straight lines
• All nodes have integer coordinates
• Smallest possible space when possible aesthetic result
• All edges from the parent to the child element strictly decreasing

There are several algorithms whose results look quite different. They usually solve some but not all wishes to the output. Known algorithms are the HV - trees ( horizontal-vertical ) and the algorithm of Walker.

Number of trees

There are several marked trees with nodes. This statement is known as Cayley 's formula.

Generalizations

Forest

A forest is an undirected graph whose connected components are trees.

K- tree

An undirected graph is called k - tree, if it is generated recursively as follows:

• The complete graph is a k- tree.
• If to a k- tree a new node added by a clique of size one associates with all nodes, so this new graph is also a k- tree.

A partial k- tree is created by the removal of edges of a tree: If a k- tree, with a partial k- tree.