Tree (graph theory)
A tree is an undirected graph which is both connected and acyclic. Equivalently, a tree is a graph such that for any two vertices with , there is exactly one path connecting and in . Every tree that has vertices has exactly edges.
The converse is also true: an undirected and connected graph with vertices and 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 .
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 parent; the parent is the other end of the edge going into the node, assuming the edges are going out from the root. Children 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 -ary tree is a tree in which all nodes have at most children. When , it is a binary tree; when , it is a ternary tree.
Example
Here is an example of a rooted tree:
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.