Editing Tree (graph theory) (section)

==Definitions==

===Tree===
A ''tree'' is an undirected graph {{mvar|G}} that satisfies any of the following equivalent conditions:
* {{mvar|G}} is [[Connected graph|connected]] and [[Cycle (graph theory)|acyclic]] (contains no cycles).
* {{mvar|G}} is acyclic, and a simple cycle is formed if any [[Edge (graph theory)|edge]] is added to {{mvar|G}}.
* {{mvar|G}} is connected, but would become [[Connectivity (graph theory)#Connected graph|disconnected]] if any single edge is removed from {{mvar|G}}.
* {{mvar|G}} is connected and the [[complete graph]] {{math|''K''{{sub|3}}}} is not a [[Minor (graph theory)|minor]] of {{mvar|G}}.
* Any two vertices in {{mvar|G}} can be connected by a unique [[Path (graph theory)|simple path]].
If {{mvar|G}} has finitely many vertices, say {{mvar|n}} of them, then the above statements are also equivalent to any of the following conditions:
* {{mvar|G}} is connected and has {{math|''n'' − 1}} edges.
* {{mvar|G}} is connected, and every [[subgraph (graph theory)|subgraph]] of {{mvar|G}} includes at least one vertex with zero or one incident edges. (That is, {{mvar|G}} is connected and [[Degeneracy (graph theory)|1-degenerate]].)
* {{mvar|G}} has no simple cycles and has {{math|''n'' − 1}} 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 [[n-connected|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 {{em|internal vertex}} (or inner vertex) is a vertex of [[Degree (graph theory)|degree]] at least 2. Similarly, an {{em|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.<ref>{{cite arXiv |last1=DeBiasio |first1=Louis |last2=Lo |first2=Allan |date=2019-10-09 |title=Spanning trees with few branch vertices |class=math.CO |eprint=1709.04937 }}</ref>

An {{em|irreducible tree}} (or series-reduced tree) is a tree in which there is no vertex of degree 2 (enumerated at sequence {{OEIS link|A000014}} in the [[OEIS]]).{{sfn|Harary|Prins|1959|p=150}}

===Forest===
A {{em|forest}} is an undirected acyclic graph or equivalently a [[disjoint union of graphs|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 {{math|1=''V'' − ''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. {{math|1=''V'' − ''E'' =}} number of trees in a forest.

===Polytree===
{{main|Polytree}}
A {{em|polytree}}<ref name="d99"/> (or ''directed tree''{{sfn|Deo|1974|p=206}} 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 (graph theory)|arborescence]]).<ref>{{cite journal
 | last = Chen | first = Wai-kai
 | doi = 10.1137/0114048
 | journal = [[SIAM Journal on Applied Mathematics]]
 | mr = 209064
 | pages = 550–560
 | title = On directed trees and directed {{mvar|k}}-trees of a digraph and their generation
 | volume = 14
 | year = 1966| issue = 3
 }}</ref><ref name=kozlov>{{cite journal
 | last = Kozlov | first = Dmitry N.
 | doi = 10.1006/jcta.1999.2984
 | issue = 1
 | journal = Journal of Combinatorial Theory
 | mr = 1713484
 | pages = 112–122
 | series = Series A
 | title = Complexes of directed trees
 | volume = 88
 | year = 1999}}</ref><ref>{{citation
 | last1 = Tran | first1 = Ngoc Mai
 | last2 = Buck | first2 = Johannes
 | last3 = Klüppelberg | first3 = Claudia
 | arxiv = 2102.06197
 | date = February 2024
 | doi = 10.1093/jrsssb/qkad165
 | journal = Journal of the Royal Statistical Society Series B: Statistical Methodology
 | title = Estimating a directed tree for extremes| volume = 86
 | issue = 3
 | pages = 771–792
 }}</ref>

===Polyforest===
A {{em|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.

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 [[Arborescence (graph theory)|branching]]).<ref name=kozlov/>

===Rooted tree===
A {{em|rooted tree}} is a tree in which one vertex has been designated the root.{{sfn|Bender|Williamson|2010|p=173}} 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''{{sfn|Deo|1974|p=206}} or ''out-tree'';{{sfn|Deo|1974|p=207}} when it has an orientation towards the root, it is called an ''anti-arborescence'' or ''in-tree''.{{sfn|Deo|1974|p=207}} The tree-order is the [[partial ordering]] on the vertices of a tree with {{math|''u'' < ''v''}} if and only if the unique path from the root to {{mvar|v}} passes through {{mvar|u}}. A rooted tree {{mvar|T}} that is a [[Glossary of graph theory#Subgraphs|subgraph]] of some graph {{mvar|G}} is a [[normal tree]] if the ends of every {{mvar|T}}-path in {{mvar|G}} are comparable in this tree-order {{harv|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; 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 {{mvar|n}} vertices (for nonnegative integers {{mvar|n}}) are typically given the labels {{math|1, 2, …, ''n''}}. A ''[[recursive tree]]'' is a labeled rooted tree where the vertex labels respect the tree order (i.e., if {{math|''u'' < ''v''}} for two vertices {{mvar|u}} and {{mvar|v}}, then the label of {{mvar|u}} is smaller than the label of {{mvar|v}}).

In a rooted tree, the ''parent'' of a vertex {{mvar|v}} is the vertex connected to {{mvar|v}} on the [[Path (graph theory)|path]] to the root; every vertex has a unique parent, except the root has no parent.{{sfn|Bender|Williamson|2010|p=173}} A ''child'' of a vertex {{mvar|v}} is a vertex of which {{mvar|v}} is the parent.{{sfn|Bender|Williamson|2010|p=173}} An ''ascendant'' of a vertex {{mvar|v}} is any vertex that is either the parent of {{mvar|v}} or is (recursively) an ascendant of a parent of {{mvar|v}}. A ''descendant'' of a vertex {{mvar|v}} is any vertex that is either a child of {{mvar|v}} or is (recursively) a descendant of a child of {{mvar|v}}. A ''sibling'' to a vertex {{mvar|v}} is any other vertex on the tree that shares a parent with {{mvar|v}}.{{sfn|Bender|Williamson|2010|p=173}} A ''leaf'' is a vertex with no children.{{sfn|Bender|Williamson|2010|p=173}} An ''internal vertex'' is a vertex that is not a leaf.{{sfn|Bender|Williamson|2010|p=173}}

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 tree]]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 ''[[k-ary tree|{{mvar|k}}-ary tree]]'' (for nonnegative integers {{mvar|k}}) is a rooted tree in which each vertex has at most {{mvar|k}} children.<ref>See {{cite web|url=http://xlinux.nist.gov/dads/HTML/karyTree.html|title=k-ary tree|last=Black|first=Paul E.|date=4 May 2007|publisher=U.S. National Institute of Standards and Technology|access-date=8 February 2015|archive-date=8 February 2015|archive-url=https://web.archive.org/web/20150208124845/http://xlinux.nist.gov/dads/HTML/karyTree.html|url-status=live}}</ref> 2-ary trees are often called ''[[binary tree]]s'', while 3-ary trees are sometimes called ''[[ternary tree]]s''.

=== {{anchor|Plane tree}} Ordered tree===
An ''ordered tree'' (alternatively, ''plane tree'' or ''positional tree''<ref>{{cite book |last1=Cormen |first1=Thomas H. |last2=Leiserson |first2=Charles E. |last3=Rivest |first3=Ronald L. |last4=Stein |first4=Clifford |title=Introduction to Algorithms |date=2022 |publisher=MIT Press |location=Section B.5.3, ''Binary and positional trees'' |isbn=9780262046305 |page=1174 |edition=4th |url=https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ |access-date=20 July 2023 |archive-date=16 July 2023 |archive-url=https://web.archive.org/web/20230716082232/https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ |url-status=live }}</ref>) is a rooted tree in which an ordering is specified for the children of each vertex.{{sfn|Bender|Williamson|2010|p=173}}<ref>{{citation|title=Enumerative Combinatorics, Vol. I|volume=49|series=Cambridge Studies in Advanced Mathematics|first=Richard P.|last=Stanley|author-link=Richard P. Stanley|publisher=Cambridge University Press|year=2012|isbn=9781107015425|page=573|url=https://books.google.com/books?id=0wmJntp8IBQC&pg=PA573}}</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.