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.

Before we dive deeper into this theorem, we need to know some terminologies used to prove its correctness.

Residual graph

In a flow network with some flow f from the source to the sink node, the capacity of all edges with flow is reduced. The remaining capacity of such edges is called their residual capacity. A graph representing the flow network with the residual capacity of its edges is called a residual graph.

A residual graph also has reverse edges between nodes with some flow in them, and the residual capacity of these reverse edges is the total flow in the forward edge. We will learn later why these reverse edges are so crucial when we learn how to find the maximum flow in a flow network.

Augmenting path