COMP 550 001 Fall 2017 Assignment 6 Part A due Monday November 20 2017 start of class This assignment does not contain a Part B You should submit a physical copy of your written homework at the start of class Optional Part C due Monday November 27 2017 start of class This assignment includes an optional Part C Earning half of the points will be worth half of a late day only integral late days may be used to turn in homework late but a partial late day can count as partial extra credit at the end of the semester and earning at least 80 of the points will be worth a full late day You should submit your code in a zip or tar gz le to Sakai and the analysis in a physical copy Part A Due Monday November 20 2017 Be sure to include a collaboration statement with your assignment even if you worked alone 10 points Problem 1 CLRS Exercise 22 3 11 Explain how a vertex u of a directed graph can end up in a depth rst tree containing only u even though u has both incoming and outgoing edges in G Assume that u does not have any self loops and that V 1 8 points Problem 2 CLRS Exercise 22 3 8 Give a counterexample to the conjecture that if a directed graph G contains a path from u to v and if u d v d in a depth rst search of G then v is a descendant of u in the depth rst forest produced 30 points Problem 3 subset of CLRS Problem 22 2 Let G V E be a connected undirected graph An articulation point of G is a vertex whose removal disconnects G For example articulation points are shown as the lled in vertices in the gure below 1 We can determine articulation points using depth rst search Let G V E be a depth rst tree of G a Prove that the root of G is an articulation point of G if and only if it has at least two children in G b Let v be a nonroot vertex of G Prove that v is an articulation point of G if and only if v has a child s such that there is no back edge from s or any descendant of s to a proper ancestor of v c Let cid 40 v low min v d w d u w is a back edge for some descendant u of v Show how to compute v low for all vertices v V in O E time d Show how to compute all articulation points in O E time 10 points Problem 4 CLRS Exercise 23 1 8 Let T be a minimum spanning tree of a graph G and let L be the sorted list of the edge weights in T Show that for any other minimum spanning tree T cid 48 of G the list L is also the sorted list of edge weights of T cid 48 10 points Problem 5 CLRS Exercise 24 1 1 a Run the Bellman Ford algorithm on the directed graph shown below using vertex z as the source In each pass relax edges in the same order as in the gure and show the d and values after each pass 2 b Now change the weight of edge z x to 4 and run the algorithm again using s as the source 10 points Problem 6 CLRS Exercise 24 3 5 Professor Newman thinks he has worked out a simpler proof of correctness for Dijkstra s algorithm He claims that Dijkstra s algorithm relaxes the edges of every shortest path in the graph in the order in which they appear on the path and therefore the path relaxation property applies to every vertex reachable from the source Show that the professor is mistaken by constructing a directed graph for which Dijkstra s algorithm could relax the edges of a shortest path out of order 12 points Problem 7 CLRS Exercise 29 1 2 Give three feasible solutions to the linear program given below What is the objective value of each one 10 points Problem 8 CLRS Exercise 29 1 5 Convert the following linear program into slack form maximize subject to 2x1 3x2 3x3 x1 x2 x3 7 x1 x2 x3 7 x1 2x2 2x3 4 0 x1 x2 x3 maximize subject to 6x3 2x1 x1 x2 x3 7 3x1 x2 8 x1 2x2 2x3 0 0 x1 x2 x3 What are the basic and nonbasic variables 3 tsxyz6785 27 3 429