MathCastle
Graph TheoryHardDirected Graphs and Network Flows

Directed Graphs and Network Flows · Hard problem

A network has capacities c(s,a)=4c(s,a)=4, c(s,b)=2c(s,b)=2, c(a,b)=3c(a,b)=3, c(a,t)=1c(a,t)=1, c(b,t)=5c(b,t)=5, starting with zero flow. Push the augmenting path s→a→b→ts\to a\to b\to t as far as it goes. What is then the residual capacity of the backward arc b→ab\to a?