1.6 Acyclic Graph

A directed graph with no cycles is called directed acyclic graph or a DAG for short. An acyclic digraph has at least one vertex with an out-degree of zero.

Figure 4 shows a variant of the directed graph of Figure 1 that contains no cycles. You will observe that vertex 4 has an out-degree of zero.

Figure 4: Example of an Acyclic Digraph

A directed tree is a connected DAG with the following properties:

  • There is one vertex, called the root, which no edges enter.

  • All vertices except the root have one entering edge.

  • There is a unique path from each vertex to the root.

A DAG consisting of one or more trees is called a forest. If the graph F=V,EF=(V,E) is a forest and the edge v,w(v,w) is in EFE(F), vertex vv is the parent of ww and vertex ww is the child of vv. If there is a path from vv to ww, then vertex vv is an ancestor of ww and vertex ww is a descendent of vv. A vertex with no proper descendants is a leaf. A vertex vv and its descendants form a subtree of FF. The vertex vv is the root of this subtree. The depth of vertex vv is the length of the path from the root to vv. The height of vertex vv is the length of the longest path from vv to a leaf. The height of a tree is the height of its root. The level of vertex vv is its depth subtracted from the height of the tree.

Figure 5 depicts a directed tree. Its root is vertex 1. Its leaves are the set of vertices LG=3,4,6,8,9L(G)=\{ 3,4,6,8,9\}.

Figure 5: Example of a Directed Tree

An undirected, connected, acyclic graph is called a free tree or an undirected tree. A rooted free tree is a free tree in which one vertex has been designated as the root. A directed tree is converted into a rooted free tree by discarding the orientation of the edges. A rooted free tree is converted into a directed tree by orienting each edge away from the root. The terminology which applies to directed trees also applies to rooted free trees.

Figure 6 depicts the directed tree of Figure 5 converted into a rooted free tree.

Figure 6: Example of a Rooted Free Tree