Tree (graph theory)

Trees

A labeled tree with 6 vertices and 5 edges.
Vertices v
Edges v − 1
Chromatic number 2 if v > 1

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. A forest is a disjoint union of trees.

The various kinds of data structures referred to as trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees. A rooted tree may be directed, called a directed rooted tree,[1][2] either making all its edges point away from the root—in which case it is called an arborescence,[3] branching,[4] or out-tree[4]—, or making all its edges point towards the root—in which case it is called an anti-arborescence[5] or in-tree.[6] A rooted tree itself has been defined by some authors as a directed graph.[7][8][9]

The term "tree" was coined in 1857 by the British mathematician Arthur Cayley.[10]

Definitions

Tree

A tree is an undirected graph G that satisfies any of the following equivalent conditions:

If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions:

As elsewhere in graph theory, the order-zero graph (graph with no vertices) is generally excluded from consideration: while it is vacuously connected as a graph (any two vertices can be connected by a path), it is not 0-connected (or even (−1)-connected) in algebraic topology, unlike non-empty trees, and violates the "one more vertex than edges" relation.

An internal vertex (or inner vertex or branch vertex) is a vertex of degree at least 2. Similarly, an external vertex (or outer vertex, terminal vertex or leaf) is a vertex of degree 1.

An irreducible tree (or series-reduced tree) is a tree in which there is no vertex of degree 2.

Forest

A forest is an undirected graph, all of whose connected components are trees; in other words, the graph consists of a disjoint union of trees. Equivalently, a forest is an undirected acyclic graph. As special cases, an empty graph, a single tree, and the discrete graph on a set of vertices (that is, the graph with these vertices that has no edges), are examples of forests.

The term hedge sometimes refers to an ordered sequence of trees.

Polytree

Main article: Polytree

A polytree[11] (or oriented tree[12][13] or singly connected network[14]) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic.

A directed tree is a directed graph which would be a tree if the directions on the edges were ignored, i.e. a polytree. Some authors restrict the phrase to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence).

Rooted tree

A rooted tree is a tree in which one vertex has been designated the root. The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. When a directed rooted tree has an orientation away from the root, it is called an arborescence, branching, or out-tree; when it has an orientation towards the root, it is called an anti-arborescence or in-tree. The tree-order is the partial ordering on the vertices of a tree with u < v if and only if the unique path from the root to v passes through u. A rooted tree which is a subgraph of some graph G is a normal tree if the ends of every edge in G are comparable in this tree-order whenever those ends are vertices of the tree (Diestel 2005, p. 15). Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science; see tree data structure.

In a context where trees are supposed to have a root, a tree without any designated root is called a free tree.

A labeled tree is a tree in which each vertex is given a unique label. The vertices of a labeled tree on n vertices are typically given the labels 1, 2, …, n. A recursive tree is a labeled rooted tree where the vertex labels respect the tree order (i.e., if u < v for two vertices u and v, then the label of u is smaller than the label of v).

In a rooted tree, the parent of a vertex is the vertex connected to it on the path to the root; every vertex except the root has a unique parent. A child of a vertex v is a vertex of which v is the parent. A descendent of any vertex v is any vertex which is either the child of v or is (recursively) the descendent of any of the children of v. A sibling to a vertex v is any other vertex on the tree which has the same parent as v. The root is an external vertex if it has precisely one child. A leaf is different from the root.

The height of a vertex in a rooted tree is the length of the longest downward path to a leaf from that vertex. The height of the tree is the height of the root. The depth of a vertex is the length of the path to its root (root path). This is commonly needed in the manipulation of the various self-balancing trees, AVL trees in particular. The root has depth zero, leaves have height zero, and a tree with only a single vertex (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no vertices, if such are allowed) has depth and height −1.

A k-ary tree is a rooted tree in which each vertex has at most k children.[15] 2-ary trees are often called binary trees, while 3-ary trees are sometimes called ternary trees.

Ordered tree

An ordered tree (or plane tree) is a rooted tree in which an ordering is specified for the children of each vertex. This is called a "plane tree" because an ordering of the children is equivalent to an embedding of the tree in the plane, with the root at the top and the children of each vertex lower than that vertex. Given an embedding of a rooted tree in the plane, if one fixes a direction of children, say left to right, then an embedding gives an ordering of the children. Conversely, given an ordered tree, and conventionally drawing the root at the top, then the child vertices in an ordered tree can be drawn left-to-right, yielding an essentially unique planar embedding .

Facts

Enumeration

Labeled trees

Cayley's formula states that there are nn−2 trees on n labeled vertices. It can be proved by first showing that the number of trees with vertices 1, 2, …, n of degrees d1, d2, …, dn respectively, is the multinomial coefficient

{n - 2 \choose d_1 - 1, d_2 - 1, \ldots, d_n - 1}.

An alternative proof uses Prüfer sequences.

Cayley's formula is the special case of complete graphs in a more general problem of counting spanning trees in an undirected graph, which is addressed by the matrix tree theorem. The similar problem of counting all the subtrees regardless of size has been shown to be #P-complete in the general case (Jerrum (1994)).

Unlabeled trees

Counting the number of unlabeled free trees is a harder problem. No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. The first few values of t(n) are

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (sequence A000055 in OEIS).

Otter (1948) proved the asymptotic estimate

t(n) \sim C \alpha^n n^{-5/2} \quad\text{as } n\to\infty,

with the values C and α known to be approximately 0.534949606… and 2.95576528565… (sequence A051491 in OEIS), respectively. (Here, f ~ g means that limn→∞ f /g = 1.) This is a consequence of his asymptotic estimate for the number r(n) of unlabeled rooted trees with n vertices:

r(n) \sim D\alpha^n n^{-3/2} \quad\text{as } n\to\infty,

with D around 0.43992401257… and the same α as above (cf. Knuth (1997), chap. 2.3.4.4 and Flajolet & Sedgewick (2009), chap. VII.5, p. 475).

The first few values of r(n) are[16]

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, …

Types of trees

See also

Notes

  1. ↑ Stanley Gill Williamson (1985). Combinatorics for Computer Science. Courier Dover Publications. p. 288. ISBN 978-0-486-42076-9.
  2. ↑ Mehran Mesbahi; Magnus Egerstedt (2010). Graph Theoretic Methods in Multiagent Networks. Princeton University Press. p. 38. ISBN 1-4008-3535-6.
  3. ↑ Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011). Design and Analysis of Approximation Algorithms. Springer Science & Business Media. p. 108. ISBN 978-1-4614-1701-9.
  4. 1 2 Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition. CRC Press. p. 116. ISBN 978-1-4398-8018-0.
  5. ↑ Bernhard Korte; Jens Vygen (2012). Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 28. ISBN 978-3-642-24488-9.
  6. ↑ Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-0.
  7. ↑ David Makinson (2012). Sets, Logic and Maths for Computing. Springer Science & Business Media. pp. 167–168. ISBN 978-1-4471-2499-3.
  8. ↑ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 747. ISBN 978-0-07-338309-5.
  9. ↑ Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer. p. 34. ISBN 3-540-44389-4.
  10. ↑ Cayley (1857) "On the theory of the analytical forms called trees," Philosophical Magazine, 4th series, 13 : 172–176.
    However it should be mentioned that in 1847, K.G.C. von Staudt, in his book Geometrie der Lage (Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees on pages 20–21. Also in 1847, the German physicist Gustav Kirchhoff investigated electrical circuits and found a relation between the number (n) of wires/resistors (branches), the number (m) of junctions (vertices), and the number (μ) of loops (faces) in the circuit. He proved the relation via an argument relying on trees. See: Kirchhoff, G. R. (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" (On the solution of equations to which one is led by the investigation of the linear distribution of galvanic currents), Annalen der Physik und Chemie, 72 (12) : 497–508.
  11. ↑ See Dasgupta (1999).
  12. ↑ See Harary & Sumner (1980).
  13. ↑ See Simion (1991).
  14. ↑ See Kim & Pearl (1983).
  15. ↑ See Black, Paul E. (4 May 2007). "k-ary tree". U.S. National Institute of Standards and Technology. Retrieved 8 February 2015.
  16. ↑ See Li (1996).

References

Further reading

Wikimedia Commons has media related to Tree (graph theory).
This article is issued from Wikipedia - version of the Saturday, April 23, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.