2023年11月25日

算法代写｜Module Title: Graph Algorithms and Complexity Theory

本次英国作业是图算法与复杂性理论的一个算法代写限时测试

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?

  • • c1 : E ! N with c1(x;y) = 1 + c(x;y) for all (x;y) 2 E
    • c2 : E ! N with c2(x;y) = 2 · c(x;y) for all (x;y) 2 E
    • c3 : E ! N with c3(x;y) = (c(x;y))3 for all (x;y) 2 E

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?

  • • f1 : E ! N with f1(x;y) = 1 + f (x;y) for all (x;y) 2 E
    • f2 : E ! N with f2(x;y) = 2 · f (x;y) for all (x;y) 2 E
    • f3 : E ! N with f3(x;y) = (f (x;y))3 for all (x;y) 2 E

(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.