Rooted tree

Trees
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 simple path. In other words, any connected graph without simple cycles is a tree. A forest is a disjoint union of trees.

The various kinds of data structures referred to as trees in computer science are equivalent as undirected graphs to trees in graph theory, although such data structures are generally rooted trees, thus in fact being directed graphs, and may also have additional ordering of branches.

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

Definitions

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

  • G is connected and has no cycles.
  • G has no cycles, and a simple cycle is formed if any edge is added to G.
  • G is connected, but is not connected if any single edge is removed from G.
  • G is connected and the 3-vertex complete graph K_3 is not a minor of G.
  • Any two vertices in G can be connected by a unique simple path.

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

  • G is connected and has n − 1 edges.
  • G has no simple cycles and has n − 1 edges.

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 node than edges" relation.

A leaf is a vertex of degree 1. An internal vertex is a vertex of degree at least 2.

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

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 cycle-free 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), all are examples of forests.

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

A polytree[2] (also known as oriented tree[3][4] or singly connected network[5]) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. In other words, if we replace its arcs with 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. 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).

A tree is called a rooted tree if one vertex has been designated the root, in which case the edges have a natural orientation, towards or away from the root. The tree-order is the partial ordering on the vertices of a tree with uv 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.

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

An n-ary tree is a rooted tree for which each vertex has at most n children. 2-ary trees are sometimes called binary trees, while 3-ary trees are sometimes called ternary trees.

A terminal vertex of a tree is a vertex of degree 1. In a rooted tree, the leaves are all terminal vertices; additionally, the root, if not a leaf itself, is a terminal vertex if it has precisely one child.

Plane Tree

An ordered tree or plane tree is a rooted tree for 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 nodes in an ordered tree can be drawn left-to-right, yielding an essentially unique planar embedding .

A leaf in a rooted tree is a vertex of degree 1 that is not the root. A terminal vertex of a tree is a vertex of degree 1. In a rooted tree, the leaves are all terminal vertices; additionally, the root, if not a leaf itself, is a terminal vertex if it has precisely one child.

Example

The example tree shown to the right has 6 vertices and 6 − 1 = 5 edges. The unique simple path connecting the vertices 2 and 6 is 2-4-5-6.

Facts

  • Every connected graph G admits a spanning tree, which is a tree that contains every vertex of G and whose edges are edges of G.
  • Every connected graph with only countably many vertices admits a normal spanning tree (Diestel 2005, Prop. 8.2.4).
  • There exist connected graphs with uncountably many vertices which do not admit a normal spanning tree (Diestel 2005, Prop. 8.5.2).
  • Every finite tree with n vertices, with n > 1, has at least two terminal vertices (leaves). This minimal number of terminal vertices is characteristic of path graphs; the maximal number, n − 1, is attained by star graphs.
  • For any three vertices in a tree, the three paths between them have exactly one vertex in common.

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

Otter (1948) proved the asymptotic estimate:

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

with C = 0.534949606… and α = 2.95576528565… (sequence OEIS). (Here, f \sim g means that \lim_{n \to \infty} 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 = 0.43992401257… and α the same as above (cf. Knuth (1997), Chap. 2.3.4.4 and Flajolet & Sedgewick (2009), Chap. VII.5).

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

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

Types of trees

A star graph is a tree which consists of a single internal vertex (and n − 1 leaves). In other words, a star graph of order n is a tree of order n with as many leaves as possible. Its diameter is at most 2.

A tree with two leaves (the fewest possible) is a path graph; a forest in which all components are isolated nodes and path graphs is called a linear forest. If all vertices in a tree are within distance one of a central path subgraph, then the tree is a caterpillar tree. If all vertices are within distance two of a central path subgraph, then the tree is a lobster.

See also

Notes

References

  • .
  • .
  • .
  • .
  • .

Further reading

  • .
  • Template:Springer
  • .
  • .
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.