xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

Assignment代写 - Algorithm Assignment 5

时间：2019-10-20

```
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.