MathCastle
Graph TheoryHardDirected Graphs and Network Flows

Directed Graphs and Network Flows · Hard problem

In the same kind of network — capacities c(s,a)=5c(s,a)=5, c(s,b)=3c(s,b)=3, c(a,b)=2c(a,b)=2, c(a,t)=4c(a,t)=4, c(b,t)=6c(b,t)=6, flow f(s,a)=5f(s,a)=5, f(s,b)=1f(s,b)=1, f(a,b)=2f(a,b)=2, f(a,t)=3f(a,t)=3, f(b,t)=3f(b,t)=3 — how many arcs are saturated (flow equal to capacity)?