## Description

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]

## Reviews

There are no reviews yet.