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 .

• Trees are always bipartite due to the freedom of circles and can be sorted topologically .

• Trees are planar .

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 ):
  • Binary trees (subdivide one-dimensional data, inner nodes have two children), including complete binary trees , AVL tree and red-black tree ,
  • Quadtrees (subdivide two-dimensional data, inner nodes have four descendants),
  • Octrees (subdivide three-dimensional data, inner nodes have eight descendants),
• 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

→ Main article : spanning tree

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

→ Main article : Wald (graph theory)

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:

• A partial k-tree is a subgraph of a k-tree.

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

See also

• Tree (data structure)
• Tree width
• Nested sets
• Search tree

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 .

See also : literature on graph theory

Web links

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 .
5. ↑ Follow A000055 in OEIS
6. ↑ 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 .
7. ↑ Sven Krumke, Hartmut Noltemeier: Graph Theoretical Concepts and Algorithms . Vieweg + Teubner Verlag, 2012, ISBN 978-3-8348-2264-2 .
8. ↑ Daniel Granot: On some optimization problems on k-trees and partial k-trees . In: Discrete Applied Mathematics . Elsevier, 1994.
9. ↑ Janka Chlebı́ková: Partial k-trees with maximum chromatic number . In: Discrete Applied Mathematics . 2002.
10. ↑ Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki: Edge-Coloring Partial k-Trees . In: Journal of Algorithms . No. 21 , 1996, pp. 598-617 .
11. ↑ Sound Kloks: Treewidth . Springer-Verlag, Berlin / Heidelberg 1994, ISBN 3-540-48672-0 .
12. ↑ A. Yamaguchi, H. Mamitsuka: Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of Spanning Trees . Springer, Berlin / Heidelberg 2003, ISBN 3-540-24587-1 .
13. ↑ Hans L. Bodlaender: A partial k-arboretum of graphs with bounded treewidth . In: Theoretical Computer Science . 1998, p. 1-45 .
14. ^ Jan van Leeuwen: Algorithms and Complexity Theory . In: Handbook of Theoretical Computer Science . vol. A. North Holland, Amsterdam 1990, p. 527-631 .