TOPICS
Search

Tree


Trees

A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph.

Trees were first studied by Cayley (1857). McKay maintains a database of trees up to 18 vertices, and Royle maintains one up to 20 vertices.

A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph (or, equivalently, a connected forest). A tree with n nodes has n-1 graph edges. Conversely, a connected graph with n nodes and n-1 edges is a tree. All trees are bipartite graphs (Skiena 1990, p. 213). Trees with no particular node singled out are sometimes called free trees (or unrooted tree), by way of distinguishing them from rooted trees (Skiena 1990, Knuth 1997).

The points of connection are known as forks and the segments as branches. Final segments and the nodes at their ends are called tree leaves. A tree with two branches at each fork and with one or two tree leaves at the end of each branch is called a binary tree.

A graph can be tested in the Wolfram Language to see if it is a tree using TreeGraphQ[g].

Hydrocarbons

Trees find applications in many diverse fields, including computer science, the enumeration of saturated hydrocarbons, the study of electrical circuits, etc. (Harary 1994, p. 4). The graphs graphs corresponding to linear hydrocarbons illustrated above are known as (n-)alkane graphs (or sometimes caterpillar graphs).

Trees are block graphs.

A tree T has either one node that is a graph center, in which case it is called a centered tree, or two adjacent nodes that are graph centers, in which case it is called a bicentered tree (Harary 1994, p. 35).

When a special node is designated to turn a tree into a rooted tree, it is called the root (or sometimes "Eve"). In such a tree, each of the nodes that is one graph edge further away from a given node is called a child, and nodes connected to the same node that are the same distance from the root vertex are called siblings.

Note that two branches placed end-to-end are equivalent to a single branch, which means for example, that there is only one tree of order 3. The number t(n) of nonisomorphic trees of order n=1, 2, ... (where trees of orders 1, 2, ..., 6 are illustrated above), are 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, ... (OEIS A000055).

The generating functions for the number of rooted trees

T(x)=sum_(n=1)^(infty)T_nx^n
(1)
=xexp[sum_(r=1)^(infty)1/rT(x^r)]
(2)

is related to the generating function for the number of unrooted trees t(x) by

t(x)=sum_(n=1)^(infty)t_nx^n
(3)
=T(x)-1/2[T^2(x)-T(x^2)].
(4)

Otter showed that

 lim_(n->infty)(t_nn^(5/2))/(alpha^n)=beta,
(5)

(Otter 1948, Harary and Palmer 1973, Knuth 1997), where alpha and beta are two constants. alpha is given by

alpha=lim_(n->infty)(T_n)/(T_(n-1))
(6)
=2.955765...
(7)

(OEIS A051491; Odlyzko 1995; Knuth 1997, p. 396, where Knuth writes 1/alpha=2.9557... instead of alpha=2.9557...) and also as the unique positive root of

 T(1/x)=1.
(8)

The constant beta is given by

beta=1/(sqrt(2pi))[1+sum_(k=2)^(infty)T^'(1/(alpha^k))1/(alpha^k)]^(3/2)
(9)
=0.5349485...
(10)

(OEIS A086308; Knuth 1997, p. 396).

If t_n is the number of nonisomorphic trees on n nodes, then an asymptotic series for t_n is given by

 t_n∼alpha^nn^(-5/2)(0.5349496061...+(0.0441699018...)/n+(0.4853877311...)/(n^2)+(2.379745574...)/(n^3)+...),
(11)

where the constants can be computed in terms of partial derivatives of the function

 F(x,y)=xexp[y+sum_(k=2)^infty(T(x^k))/k]-y
(12)

(Plotkin and Rosenthal 1994; Finch 2003).


See also

Alkane Graph, B-Tree, Banana Tree, Barnsley's Tree, Bicentered Tree, Binary Tree, Caterpillar Graph, Cayley Tree, Centered Tree, Child, Dijkstra Tree, Extended Binary Tree, Forest, Free Tree, k-Tree, Kruskal's Algorithm, Kruskal's Tree Theorem, Labeled Tree, Lobster Graph, Mandelbrot Tree, Matrix Tree Theorem, Orchard-Planting Problem, Ordered Tree, Otter's Theorem, Path Graph, Planted Planar Tree, Pólya Enumeration Theorem, Polynema, Pythagoras Tree, Quadtree, Ramus Tree, Red-Black Tree, Root Vertex, Rooted Tree, Series-Reduced Tree, Sibling, Spanning Tree, Star Graph, Steiner Tree, Stern-Brocot Tree, Tree Decomposition, Tree Leaf, Tree Searching, Weakly Binary Tree, Weighted Tree Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Finch, S. R. "Otter's Tree Enumeration Constants." §5.6 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 295-316, 2003.Bergeron, F.; Leroux, P.; and Labelle, G. Combinatorial Species and Tree-Like Structures. Cambridge, England: Cambridge University Press, p. 284, 1998.Cayley, A. "On the Theory of Analytic Forms Called Trees." Philos. Mag. 13, 19-30, 1857. Reprinted in Mathematical Papers, Vol. 3. Cambridge: pp. 242-246, 1891.Chauvin, B.; Cohen, S.; and Rouault, A. (Eds.). Trees: Workshop in Versailles, June 14-16, 1995. Basel, Switzerland: Birkhäuser, 1996.Finch, S. "Two Asymptotic Series." December 10, 2003. http://algo.inria.fr/bsolve/.Gardner, M. "Trees." Ch. 17 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, pp. 240-250, 1978.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Harary, F. "Trees." Ch. 4 in Graph Theory. Reading, MA: Addison-Wesley, pp. 32-42, 187-194, and 231-234, 1994.Harary, F. and Manvel, B. "Trees." Scripta Math. 28, 327-333, 1970.Harary, F. and Palmer, E. M. "Trees." Ch. 3 in Graphical Enumeration. New York: Academic Press, pp. 51-80, 1973.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.König, D. Theorie der endlichen und unendlichen Graphen. New York: Chelsea, p. 48, 1950.McKay, B. D. "Trees Sorted by Diameter." http://cs.anu.edu.au/~bdm/data/trees.html.Nijenhuis, A. and Wilf, H. Combinatorial Algorithms for Computers and Calculators, 2nd ed. New York: Academic Press, 1978.Odlyzko, A. M. "Asymptotic Enumeration Methods." In Handbook of Combinatorics, Vol. 2 (Ed. R. L. Graham, M. Grötschel, and L. Lovász). Cambridge, MA: MIT Press, pp. 1063-1229, 1995. http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.pdf.Otter, R. "The Number of Trees." Ann. Math. 49, 583-599, 1948.Plotkin, J. M. and Rosenthal, J. W. "How to Obtain an Asymptotic Expansion of a Sequence from an Analytic Identity Satisfied by Its Generating Function." J. Austral. Math. Soc. Ser. A 56, 131-143, 1994.Royle, G. "Trees On Up to 16 [sic] Vertices." http://school.maths.uwa.edu.au/~gordon/remote/graphs/#trees.Skiena, S. "Trees." Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 107 and 151-153, 1990.Sloane, N. J. A. Sequences A000055/M0791, A051491, and A086308 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M0791 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.Wilf, H. S. Combinatorial Algorithms: An Update. Philadelphia, PA: SIAM, 1989.

Referenced on Wolfram|Alpha

Tree

Cite this as:

Weisstein, Eric W. "Tree." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Tree.html

Subject classifications