1. (15pts) Let G=(V, E) be a digraph. Run the algorithm DFS(G) following the coloring and node-priority convention given in class. We found that the four edge classes have the following properties:

A tree edge runs from a node of a smaller DFS number to that of a larger DFS number. The latter node is blue when the edge is first colored.

A back edge runs from a node of a larger DFS number to that of a smaller DFS number. The latter node is blue when the edge is first colored.

A forward edge runs from a node of a smaller DFS number to that of a larger DFS number. The latter node is red when the edge is first colored.

A cross edge runs from a node of a larger DFS number to that of a smaller DFS number. The latter node is red when the edge is first colored.

By running DFS(G), we obtain a DFS forest consisting of the tree edges. Let v be any node in V. An ancestor of v is a node z such that there is a non-empty path from z to v consisting of only tree edges. (So z is the parent of v, or grand parent, or great grand parent in a DFS tree.) If z is an ancestor of v, we say v is a descendant of z. Denote by dfs(v) the DFS number assigned to v.

Fill in the blanks to complete the description.

We have observations:

For any forward edge (v, w), v is ____(a)____ of w.

(Because when the edge is fist colored, the only red nodes with DFS numbers ____(b)___ than dfs(v) exist in the subtree rooted at v)

For any cross edge (v, w), v is _____(c)_____ of w.

For any back edge (v, w), v is _____(d)_____ of w.

The statements (II) and (III) are justified similarly to (I).

We also see:

If there exists a path from v to w such that dfs(w)>dfs(v), the path includes ____(e)____ of w.

To prove (IV), let (v, w) be the last edge to decrease the dfs number in the path, i.e., dfs(v)>dfs(w). If theres no such e, set w=v. There exists such w because dfs(w)>dfs(v). Every edge in the path from w to w _____(f)____ the DFS number so it must be a ______(g)_____ edge. By the above, w must be ____(h)____ of w. The node w is our proof of (IV).

Fill-in Choices: (1) an ancestor, (2) a descendant, (3) either an ancestor or descendant,

(4) neither an ancestor nor descendant, (5) both an ancestor and descendant,

(6) smaller, (7) larger, (8) increases, (9) decreases,

(10) tree, (11) back, (12) forward, (13) cross, (14) tree or back,

(15) tree or forward, (16) tree or cross, (17) cross or forward, (18) None of the above.