MathCastle
Graph TheoryChallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Challenge 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 (its maximum flow is 1313, limited by the cut {s,a,b,d,e}\{s,a,b,d,e\}). If the capacity of d→td\to t alone is increased from 22 to 77, what is the new maximum flow?