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 in between, with capacities c(s,a)=4c(s,a)=4, c(s,b)=6c(s,b)=6, c(a,b)=1c(a,b)=1, c(a,c)=3c(a,c)=3, c(a,d)=2c(a,d)=2, c(b,c)=2c(b,c)=2, c(b,d)=5c(b,d)=5, c(c,t)=4c(c,t)=4, c(d,t)=5c(d,t)=5. What is the maximum flow from ss to tt?