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,ca,b,c with capacities c(s,a)=6c(s,a)=6, c(s,b)=5c(s,b)=5, c(a,c)=4c(a,c)=4, c(a,t)=2c(a,t)=2, c(b,c)=3c(b,c)=3, c(b,t)=4c(b,t)=4, c(c,t)=6c(c,t)=6. A flow currently sends f(s,a)=3f(s,a)=3, f(a,c)=3f(a,c)=3, f(c,t)=3f(c,t)=3, f(s,b)=4f(s,b)=4, f(b,t)=4f(b,t)=4 (every other arc carries 00) – a valid flow of value 77. By how much can the total flow still be increased by rerouting along augmenting paths?