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

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

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

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 treeSee .See . or singly connected networkSee .) 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 v ...

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

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 practical disciplines (includin ...

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 British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics. As a child, Cayley enjoyed solving complex maths problems ...

Definitions

Tree

A ''tree'' is an undirected graph that satisfies any of the following equivalent conditions: * is

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

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 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 ** Bar ...

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

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

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

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

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

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 Normal(s) or The Normal(s) may refer to: Film and television * ''Normal'' (2003 film), starring Jessica Lange and Tom Wilkinson * ''Normal'' (2007 film), starring Carrie-Anne Moss, Kevin Zegers, Callum Keith Rennie, and Andrew Airlie * ''Norma ...

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

. 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

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 i