Graph theory

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. A forest is a disjoint union of trees - wikipedia

A ''forest'' is an undirected graph, all of whose connected components are trees; in other words, the graph consists of a disjoint union of trees.

Equivalently, a forest is an undirected acyclic 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), are examples of forests.

A ''polytree'' (or ''oriented tree'' or ''singly connected network'') 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.

A ''directed tree'' is a directed graph which would be a tree if the directions on the edges were ignored, i.e. a polytree.

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 arborescence (Arborescence (graph theory))).

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'', ''branching'', 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 on the vertices of a tree with if and only if the unique path from the root to ''v'' passes through ''u''. A rooted tree which is a subgraph (Glossary of graph theory#Subgraphs) 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''.

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 for two vertices ''u'' and ''v'', then the label of ''u'' is smaller than the label of ''v'').

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 ''descendant'' of any vertex ''v'' is any vertex which is either the child of ''v'' or is (recursively) the descendant of any of the children of ''v''. A ''sibling'' to a vertex ''v'' is any other vertex on the tree which has the same parent as ''v''. The root is an external vertex if it has precisely one child. A leaf is different from the root.

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 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 (tree with no vertices, if such are allowed) has depth and height −1.

A ''k-ary tree'' is a rooted tree in which each vertex has at most ''k'' children. 2-ary trees are often called ''binary trees'', while 3-ary trees are sometimes called ''ternary trees''.

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 .