MathCastle
Graph TheorySuperchallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Superchallenge problem

A flow network has source ss, sink tt, and vertices a,b,c,d,ea,b,c,d,e with capacities c(s,a)=9c(s,a)=9, c(s,b)=7c(s,b)=7, c(a,c)=4c(a,c)=4, c(a,d)=3c(a,d)=3, c(b,d)=4c(b,d)=4, c(b,e)=6c(b,e)=6, c(c,d)=2c(c,d)=2, c(d,e)=3c(d,e)=3, c(c,t)=6c(c,t)=6, c(d,t)=2c(d,t)=2, c(e,t)=7c(e,t)=7 (maximum flow 1313, achieved exactly by the cut {s,a,b,d,e}\{s,a,b,d,e\}, whose three crossing arcs are a→ca\to c, d→td\to t, e→te\to t). If you could raise the capacity of exactly ONE of these three arcs without limit, which choice allows the largest possible new maximum flow, and what is that new maximum flow?