MathCastle
Graph TheoryHardDirected Graphs and Network Flows

Directed Graphs and Network Flows · Hard problem

A flow network has source ss, sink tt, and vertices a,b,ca,b,c, with capacities c(s,a)=7c(s,a)=7, c(s,b)=2c(s,b)=2, c(a,b)=3c(a,b)=3, c(a,c)=4c(a,c)=4, c(b,c)=2c(b,c)=2, c(b,t)=3c(b,t)=3, c(c,t)=6c(c,t)=6. A flow sends f(s,a)=7f(s,a)=7, f(s,b)=2f(s,b)=2, f(a,b)=3f(a,b)=3, f(b,c)=2f(b,c)=2, f(b,t)=3f(b,t)=3, with f(a,c)f(a,c) fixed by conservation at aa and f(c,t)f(c,t) fixed by conservation at cc. Is this flow already maximum, and if so, what is the maximum flow value?