Understanding the max-flow min-cut theorem
Now that we know what flow networks are and the maximum flow problem, we can explore the fundamental theorem and its solution. The max-flow min-cut theorem states that for any flow network, the maximum flow from the source to the sink is the minimum sum of weights of edges that, if removed, will completely disconnect the source and sink. Consider the flow network given below; we will use it as an example to prove the max-flow min-cut theorem.
Loading Image
A flow network with a source and sink where edge weight is the maximum capacity of the edge.
Before we dive deeper into this theorem, we need to know some terminologies used to to prove its correctness.
Liking the course? Check our discounted plans to continue learning.