In
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, more specifically
graph theoryIn mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a
tree is an undirected graph in which any two
verticesIn graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
are connected by
exactly one simple pathIn graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
. In other words, any
connectedIn mathematics, connectedness is used to refer to various properties meaning, in some sense, "all one piece". When a mathematical object has such a property, we say it is connected; otherwise it is disconnected...
graph without
cyclesIn graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
is a tree. A
forest is a
disjoint unionIn mathematics, the term disjoint union may refer to one of two different concepts:* In set theory, a disjoint union is a modified union operation that indexes the elements according to which set they originated in; disjoint sets have no element in common.* In probability theory , a disjoint union...
of trees.
The various kinds of data structures referred to as
treesIn computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
in
computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
are similar to trees in graph theory, except that computer science trees have directed edges. Although they do not meet the definition given here, these graphs are referred to in graph theory as ordered directed trees (see below).
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
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
is not a minorIn graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
of G.
- Any two vertices in G can be connected by a unique simple path
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
.
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.
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 componentIn graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
s are trees; in other words, the graph consists of a
disjoint unionIn mathematics, the term disjoint union may refer to one of two different concepts:* In set theory, a disjoint union is a modified union operation that indexes the elements according to which set they originated in; disjoint sets have no element in common.* In probability theory , 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
polytreeIn graph theory, a polytree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph for which there are no undirected cycles either...
or
oriented tree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a
directed acyclic graphIn mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
for which there are no undirected cycles either.
A
directed tree is a
directed graphA directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
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
arborescenceIn graph theory, an arborescence is a directed graph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v....
).
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
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 . 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
leaf is a vertex without children.
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
ordered tree or
plane tree is a rooted tree for which an ordering is specified for the children of each vertex.
An
n-ary treeIn graph theory, a k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree.A binary tree is the special case where k=2....
is a rooted tree for which each vertex which is not a leaf has at most
n children.
2-ary trees are sometimes called
binary treeIn computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...
s, while
3-ary trees are sometimes called
ternary treeIn computer science, a ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as "left", “mid” and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a...
s.
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 tree is a bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
and a median graphIn mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m that belongs to shortest paths between any two of a, b, and c.The concept of median graphs has long been studied, for instance by or ...
. Every tree with only countablyIn mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
many vertices is a planar graphIn graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
.
- Every connected graph G admits a spanning tree
In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every vertex...
, which is a tree that contains every vertex of G and whose edges are edges of G.
- Every connected graph with only countably
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
many vertices admits a normal spanning tree .
- There exist connected graphs with uncountably
In mathematics, an uncountable set is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers.-Characterizations:There...
many vertices which do not admit a normal spanning tree .
- Every finite tree with n vertices, with , has at least two terminal vertices (leaves). This minimal number of terminal vertices is characteristic of path graph
In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
s; the maximal number, , is attained by star graphs.
- For any three vertices in a tree, the three paths between them have exactly one vertex in common.
Enumeration
Given
n labeled vertices, there are
nn−2 different ways to connect them to make a tree. This result is called
Cayley's formula. It can be proven by first showing that the number of trees with vertices
1,2,...,n, of degrees
d1,
d2,...,
dn respectively, is the
multinomial coefficientIn mathematics, the multinomial theorem says how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem to polynomials.-Theorem:...
An alternative proof uses
Prüfer sequenceIn combinatorial mathematics, the Prüfer sequence of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n − 2, and can be generated by a simple iterative algorithm...
s. This is the special case for
complete graphIn the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
s of a more general problem, counting the number of
spanning treeSpanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
s in an undirected graph, which can be achieved by computing a
determinantIn linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
according to 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 .
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 toIn mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...
graph isomorphismIn graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
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, ... . proved the asymptotic estimate:
with
C = 0.534949606… and α = 2.99557658565…. (Here,
means that
.) This is a consequence of his asymptotic estimate for the number
of unlabeled rooted trees with
n vertices:
with
D = 0.43992401257… and α the same as above (cf. , Chap. 2.3.4.4 and , Chap. VII.5).
Types of trees
A
star graphIn graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves...
is a tree which either has order
n ≤ 2, or consists of a single internal node (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 terminal vertices (the fewest possible) is a
path graphIn the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
. If all nodes in a tree are within distance one of a central path subgraph, then the tree is a
caterpillar treeIn graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices of the caterpillar are within distance 1 of a central path....
. If all nodes are within distance two of a central path subgraph, then the tree is a lobster.
See also
- Decision tree
A decision tree is a decision support tool that uses a tree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm. Decision trees are commonly used in operations research, specifically...
- Pseudoforest
In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be...
- Tree structure
A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, even though the chart is generally upside down compared to an actual tree, with the "root" at the top and the...
- Tree data structure
- Unrooted binary tree
In mathematics and computer science, an unrooted binary tree is an unrooted tree in which each vertex has either one or three neighbors.-Definitions:...