Furthermore, please note that the graders will grade 2 out of the 4 questions randomly. Therefore, if the grader decides to check questions 1 and 4, and you havenβt answered question 4, youβll lose points for question 4. Hence, please answer all the questions.
1. Consider an undirected graph G = (V,E) with nonnegative edge weights we β₯ 0. Suppose that you have computed a minimum spanning tree of G, and that you have also computed the shortest paths to all nodes from a particular node s β V . Now suppose, each edge weight is increased by 1: the new weights are [25]
β’ Does the minimum spanning tree change? Give an example where it changes or prove it cannot change.
β’ Do the shortest paths change? Give an example where they change or prove they cannot change.
2. Let G = (V,E) be an undirected graph. A node cover of G is a subset U of the vertex set V such that every edge in E is incident to at least one vertex in U. A minimum node cover is one with the fewest number of vertices. Consider the following greedy algorithm for this problem:
(a) Procedure COVER(V, E)
(b) U β Ο
(c) loop
(d) Let v β V be a vertex of maximum degree
(e) U β U βͺ{v};V β V β{v}
(f) E β E β{(u,w)} such that u = v or w = v
(g) until E = Ο go to (c)
(h) return (U)
(i) end COVER
Does this algorithm always generate a minimum node cover? If yes, provide some arguments as to why you think so. Else, then provide a counter example where this algorithm fails. [25]
3. For the network shown in Figure 1, compute the maximum flow from Vancouver to Winnipeg. Show all your work.
[25]
Figure 1: Network for Q3
4. Will the maximum flow from the source to the destination node in the Ford-Fulkerson Algorithm will be equal to the capacityof the minimum cut, if the capacity of a cut is defined in the following manner? For each definition, if you agree, then please provide arguments as to why. Else, provide a counter example to show that the definition does not hold:
(a) C(S : S) = Peβ(S:S ) C(e) + Peβ(S :S) C(e) [6]
[6] [6]
[7]
