What is the intuition behind the max-flow min-cut theorem?
I know that the min-cut is the dual of max-flow when formulated as a linear program, but the result seems artificial to me.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
So you have a flow thought the network. If you want the maximal flow, your network should not have any bottlenecks. And if you partition the network in two parts, where the source and the sink are in different partitions - you won't be able to push more though the network than this cut - i.e. the sum of edges.
Now the minimum cut will be the worst bottleneck in the network. So it will correspond to maxflow.