MathCastle
Graph TheoryHardDirected Graphs and Network Flows

Directed Graphs and Network Flows · Hard problem

In a flow network with source ss, sink tt, and vertices a,b,ca,b,c in between, the capacities are c(s,a)=8c(s,a)=8, c(s,b)=8c(s,b)=8, c(a,b)=2c(a,b)=2, c(a,c)=3c(a,c)=3, c(a,t)=1c(a,t)=1, c(b,c)=1c(b,c)=1, c(b,t)=2c(b,t)=2, c(c,t)=10c(c,t)=10. Among the four cuts S1={s}S_1=\{s\}, S2={s,a}S_2=\{s,a\}, S3={s,a,b}S_3=\{s,a,b\}, S4={s,b}S_4=\{s,b\} (with TT everything else), what is the smallest of the four capacities?