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]
