3.2. Verifying a Solution#
How big can the optimal flow value be? Partition the vertices \(V\) into a set \(S\) containing the source \(s\) and a set \(T\) containing the sink \(t\). (The sets \(S\) and \(T\) form a partition of \(V\) if each node in \(V\) is in exactly one of \(S\) and \(T\).) We shall call such a partition \((S,T)\) a cut; note that the definition of a cut requires that \(s \in S\) and \(t \in T\). Observe that every unit of flow that goes from node \(s\) to node \(t\) must at some point pass along an edge \((v,w) \in A\) where \(v \in S\) and \(w \in T\). However, there are only so many arcs of this form, and each such arc \((v,w)\) has an upper bound \(u(v,w)\) on the total flow that can use it. If we let \(D(S,T)\) denote the set of arcs \((v,w)\) for which \(v \in S\) and \(w \in T\), then the capacity of the cut \((S,T)\) is equal to
Since each unit of flow from \(s\) to \(t\) “uses up” one unit of the capacity of the cut \((S,T)\), the value of the maximum flow is at most the capacity of the cut. This claim is true for any cut \((S,T)\). For the same input, some cuts may have large capacity, and some cuts may have small capacity. However, for each cut, its capacity places a limit on the value of the maximum flow. Hence, if we found a cut of minimum capacity, this would give us the best information about how big the maximum flow value might be.
Even more importantly, there is the following verification property that is built into the notion of a feasible flow and a cut:
If \(f^*\) is a feasible flow and \((S,T)\) is a cut such that the value of \(f^*\) is equal to the capacity of \((S,T)\), then \(f^*\) is a maximum flow.
Why is this? Let \(\mu\) denote the value of the feasible flow \(f^*\) (and hence \(\mu\) is also the capacity of the cut \((S,T)\)). Suppose there was another feasible flow \(\bar f\) of value greater than \(\mu\); say that its value is \(\bar\mu\). But we know that the value of \(\bar f\) is at most the capacity of the cut \((S,T)\), which is \(\mu\). This is a contradiction: \( \bar \mu\) cannot both be bigger than \(\mu\) and at most \(\mu\). Hence, there cannot exist such a feasible flow, and \(f^*\) is a maximum flow.