Ingraph theory, atree is anundirected graph in which every pair of distinctvertices is connected byexactly onepath, or equivalently, aconnectedacyclic undirected graph.[1] Aforest is an undirected graph in which any two vertices are connected byat most one path, or equivalently an acyclic undirected graph, or equivalently adisjoint union of trees.[2]
A directed tree,[3] oriented tree,[4][5]polytree,[6] or singly connected network[7] is adirected 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 ofdata structures referred to astrees incomputer science haveunderlying graphs that are trees in graph theory, although such data structures are generallyrooted trees. A rooted tree may be directed, called a directed rooted tree,[8][9] either making all its edges point away from the root—in which case it is called anarborescence[3][10] or out-tree[11][12]—or making all its edges point towards the root—in which case it is called an anti-arborescence[13] or in-tree.[11][14] A rooted tree itself has been defined by some authors as a directed graph.[15][16][17] 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 abranching 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 termtree was coined in 1857 by the British mathematicianArthur Cayley.[18]
Any two vertices inG can be connected by a uniquesimple path.
IfG has finitely many vertices, sayn of them, then the above statements are also equivalent to any of the following conditions:
G is connected and hasn − 1 edges.
G is connected, and everysubgraph ofG includes at least one vertex with zero or one incident edges. (That is,G is connected and1-degenerate.)
G has no simple cycles and hasn − 1 edges.
As elsewhere in graph theory, theorder-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 not0-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.
Aninternal vertex (or inner vertex) is a vertex ofdegree at least 2. Similarly, anexternal 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.[19]
Anirreducible tree (or series-reduced tree) is a tree in which there is no vertex of degree 2 (enumerated at sequenceA000014 in theOEIS).[20]
Aforest is an undirected acyclic graph or equivalently adisjoint 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 treeV −E = 1, we can easily count the number of trees that are within a forest by subtracting the difference between total vertices and total edges.V −E = number of trees in a forest.
Apolytree[6] (ordirected tree[3] ororiented tree[4][5] orsingly connected network[7]) is adirected 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 (seearborescence).[21][22][23]
Apolyforest (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 (seebranching).[22]
Arooted tree is a tree in which one vertex has been designated the root.[24] 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 anarborescence[3] orout-tree;[11] when it has an orientation towards the root, it is called ananti-arborescence orin-tree.[11] The tree-order is thepartial ordering on the vertices of a tree withu <v if and only if the unique path from the root tov passes throughu. A rooted treeT that is asubgraph of some graphG is anormal tree if the ends of everyT-path inG are comparable in this tree-order (Diestel 2005, p. 15). 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; seetree data structure.
In a context where trees typically have a root, a tree without any designated root is called afree tree.
Alabeled tree is a tree in which each vertex is given a unique label. The vertices of a labeled tree onn vertices (for nonnegative integersn) are typically given the labels1, 2, …,n. Arecursive tree is a labeled rooted tree where the vertex labels respect the tree order (i.e., ifu <v for two verticesu andv, then the label ofu is smaller than the label ofv).
In a rooted tree, theparent of a vertexv is the vertex connected tov on thepath to the root; every vertex has a unique parent, except the root has no parent.[24] Achild of a vertexv is a vertex of whichv is the parent.[24] Anascendant of a vertexv is any vertex that is either the parent ofv or is (recursively) an ascendant of a parent ofv. Adescendant of a vertexv is any vertex that is either a child ofv or is (recursively) a descendant of a child ofv. Asibling to a vertexv is any other vertex on the tree that shares a parent withv.[24] Aleaf is a vertex with no children.[24] Aninternal vertex is a vertex that is not a leaf.[24]
Theheight of a vertex in a rooted tree is the length of the longest downward path to a leaf from that vertex. Theheight of the tree is the height of the root. Thedepth 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.
Ak-ary tree (for nonnegative integersk) is a rooted tree in which each vertex has at mostk children.[25] 2-ary trees are often calledbinary trees, while 3-ary trees are sometimes calledternary trees.
Anordered tree (alternatively,plane tree orpositional tree[26]) is a rooted tree in which an ordering is specified for the children of each vertex.[24][27] 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.
Every tree is abipartite 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 connected graphG admits aspanning tree, which is a tree that contains every vertex ofG and whose edges are edges ofG. More specific types spanning trees, existing in every connected finite graph, includedepth-first search trees andbreadth-first search trees. Generalizing the existence of depth-first-search trees, every connected graph with onlycountably many vertices has aTrémaux tree.[28] However, someuncountable-order graphs do not have such a tree.[29]
Every finite tree withn vertices, withn > 1, has at least two terminal vertices (leaves). This minimal number of leaves is characteristic ofpath graphs; the maximal number,n − 1, is attained only bystar 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 amedian graph.
Every tree has acenter consisting of one vertex or two adjacent vertices. The center is the middle vertex or middle two vertices in every longest path. Similarly, everyn-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 thann/2 vertices. In the second case, removal of the edge between the two centroidal vertices splits the tree into two subtrees of exactlyn/2 vertices.
The maximal cliques of a tree are precisely its edges, implying that the class of trees hasfew cliques.
Cayley's formula states that there arenn−2 trees onn labeled vertices. A classic proof usesPrüfer sequences, which naturally show a stronger result: the number of trees with vertices1, 2, …,n of degreesd1,d2, …,dn respectively, is themultinomial coefficient
Counting the number of unlabeled free trees is a harder problem. No closed formula for the numbert(n) of trees withn verticesup tograph isomorphism is known. The first few values oft(n) are
Apath graph (orlinear graph) consists ofn vertices arranged in a line, so that verticesi andi + 1 are connected by an edge fori = 1, …,n – 1.
Astarlike tree consists of a central vertex calledroot and several path graphs attached to it. More formally, a tree is starlike if it has exactly one vertex of degree greater than 2.
Astar tree is a tree which consists of a single internal vertex (andn – 1 leaves). In other words, a star tree of ordern is a tree of ordern with as many leaves as possible.
Acaterpillar tree is a tree in which all vertices are within distance 1 of a central path subgraph.
Alobster tree is a tree in which all vertices are within distance 2 of a central path subgraph.
^Stanley Gill Williamson (1985).Combinatorics for Computer Science. Courier Dover Publications. p. 288.ISBN978-0-486-42076-9.
^Mehran Mesbahi; Magnus Egerstedt (2010).Graph Theoretic Methods in Multiagent Networks. Princeton University Press. p. 38.ISBN978-1-4008-3535-5.
^Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011).Design and Analysis of Approximation Algorithms. Springer Science & Business Media. p. 108.ISBN978-1-4614-1701-9.
^Jonathan L. Gross; Jay Yellen;Ping Zhang (2013).Handbook of Graph Theory, Second Edition. CRC Press. p. 116.ISBN978-1-4398-8018-0.
^Bernhard Korte; Jens Vygen (2012).Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 28.ISBN978-3-642-24488-9.
^Kenneth Rosen (2011).Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 747.ISBN978-0-07-338309-5.
^Alexander Schrijver (2003).Combinatorial Optimization: Polyhedra and Efficiency. Springer. p. 34.ISBN3-540-44389-4.
^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 bookGeometrie der Lage (Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees onpages 20–21. Also in 1847, the German physicistGustav 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"Archived 2023-07-20 at theWayback Machine (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.
^DeBiasio, Louis; Lo, Allan (2019-10-09). "Spanning trees with few branch vertices".arXiv:1709.04937 [math.CO].
^abKozlov, Dmitry N. (1999). "Complexes of directed trees".Journal of Combinatorial Theory. Series A.88 (1):112–122.doi:10.1006/jcta.1999.2984.MR1713484.
^Tran, Ngoc Mai; Buck, Johannes; Klüppelberg, Claudia (February 2024), "Estimating a directed tree for extremes",Journal of the Royal Statistical Society Series B: Statistical Methodology,86 (3):771–792,arXiv:2102.06197,doi:10.1093/jrsssb/qkad165
^SeeBlack, Paul E. (4 May 2007)."k-ary tree". U.S. National Institute of Standards and Technology.Archived from the original on 8 February 2015. Retrieved8 February 2015.
^Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022).Introduction to Algorithms (4th ed.). Section B.5.3,Binary and positional trees: MIT Press. p. 1174.ISBN9780262046305.Archived from the original on 16 July 2023. Retrieved20 July 2023.{{cite book}}: CS1 maint: location (link)
Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree",Journal of Combinatorics, Information & System Sciences,5 (3):184–187,MR0603363.
