MathCastle
Graph TheoryMediumDirected Graphs and Network Flows

Directed Graphs and Network Flows · Medium problem

In the network with capacities c(s,a)=7c(s,a)=7, c(s,b)=5c(s,b)=5, c(a,b)=3c(a,b)=3, c(a,c)=5c(a,c)=5, c(b,c)=2c(b,c)=2, c(b,t)=4c(b,t)=4, c(c,t)=7c(c,t)=7, compare the four cuts S={s,a}S=\{s,a\}, S={s,b}S=\{s,b\}, S={s,a,b}S=\{s,a,b\}, and S={s,a,c}S=\{s,a,c\} (each with T=V∖ST=V\setminus S). What is the smallest of their four capacities?