# Tree (graph theory)

In graph theory, a tree is a special type of graph that is connected and does not contain closed paths ; H. this can be used to model a monohierarchy . Depending on whether the edges of the tree have a distinct and uniform direction, graph-theoretical trees can be subdivided into undirected trees and rooted trees , and for rooted trees into out-trees , in which the edges start from the root , and in-trees , with edges pointing towards the root.

A tree is a forest with exactly one connected component .

Representation of all trees with one, two or three edges in the first mathematical modeling of trees by Arthur Cayley (1857)

## Definitions

Undirected tree with four inner nodes (black) and five leaves (white)

A tree is a connected circular undirected graph . The nodes with degree 1 are called leaves , the remaining nodes are called inner nodes .

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

A directed tree is a directed graph that is an undirected tree if one ignores the directions of the edges. So it is a directed, weakly connected circular graph . For many authors, the directions must be uniformly oriented away from or towards a node. But there is also the sharper term of the rooted tree.

A Rooted tree is a directed from one node of strongly connected circular free graph . The node defining the strong connection is called the root . It has entry degree 0 and is the only node with this property. All nodes with degree of exit 0 are called leaves . All nodes with a positive initial degree are called inner nodes . This is how the definition of an out-tree works . ${\ displaystyle w}$${\ displaystyle w}$

If the directions of all edges of such a graph are inverted, it becomes an in-tree . This is also seen as a rooted tree.

You can grab and “shake” any undirected tree at any node - gravity gives all edges a defined direction away, which turns the originally undirected tree into a rooted one . ${\ displaystyle w}$${\ displaystyle w}$${\ displaystyle w}$

The edges of an undirected tree can be given different directions and thus directed trees can be derived. Exactly of these are out-trees and just as many are in-trees . Conversely, if you remove the orientation of the edges from a directed tree, you get an undirected tree. ${\ displaystyle m}$ ${\ displaystyle 2 ^ {m}}$${\ displaystyle 2 ^ {m}}$${\ displaystyle n = m + 1}$

## properties

A finite graph with nodes and edges can be defined as a tree using the following equivalent statements: ${\ displaystyle G = (V, E)}$${\ displaystyle | V | = n}$ ${\ displaystyle | E | = m}$

• There is exactly one path between every two nodes of .${\ displaystyle G}$
• ${\ displaystyle G}$is connected and does not contain a circle
• ${\ displaystyle G}$is empty or is contiguous and it holds .${\ displaystyle G}$${\ displaystyle m = n-1}$
• ${\ displaystyle G}$is empty or does not contain a circle and it applies .${\ displaystyle G}$${\ displaystyle m = n-1}$
• ${\ displaystyle G}$is minimally connected, that is, it is connected, but no longer connected, as soon as any edge is removed from it.${\ displaystyle G}$
• ${\ displaystyle G}$is maximally acyclic, i.e. is free of a circle, but every further edge between any two nodes creates a circle.${\ displaystyle G}$

In the case of infinite graphs, the third and fourth conditions must be excluded from the equivalence.

### proofs

• There is exactly one path between every two nodes of .${\ displaystyle G}$

Between each pair of nodes there is at least one path, because each tree connected is. If there were two nodes of with at least two paths, then there would be two nodes and on these paths whose paths do not have a common inner node ( disjoint paths ), for example and . Then a circle of would be contrary to the assumption that a tree is. ${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u, v_ {1}, \ dots, v_ {k}, v}$${\ displaystyle u, u_ {1}, \ dots, u_ {l}, v}$${\ displaystyle u, v_ {1}, \ dots, v_ {k}, v, u_ {l}, \ cdots, u_ {1}, u}$${\ displaystyle G}$${\ displaystyle G}$

• ${\ displaystyle G}$is empty or is contiguous and it holds .${\ displaystyle G}$${\ displaystyle m = n-1}$

This can be shown with complete induction . For , i.e. an empty graph with a single node and no edges , holds . By the induction hypothesis , we assume that the equation holds for every tree with nodes. Is a graph with nodes and the nodes of a longest path of . All neighbors of lying on this path , otherwise he would not be the longest path. is the only neighbor of , otherwise it would contain a circle. We remove and the edge from , we obtain a connected graph, because the only neighbor . The resulting graph has exactly one node and one edge less than , i.e. node. According to the induction hypothesis , the resulting graph has edges. From this it follows that the graph has exactly nodes and edges. ${\ displaystyle n = 1}$${\ displaystyle m = n-1 = 0}$ ${\ displaystyle m = n-1}$${\ displaystyle n-1}$${\ displaystyle G}$${\ displaystyle n}$${\ displaystyle v_ {1}, v_ {2}, \ dots, v_ {k}}$${\ displaystyle G}$${\ displaystyle v_ {1}}$${\ displaystyle v_ {2}}$${\ displaystyle v_ {1}}$${\ displaystyle G}$${\ displaystyle v_ {1}}$${\ displaystyle (v_ {1}, v_ {2})}$${\ displaystyle G}$${\ displaystyle v_ {2}}$${\ displaystyle v_ {1}}$${\ displaystyle G}$${\ displaystyle n-1}$${\ displaystyle m = n-1}$${\ displaystyle m-1 = n-2}$${\ displaystyle G}$${\ displaystyle n}$${\ displaystyle m = n-1}$

• ${\ displaystyle G}$is minimally connected , that is, it is connected, but no longer connected, as soon as any edge is removed from it.${\ displaystyle G}$

If the edge were still connected, then the resulting graph would contain a path from to and would be a circle from . ${\ displaystyle G}$${\ displaystyle e = (u, v)}$${\ displaystyle u, v_ {1}, \ dots, v_ {k}, v}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u, v_ {1}, \ dots, v_ {k}, v, u}$${\ displaystyle G}$

• ${\ displaystyle G}$is maximally acyclic, i.e. is free of a circle, but every further edge between any two nodes creates a circle.${\ displaystyle G}$

If after adding the edge it were still free of a circle, then it would not contain a path from to and would not be contiguous in contradiction to the assumption that a tree is. ${\ displaystyle G}$${\ displaystyle e = (u, v)}$${\ displaystyle G}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle G}$

## Other properties

• By removing an edge , a tree splits into two subtrees and thus forms a forest with two components.
• If you remove a knot together with the adjacent edges, a tree breaks down into a forest of trees, with the degree of the knot removed. If you remove a leaf ( ) from a tree , the rest is still a tree.${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k = 1}$
• Adding an edge between two existing nodes creates a circle in the undirected tree .

## Special trees

There are a number of terms that specify trees in more detail. So there is for example

• the empty graph . This does not contain any nodes or edges .
• the isolated knot with no edges
• linear graph . The inner nodes each have exactly two neighbors.${\ displaystyle P_ {n}}$
• Star graphs or . These contain an inner knot and leaves.${\ displaystyle S_ {n}}$${\ displaystyle K_ {1, n}}$${\ displaystyle n}$
• Caterpillars. All leaves have a maximum distance of 1 from a central path .
• Trees with constant branching factor , i.e. degree of inner nodes ( area tree ):
• Binomial trees have a variable but fixed branching factor. A binomial tree of order k has a root with degree k, whose children the order exactly possess.${\ displaystyle k-1, k-2, \ dots, 0}$
• Trees can be balanced according to their height , the weight of the nodes or the arrangement of the roots .
• Binary tree with node types

• balanced binary tree

• Binomial heap with 13 elements. The keys of the fathers are at most as big as the keys of their children.

• Caterpillar tree

• The star graphs , , and${\ displaystyle S_ {3}}$${\ displaystyle S_ {4}}$${\ displaystyle S_ {5}}$${\ displaystyle S_ {6}}$

## Drawing trees

The graphical output of a tree is not a trivial problem. As a general rule, every tree can be drawn in a planar manner, i.e. without the edges intersecting . Depending on the application, there are further requirements for the type of output:

• all edges are straight lines
• all nodes have integer coordinates
• Smallest possible space requirement with the most aesthetic result possible
• all edges from parent element to child decreasing strictly monotonically

There are different algorithms , the results of which look quite different. Mostly they only solve some, but not all, requests for the output. Well-known algorithms are the HV trees and Walker's algorithm .

## Combinatorics

There are several labeled trees with knots . This statement is known as the Cayley Formula . The checker code provides a simple proof, which enables a bijection between all possible codes of length and all designated trees on nodes. ${\ displaystyle n ^ {n-2}}$${\ displaystyle n}$ ${\ displaystyle n-2}$${\ displaystyle n}$

If the nodes are not numbered, i.e. isomorphic trees (see isomorphism of graphs ) are not counted, this number behaves asymptotically as with and , as Richard Otter proved in 1948. An exact mathematical formula is not known. ${\ displaystyle C \ cdot \ alpha ^ {n} \ cdot n ^ {- {\ tfrac {5} {2}}}}$${\ displaystyle C \ approx 0.534949606}$${\ displaystyle \ alpha \ approx 2,95576528565}$

The following table shows the numbers determined with the help of a computer for : ${\ displaystyle n \ leq 12}$

Number of trees
n with numbered nodes without numbered nodes
1 1 1
2 1 1
3 3 1
4th 16 2
5 125 3
6th 1,296 6th
7th 16.807 11
8th 262.144 23
9 4,782,969 47
10 100,000,000 106
11 2,357,947,691 235
12 61.917.364.224 551

## Spanning trees

Every undirected , connected graph contains a tree spanning it as a subgraph . Minimal spanning trees have the smallest possible number of edges or the smallest possible sum of the edge weights. The calculation of minimal spanning trees is directly used in practice, for example for the creation of cost-effective interconnected networks , such as telephone networks or electrical networks .

## Generalizations

### Forest

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

### k-tree

An undirected graph is called a -tree if it can be generated recursively as follows: ${\ displaystyle k}$

• The full graph is a tree.${\ displaystyle K_ {k}}$${\ displaystyle k}$
• If you add a new node to a -tree by connecting to all nodes of a clique of size from , this new graph is also a -tree.${\ displaystyle k}$${\ displaystyle G}$${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle k}$${\ displaystyle G}$${\ displaystyle k}$

A partial -Tree${\ displaystyle k}$ created by the removal of edges of a -tree: Is a -tree, then with a partial -tree. ${\ displaystyle k}$${\ displaystyle G = (V, E)}$${\ displaystyle k}$${\ displaystyle H = (V, F)}$${\ displaystyle F \ subseteq E}$${\ displaystyle k}$

By the definition given, partial k-trees always have at least k nodes, which is not always desirable. That is why there is also the following definition:

Another property is that the set of partial k-trees is equal to the set of graphs with tree width at most k.

## Remarks

1. Some of the trees shown are isomorphic to one another; namely, both trees in Fig. 2 and in Fig. 3 (counting from the left) trees 1 and 3 and 2 and 4. Only undirected trees are shown. If the topmost node is understood as a root, the result is correspondingly different (heteromorphic) rooted trees.

## literature

• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exact algorithms for difficult graph problems . Springer-Verlag, Berlin / Heidelberg 2010, ISBN 978-3-642-04499-1 .
• Sven Krumke, Hartmut Noltemeier: Graph theoretical concepts and algorithms. 3. Edition. Springer Vieweg Verlag, Wiesbaden 2012, ISBN 978-3-8348-1849-2 .

Commons : Tree structures  - collection of images, videos and audio files

## Individual evidence

1. a b Reinhard Diestel: Graph theory . 3., rework. and exp. Edition. Springer, Berlin 2006, ISBN 3-540-21391-0 , pp. 14 .
2. Angelika Steger: Discrete Structures . 2nd Edition. tape 1 : combinatorics, graph theory, algebra . Springer, Berlin 2007, ISBN 978-3-540-46660-4 , pp. 65 .
3. Stephan Hußmann, Brigitte Lutz-Westphal: Experiencing combinatorial optimization: in studies and lessons . 1st edition. Vieweg, Wiesbaden 2007, ISBN 978-3-528-03216-6 , pp. 47 .
4. ^ Richard Otter: The Number of Trees . In: Annals of Mathematics . 49, No. 3, 1948, pp. 583-599. doi : 10.2307 / 1969046 .