MathCastle
Graph TheoryChallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Challenge problem

A flow network has source ss, sink tt, and vertices a,b,c,d,ea,b,c,d,e in between, with capacities c(s,a)=9c(s,a)=9, c(s,b)=7c(s,b)=7, c(a,c)=4c(a,c)=4, c(a,d)=3c(a,d)=3, c(b,d)=4c(b,d)=4, c(b,e)=6c(b,e)=6, c(c,d)=2c(c,d)=2, c(d,e)=3c(d,e)=3, c(c,t)=6c(c,t)=6, c(d,t)=2c(d,t)=2, c(e,t)=7c(e,t)=7. What is the maximum flow from ss to tt?