View source for Tree (graph theory)

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

The converse is also true: an undirected and connected graph with <math>n</math> vertices and <math>n-1</math> 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 <math>|V|-|E|</math>.

===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 <math>1</math> ''parent''; the parent is the other end of the edge going into the node, assuming the edges are going out from the root. ''Child''s 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 '''<math>\boldsymbol{k}</math>-ary tree''' is a tree in which all nodes have at most <math>k</math> children. When <math>k=2</math>, it is a binary tree; when <math>k=3</math>, it is a ternary tree.

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", (0,0), NE);

add(pic.fit(),(0,1),10N);
</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. 

{{stub}}