Reference no: EM131576749

Question: Use Exercise I to construct an algorithm for determining whether a directed graph contains a circuit.

Exercise I: Show that if G is a directed graph and T is a spanning tree constructed using depth-first search, then G contains a circuit if and only if G contains a back edge (see Exercise II) relative to the spanning tree T .

Exercise II; Show that if G is a directed graph and T is a spanning tree constructed using depth-first search, then every edge not in the spanning tree is a forward edge connecting an ancestor to a descendant, a back edge connecting a descendant to an ancestor, or a cross edge connecting a vertex to a vertex in a previously visited sub tree.