In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a tree is an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
in which any two
vertices are connected by ''exactly one''
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desire p ...
, or equivalently a
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ''at most one'' path, or equivalently an acyclic undirected graph, or equivalently a
disjoint union
In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A (th ...
of trees.
A
polytree
In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree; . or singly connected network.) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its ...
[See .] (or directed tree or oriented tree
[See .][See .] or singly connected network
[See .]) is a
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
(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
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
referred to as
trees
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
have
underlying graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
s 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,
either making all its edges point away from the root—in which case it is called an
arborescence or out-tree
—or making all its edges point towards the root—in which case it is called an anti-arborescence
or in-tree.
A rooted tree itself has been defined by some authors as a directed graph.
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 "tree" was coined in 1857 by the British mathematician
Arthur Cayley
Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific United Kingdom of Great Britain and Ireland, British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics.
As a child, C ...
.
Definitions
Tree
A ''tree'' is an undirected graph that satisfies any of the following equivalent conditions:
* is
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
and
acyclic (contains no cycles).
* is acyclic, and a simple cycle is formed if any
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
is added to .
* is connected, but would become
disconnected if any single edge is removed from .
* 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. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
is not a
minor
Minor may refer to:
* Minor (law), a person under the age of certain legal activities.
** A person who has not reached the age of majority
* Academic minor, a secondary field of study in undergraduate education
Music theory
*Minor chord
** Barb ...
of .
* Any two vertices in can be connected by a unique
simple path.
If has finitely many vertices, say of them, then the above statements are also equivalent to any of the following conditions:
* is connected and has edges.
* is connected, and every
subgraph of includes at least one vertex with zero or one incident edges. (That is, is connected and
1-degenerate.)
* has no simple cycles and has edges.
As elsewhere in graph theory, the
order-zero graph
In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
Order-zero graph
The order-zero graph, , is th ...
(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 internal vertex (or inner vertex) is a vertex of
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
at least 2. Similarly, an external vertex (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.
An ''irreducible tree'' (or ''series-reduced tree'') is a tree in which there is no vertex of degree 2 (enumerated at sequence in the
OEIS
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
).
Forest
A ''forest'' is an undirected graph in which any two vertices are connected by at most one path. Equivalently, a forest is an undirected acyclic graph, all of whose
connected components are trees; in other words, the graph consists of a
disjoint union
In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A (th ...
of trees. 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 , we can easily count the number of trees that are within a forest by subtracting the difference between total vertices and total edges. number of trees in a forest.
Polytree
A ''polytree''
(or ''directed tree'' or ''oriented tree''
or ''singly connected network''
) is a
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
(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).
Polyforest
A ''polyforest'' (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.
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).
Rooted tree
A ''rooted tree'' is a tree in which one vertex has been designated the ''root''. 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 ''arborescence'' or ''out-tree''; when it has an orientation towards the root, it is called an ''anti-arborescence'' or ''in-tree''. The ''tree-order'' is the
partial ordering
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
on the vertices of a tree with if and only if the unique path from the root to passes through . A rooted tree which is a
subgraph of some graph is a
normal tree if the ends of every -path in are comparable in this tree-order . 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 computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...
.
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 vertices are typically given the labels . A ''
recursive tree
In graph theory, a recursive tree (i.e., unordered tree) is a labeled, rooted tree. A size- recursive tree's vertices are labeled by distinct positive integers , where the labels are strictly increasing starting at the root labeled 1. Recursive ...
'' is a labeled rooted tree where the vertex labels respect the tree order (i.e., if for two vertices and , then the label of is smaller than the label of ).
In a rooted tree, the ''parent'' of a vertex is the vertex connected to on the
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desire p ...
to the root; every vertex has a unique parent except the root which has no parent. A ''child'' of a vertex is a vertex of which is the parent. An ''ascendant'' of a vertex is any vertex which is either the parent of or is (recursively) the ascendant of the parent of . A ''descendant'' of a vertex is any vertex which is either the child of or is (recursively) the descendant of any of the children of . A ''sibling'' to a vertex is any other vertex on the tree which has the same parent as . A ''leaf'' is a vertex with no children. An ''internal vertex'' is a vertex that is not a leaf.
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''). This is commonly needed in the manipulation of the various self-balancing trees,
AVL tree
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any nod ...
s 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 ''
-ary tree'' is a rooted tree in which each vertex has at most children. 2-ary trees are often called ''
binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
s'', while 3-ary trees are sometimes called ''
ternary tree
:
In 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 ...
s''.
Ordered tree
An ''ordered tree'' (or ''plane tree'') is a rooted tree in 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 vertices in an ordered tree can be drawn left-to-right, yielding an essentially unique planar embedding.
Properties
* Every tree is a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
. 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
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
many vertices is a
planar graph
In 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. In other words, it can be drawn in such a way that no edges cross ...
.
* Every connected graph ''G'' admits a
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
, 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
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alon ...
trees and
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...
trees. Generalizing the existence of depth-first-search trees, every connected graph with only
countably
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
many vertices has a
Trémaux tree
In graph theory, a Trémaux tree of an undirected graph G is a type of spanning tree, generalizing depth-first search trees.
They are defined by the property that every edge of G connects an ancestor–descendant pair in the tree. Trémaux trees ar ...
. However, some
uncountable
In mathematics, an uncountable set (or uncountably infinite 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 numb ...
graphs do not have such a tree.
* Every finite tree with ''n'' vertices, with , has at least two terminal vertices (leaves). This minimal number of leaves is characteristic of
path graph
In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...
s; the maximal number, , is attained only by
star graph
In graph theory, a star is the complete bipartite graph a tree (graph theory), tree with one internal node and leaves (but no internal nodes and leaves when ). Alternatively, some authors define to be the tree of order (graph theory), order ...
s. 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
In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest paths between each pair o ...
.
* Every tree has a
center
Center or centre may refer to:
Mathematics
*Center (geometry), the middle of an object
* Center (algebra), used in various contexts
** Center (group theory)
** Center (ring theory)
* Graph center, the set of all vertices of minimum eccentrici ...
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.
Enumeration
Labeled trees
Cayley's formula
In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer n, the number of trees on n labeled vertices is n^.
The formula equivalently counts the number of spanning trees ...
states that there are trees on labeled vertices. A classic proof uses
Prüfer sequence In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) 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 ...
s, which naturally show a stronger result: the number of trees with vertices of degrees respectively, is the
multinomial coefficient
In mathematics, the multinomial theorem describes 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 from binomials to multinomials.
Theorem
For any positive integer an ...
:
A more general problem is to count
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
s in an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
, which is addressed by the
matrix tree theorem
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time ...
. (Cayley's formula is the special case of spanning trees in a
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. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
.) The similar problem of counting all the subtrees regardless of size is
#P-complete in the general case ().
Unlabeled trees
Counting the number of unlabeled free trees is a harder problem. No closed formula for the number of trees with vertices
up to Two Mathematical object, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R''
* if ''a'' and ''b'' are related by ''R'', that is,
* if ''aRb'' holds, that is,
* if the equivalence classes of ''a'' and ''b'' wi ...
graph isomorphism
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H''
: f \colon V(G) \to V(H)
such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...
is known. The first few values of are
: 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … .
proved the asymptotic estimate
:
with and . Here, the symbol means that
:
This is a consequence of his asymptotic estimate for the number of unlabeled rooted trees with vertices:
:
with and the same as above (cf. , chap. 2.3.4.4 and , chap. VII.5, p. 475).
The first few values of are
[See .]
: 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, …
Types of trees
* A ''
path graph
In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...
'' (or ''linear graph'') consists of vertices arranged in a line, so that vertices and are connected by an edge for .
* 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 leaves). In other words, a star tree of order is a tree of order with as many leaves as possible.
* A ''
caterpillar tree
In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.
Caterpillars were first studied in a series of papers by Harary and Schwenk. The name was suggested by Arthur Hobb ...
'' 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 is the infinite tree with edges at each vertex. These arise as the
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayle ...
s of
free group
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
s, and in the theory of
Tits buildings.
See also
*
Decision tree
A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm that only contains condit ...
*
Hypertree
In the mathematical field of graph theory, a hypergraph is called a hypertree if it admits a host graph such that is a tree (graph theory), tree. In other words, is a hypertree if there exists a tree such that every hyperedge of is the set ...
*
Multitree
In combinatorics and Order theory, order-theoretic mathematics, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two Vertex (graph theory), vert ...
*
Pseudoforest
In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every connected component has at most one cycle. Tha ...
*
Tree structure
A tree structure, tree diagram, or tree model 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, although the chart is gener ...
(general)
*
Tree (data structure)
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...
*
Unrooted binary tree
Notes
References
*
* .
*
*
* .
* .
* .
* .
Further reading
* .
*
*
*
* .
* .
{{Authority control
*
Bipartite graphs