Question 1
This is a question on maximum flows in networks.
(a) MCQ Given a network (G;s;t), where G = (V ;E), with capacity function c : E ! N, a flow f : E ! N
and a cut (A;B) of (G;s;t).
• Is there always a capacity function cmax : E ! N such that f becomes a maximum flow w.r.t.
cmax?
(b) MCQ Let (A;B) be a minimum cut of a network (G;s;t) with capacity function c : E ! N. Let k be the
number of edges across the cut (A;B).
• Will every execution of the Ford-Fulkerson method require at least k augmenting paths?
• Can we always find a maximum flow by the Ford-Fulkerson method that uses at most k aug
menting paths?• Is there always a capacity function cmin : E ! N such that (A;B) becomes a minimum cut of
(G;s;t)?
(c) MCQ Let (G;s;t) be a network, where G = (V ;E), with capacity function c : E ! N. Will its minimum
cuts be preserved if we replace c by one of the ci for i = 1;2;3 below?
Let f : E ! N be a maximum flow in the network (G;s;t) with capacities c. For i = 1;2;3, will the fi
defined below be a flow in the network (G;s;t) with capacity function ci as above?
(d) In the network below capacities are indicated by numbers next to the edges. Compute, starting from
the all-zero flow, a maximum flow in this network, state its value, and find a minimum cut, the edges
across this cut, and state the cut’s capacity. Show your work.