Assignment 6 (85 points)CS 610 Spring 2019Due : Apr.24,2019 in classProblem 1. (7 points)How will you modify the DFS biconnectivity algorithm discussed in class sothat we can output edges of each biconnected component ?Hint: Keep both tree and back edges on stack and think about when to popthem from stack as part of a biconnected component.Problem 2. (15 points)Apply the biconnectivity algorithm discussed in class to the undirected graphshown in Figure 6.8 of the text book to identify the separation vertices. Yoursearch should start from vertex A. Assume the adjacent list of each vertexcontains vertices in alphabetical order. For example for vertex M, the adjacencylist has vertices A, B and C in that order. You need to show the DFS treeshowing both tree and back edges and also DF, LOW values for each vertex.Problem 3. (10 points)For the following weighted graph, produce minimimum cost spanning tree(MST) using Prim-Jarn`?k’s algorithm showing all intermediate steps. Youralgorithm should start from vertex a.1Problem 4. (10 points)Repeat the above problem except that you need to use Kruskal’s algorithm forMST.2Problem 5. (10 points)(a) Show how to modify Dijkstra’s algorithm to not only output the distancefrom a vertex s to each vertex in G but also to output a spanning treeT rooted at s such that the path in T from s to a vertex u is aCS 610留学生作业代做、代写DFS algorithm作业、代做Java，Python实验作业、代写c++程序作业 ctually ashortest path in G from v to u. Your output of the tree should be something like ”v1 has shortest distance d and v2 is parent of v1 ”. (5 points)(b) Do additional modification so that if there are more than one shortest pathfrom s to u, we output the one with shortest number of edges.(5 points)Problem 6. (18 points)Let G = (V, E) be a directed graph where each edge has a probability valueassociated with it given by the function p : E? > [0, 1]. Assume there are noself-cycles in this graph. The reliability of a directed path P = (e1, e2, ...ek)from vertex u to vertex v given by R(P) = Qki=1 p(ei) is the product of probabilitiesof edges in the path. All-pairs Max Reliablity Problem is one of findingfor each pair of vertices u and v, the maximum reliability among all paths fromu to v.(a) Define a proper closed semi-ring for this all-pairs problem and prove it is aclosed semi-ring.(7 pts)(b) Modify Warshall-Floyd algorithm to solve this problem using proper semiringoperations.Your algorithm should also find for each pair of vertices theactual path that achieves maximum reliability.(8 pts)(c) Estimate the time complexity of this algorithm specifying exactly the primitiveoperations being measured.(3 pts)Problem 7. (15 points) Problem R-8.4 from the text book. Show all thedifferent steps of the algorithm and also the miniumum cut.3转自：http://www.7daixie.com/2019042536755957.html
网友评论