Tree (graph theory)

A tree is an undirected graph which is both connected and acyclic. Equivalently, a tree is a graph $G=(V,E)$ such that for any two vertices $u, v \in V$ with $u \neq v$ , there is exactly one path connecting $u$ and $v$ in $G$ . Every tree that has $|V|=n$ vertices has exactly $n-1$ edges.

The converse is also true: an undirected and connected graph with $n$ vertices and $n-1$ edges is a tree.

A forest is an undirected graph where there is at most one path from any vertex to another. A forest is an undirected graph that is acyclic in which all connected components are trees; it is a disjoint union of trees. The number of trees in a forest could be found by $|V|-|E|$ .

Rooted Tree

A rooted tree is a tree that has a node designated as the root. We can assign the nodes directions going either to the root or outwards from the root.

For every node except the root, there is only $1$ parent; the parent is the other end of the edge going into the node, assuming the edges are going out from the root. Childs of a node is the nodes where this node's outward edges reach (assuming the edges are going out 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 depth of a vertex is the length of the path going from the root to itself. The height of a tree is the height of the root. The depth of a tree is the maximum depth of all vertices in the tree.

A $\boldsymbol{k}$ -ary tree is a tree in which all nodes have at most $k$ children. When $k=2$ , it is a binary tree; when $k=3$ , it is a ternary tree.

Example

Here is an example of a rooted tree: $[asy] import binarytree; picture pic; binarytree bt=binarytree(1,2,3,4,5,nil,nil,6,nil,nil,7,8,nil,nil,nil,nil,9,10,11,nil,nil,12,nil,nil,13,14,nil,15); draw(pic,bt,condensed=false); label("node 1 is the root", (10,0), NE); add(pic.fit(),(0,0)); [/asy]$

In the graph above, it is a binary tree since each node has at most 2 children.

For example, node 3 is a child of node 2, node 6 is a child of node 4. Node 4 has 2 children: 5 and 6 and 1 parent: 3.

This article is a stub. Help us out by expanding it.

Page

Toolbox

Search

Tree (graph theory)

Rooted Tree

Example