Lesson 2

In the general case, we define an \((s,t)\)-cut as a partition of all vertices into two disjoint groups \(L\) and \(R\), containing \(s\) and \(t\) respectively. The flow through the cut is defined as \[f(L,R)=\sum_{u \in L, v \in R}f(u,v)-\sum_{u \in R, v \in L}f(u,v) \ .\] It is easy to see that the flow through any cut equals the flow value \(f\).

The capacity of a cut is the total capacity of edges from \(L\) to \(R\): \[\operatorname{capacity}(L,R)=\sum_{u \in L, v \in R}c(u,v) \ .\] The following obvious observation is key:

For any flow \(f\) and any \((s,t)\)-cut \((L,R)\) the flow value does not exceed the cut capacity: \[\operatorname{size}(f) \le \operatorname{capacity}(L,R).\]

Thus, any cut gives an upper bound on flows. Some cuts have large capacities, and therefore give very rough bounds. For instance, the cut \((\{s,b,c\}, \{a,d,e,t\})\) has capacity \(19\). But we managed to exhibit a cut with capacity \(7\), exactly equal to the flow constructed, and thus proved its optimality. It turns out such a cut exists always!