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,c,da,b,c,d, with capacities c(s,a)=6c(s,a)=6, c(s,b)=4c(s,b)=4, c(a,c)=5c(a,c)=5, c(b,c)=2c(b,c)=2, c(b,d)=3c(b,d)=3, c(c,t)=4c(c,t)=4, c(d,t)=5c(d,t)=5, c(a,d)=1c(a,d)=1. What is the minimum possible capacity of an ss-tt cut in this network?