Homework Exercise 5

Due: by 6pm on Tue 11 Nov
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

  1. Find a cut with minimum capacity in the network N = (V,E) with vertex set V = {s,a,b,c,d,e,f,t} and edge set described below. Justify that your cut's capacity is minimum, and show your work (i.e., show the steps you followed in order to determine the cut).

    edge capacity
    (s,a) 11
    (s,c) 16
    (s,d) 4
    (a,b) 18
    (a,d) 6
    (a,f) 3
    (b,e) 1
    (b,f) 8
    (c,b) 32
    (c,e) 2
    (d,f) 10
    (d,t) 1
    (e,c) 3
    (e,t) 2
    (f,b) 9
    (f,e) 12
    (f,t) 24

  2. Consider a flow network in which each vertex has a capacity, in addition to each edge, i.e., a network N = (V,E) with a single source s ∈ V, a single sink t ∈ V, edge capacities c(e) ≥ 0 for all e ∈ E and vertex capacities c(v) ≥ 0 for all v ∈ V (including s and t).

    For such a network, the capacity constraint is extended to include vertices: for each vertex v ∈ V, fin(v), fout(v) ≤ c(v), i.e., the total flow into or out of any vertex cannot exceed the capacity of that vertex.

    Explain how to determine a flow with maximum value in such a network, and justify that your algorithm works properly.