Tree

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 nodes has graph edges. Conversely, a connected graph with nodes and 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].

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).

A tree 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 of nonisomorphic trees of order , 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

			(1)
			(2)

is related to the generating function for the number of unrooted trees by

			(3)
			(4)

Otter showed that

(5)

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

			(6)
			(7)

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

(8)

The constant is given by

			(9)
			(10)

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

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

(11)

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

(12)

(Plotkin and Rosenthal 1994; Finch 2003).

Wolfram Web Resources