Problem 1.(17 points) In performing search of a graph we get a tree where atree edge(u, v) indicates thatvhas not been visited when we examine this edge while we visitu. We have the following 3 types of non-tree edges: (a)back edge(u, v) is a non-tree edge such thatvis an ancestor ofuin the tree discovered when we visitu, (b)forward edge(u, v) is a non-tree edge such thatvis a descendant ofu discovered when we visitu, (c)cross edge(u, v) is a non-tree edge such that vis neither a descendant of nor an ancestor ofudiscovered when we visitu. (a) Show the DFS and BFS tree of the following directed graph starting from vertexv 1 showing clearly the tree edges and for non-tree edges mark them as one of the above 3 types (back,forward,cross).Assume that vertices in the ad- jaceny list of a vertex are stored in increasing order of its indices.(11 points)

(b) What types of non-tree edges are possible when we perform a DFS of an undirected graph? Justify your answer.(3 pts) (c) What types of non-tree edges are possible when we perform a BFS of an undirected graph? Justify your answer.(3 pts)

Problem 2.(15 points) (a) Prove that in a BFS search of an undirected graph, if (u, v) is a non-tree edge, eitheruandvmust be at the same level or at adjacent levels of the BFS tree. (8 points) (b) Using the above fact, devise anO(n+m)-time Algorithm to find a cycle of odd length if it exists in a connected undirected graphG= (V, E) wherenis the number of vertices andmis the number of edges. (7 points)

Problem 3.(10 points) LetG= (V, E) be an undirected graph where each vertexvV is labeled with a unique integer from 1to nwheren=|V|. For a vertexv, let min(v) be the minimum label of a vertex reachable by a path fromv. Give anO(n+m) -time algorithm to compute min(v) for allvV wherem=|E|.

Problem 4.(8 points) Problem R-6.10 of the text book.