Tree (graph theory)

In graph theory, a tree is an undirected graph in which any two vertices are connected by Template:Em path, or equivalently a connected acyclic undirected graph.Template:Sfn A forest is an undirected graph in which any two vertices are connected by Template:Em path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.Template:Sfn

A directed tree,Template:Sfn oriented tree,<ref name="Harary 1980">See Template:Harvtxt.</ref><ref name="s91">See Template:Harvtxt.</ref> polytree,<ref name="d99">See Template:Harvtxt.</ref> or singly connected network<ref name="kp83">See Template:Harvtxt.</ref> is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest.

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,<ref name="Williamson1985">Template:Cite book</ref><ref name="multi">Template:Cite book</ref> either making all its edges point away from the root—in which case it is called an arborescenceTemplate:Sfn<ref name="DuKo2011">Template:Cite book</ref> or out-treeTemplate:Sfn<ref name="GrossYellen2013">Template:Cite book</ref>—or making all its edges point towards the root—in which case it is called an anti-arborescence<ref name="KorteVygen2012b">Template:Cite book</ref> or in-tree.Template:Sfn<ref name="MehlhornSanders2008">Template:Cite book</ref> A rooted tree itself has been defined by some authors as a directed graph.<ref name="Makinson2012">Template:Cite book</ref><ref>Template:Cite book</ref><ref name="Schrijver2003">Template:Cite book</ref> A rooted forest is a disjoint union of rooted trees. A rooted forest may be directed, called a directed rooted forest, either making all its edges point away from the root in each rooted tree—in which case it is called a branching or out-forest—or making all its edges point towards the root in each rooted tree—in which case it is called an anti-branching or in-forest.

The term Template:Em was coined in 1857 by the British mathematician Arthur Cayley.<ref>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" Template:Webarchive (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.</ref>

Definitions

Tree

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

• Template:Mvar is connected and acyclic (contains no cycles).
• Template:Mvar is acyclic, and a simple cycle is formed if any edge is added to Template:Mvar.
• Template:Mvar is connected, but would become disconnected if any single edge is removed from Template:Mvar.
• Template:Mvar is connected and the complete graph Template:Math is not a minor of Template:Mvar.
• Any two vertices in Template:Mvar can be connected by a unique simple path.

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

• Template:Mvar is connected and has Template:Math edges.
• Template:Mvar is connected, and every subgraph of Template:Mvar includes at least one vertex with zero or one incident edges. (That is, Template:Mvar is connected and 1-degenerate.)
• Template:Mvar has no simple cycles and has Template:Math edges.

As elsewhere in graph theory, the order-zero graph (graph with no vertices) is generally not considered to be a tree: 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. It may, however, be considered as a forest consisting of zero trees.

An Template:Em (or inner vertex) is a vertex of degree at least 2. Similarly, an Template:Em (or outer vertex, terminal vertex or leaf) is a vertex of degree 1. A branch vertex in a tree is a vertex of degree at least 3.<ref>Template:Cite arXiv</ref>

An Template:Em (or series-reduced tree) is a tree in which there is no vertex of degree 2 (enumerated at sequence A000014 in the OEIS).Template:Sfn

Forest

A Template:Em is an undirected acyclic graph or equivalently a disjoint union of trees. Trivially so, each connected component of a forest is a tree. As special cases, the order-zero graph (a forest consisting of zero trees), a single tree, and an edgeless graph, are examples of forests. Since for every tree Template:Math, we can easily count the number of trees that are within a forest by subtracting the difference between total vertices and total edges. Template:Math number of trees in a forest.

Polytree

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} A Template:Em<ref name="d99"/> (or directed treeTemplate:Sfn or oriented tree<ref name="Harary 1980"/><ref name="s91"/> or singly connected network<ref name="kp83"/>) 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.

Some authors restrict the phrase "directed tree" to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence).<ref>Template:Cite journal</ref><ref name=kozlov>Template:Cite journal</ref><ref>Template:Citation</ref>

Polyforest

A Template:Em (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic.

As with directed trees, some authors restrict the phrase "directed forest" to the case where the edges of each connected component are all directed towards a particular vertex, or all directed away from a particular vertex (see branching).<ref name=kozlov/>

Rooted tree

A Template:Em is a tree in which one vertex has been designated the root.Template:Sfn 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 arborescenceTemplate:Sfn or out-tree;Template:Sfn when it has an orientation towards the root, it is called an anti-arborescence or in-tree.Template:Sfn The tree-order is the partial ordering on the vertices of a tree with Template:Math if and only if the unique path from the root to Template:Mvar passes through Template:Mvar. A rooted tree Template:Mvar that is a subgraph of some graph Template:Mvar is a normal tree if the ends of every Template:Mvar-path in Template:Mvar are comparable in this tree-order Template:Harv. Rooted trees, often with an additional structure such as an ordering of the neighbors at each vertex, are a key data structure in computer science; see tree data structure.

In a context where trees typically 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 Template:Mvar vertices (for nonnegative integers Template:Mvar) are typically given the labels Template:Math. A recursive tree is a labeled rooted tree where the vertex labels respect the tree order (i.e., if Template:Math for two vertices Template:Mvar and Template:Mvar, then the label of Template:Mvar is smaller than the label of Template:Mvar).

In a rooted tree, the parent of a vertex Template:Mvar is the vertex connected to Template:Mvar on the path to the root; every vertex has a unique parent, except the root has no parent.Template:Sfn A child of a vertex Template:Mvar is a vertex of which Template:Mvar is the parent.Template:Sfn An ascendant of a vertex Template:Mvar is any vertex that is either the parent of Template:Mvar or is (recursively) an ascendant of a parent of Template:Mvar. A descendant of a vertex Template:Mvar is any vertex that is either a child of Template:Mvar or is (recursively) a descendant of a child of Template:Mvar. A sibling to a vertex Template:Mvar is any other vertex on the tree that shares a parent with Template:Mvar.Template:Sfn A leaf is a vertex with no children.Template:Sfn An internal vertex is a vertex that is not a leaf.Template:Sfn

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). The depth of a tree is the maximum depth of any vertex. Depth 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 (a tree with no vertices, if such are allowed) has depth and height −1.

A [[k-ary tree|Template:Mvar-ary tree]] (for nonnegative integers Template:Mvar) is a rooted tree in which each vertex has at most Template:Mvar children.<ref>See {{#invoke:citation/CS1|citation |CitationClass=web }}</ref> 2-ary trees are often called binary trees, while 3-ary trees are sometimes called ternary trees.

Template:Anchor Ordered tree

An ordered tree (alternatively, plane tree or positional tree<ref>Template:Cite book</ref>) is a rooted tree in which an ordering is specified for the children of each vertex.Template:Sfn<ref>Template:Citation</ref> 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.

Properties

• Every tree is a bipartite graph. A graph is bipartite if and only if it contains no cycles of odd length. Since a tree contains no cycles at all, it is bipartite.
• Every tree with only countably many vertices is a planar graph.
• 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. More specific types spanning trees, existing in every connected finite graph, include depth-first search trees and breadth-first search trees. Generalizing the existence of depth-first-search trees, every connected graph with only countably many vertices has a Trémaux tree.Template:Sfnp However, some uncountable-order graphs do not have such a tree.Template:Sfnp
• Every finite tree with n vertices, with Template:Nowrap, has at least two terminal vertices (leaves). This minimal number of leaves is characteristic of path graphs; the maximal number, Template:Nowrap, is attained only by star graphs. The number of leaves is at least the maximum vertex degree.
• For any three vertices in a tree, the three paths between them have exactly one vertex in common. More generally, a vertex in a graph that belongs to three shortest paths among three vertices is called a median of these vertices. Because every three vertices in a tree have a unique median, every tree is a median graph.
• Every tree has a center consisting of one vertex or two adjacent vertices. The center is the middle vertex or middle two vertices in every longest path. Similarly, every n-vertex tree has a centroid consisting of one vertex or two adjacent vertices. In the first case removal of the vertex splits the tree into subtrees of fewer than n/2 vertices. In the second case, removal of the edge between the two centroidal vertices splits the tree into two subtrees of exactly n/2 vertices.
• The maximal cliques of a tree are precisely its edges, implying that the class of trees has few cliques.

Enumeration

Labeled trees

Cayley's formula states that there are Template:Math trees on Template:Mvar labeled vertices. A classic proof uses Prüfer sequences, which naturally show a stronger result: the number of trees with vertices Template:Math of degrees Template:Math respectively, is the multinomial coefficient

<math>{n - 2 \choose d_1 - 1, d_2 - 1, \ldots, d_n - 1}.</math>

A more general problem is to count spanning trees in an undirected graph, which is addressed by the matrix tree theorem. (Cayley's formula is the special case of spanning trees in a complete graph.) The similar problem of counting all the subtrees regardless of size is #P-complete in the general case (Template:Harvtxt).

Unlabeled trees

Counting the number of unlabeled free trees is a harder problem. No closed formula for the number Template:Math of trees with Template:Mvar vertices up to graph isomorphism is known. The first few values of Template:Math are

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

Template:Harvtxt proved the asymptotic estimate

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

with Template:Math and Template:Math (sequence A051491 in the OEIS). Here, the Template:Math symbol means that

<math>\lim_{n \to \infty} \frac{t(n)}{C \alpha^n n^{-5/2} } = 1.</math>

This is a consequence of his asymptotic estimate for the number Template:Math of unlabeled rooted trees with Template:Mvar vertices:

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

with Template:Math and the same Template:Mvar as above (cf. Template:Harvtxt, chap. 2.3.4.4 and Template:Harvtxt, chap. VII.5, p. 475).

The first few values of Template:Math are<ref>See Template:Harvtxt.</ref>

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … (sequence A000081 in the OEIS).

Types of trees

• A path graph (or linear graph) consists of Template:Mvar vertices arranged in a line, so that vertices Template:Mvar and Template:Math are connected by an edge for Template:Math.
• A starlike tree consists of a central vertex called root and several path graphs attached to it. More formally, a tree is starlike if it has exactly one vertex of degree greater than 2.
• A star tree is a tree which consists of a single internal vertex (and Template:Math leaves). In other words, a star tree of order Template:Mvar is a tree of order Template:Mvar with as many leaves as possible.
• A caterpillar tree is a tree in which all vertices are within distance 1 of a central path subgraph.
• A lobster tree is a tree in which all vertices are within distance 2 of a central path subgraph.
• A regular tree of degree Template:Mvar is the infinite tree with Template:Mvar edges at each vertex. These arise as the Cayley graphs of free groups, and in the theory of Tits buildings. In statistical mechanics they are known as Bethe lattices.

See also

• Decision tree
• Hypertree
• Multitree
• Pseudoforest
• Tree structure (general)
• Tree (data structure)
• Unrooted binary tree

References

• Template:Citation
• Template:Citation.
• Template:Citation
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.

Further reading

• Template:Citation.
• Template:Citation
• Template:Springer
• Template:Citation
• Template:Citation.
• Template:Citation.