カット

証明 任意の実現可能なフロー \(f\) とカット \((S, T)\) を取ると、次の不等式が成り立つ: \[ \begin{aligned} |f| & = \partial f (s) & [\text{定義}] \\ & = \sum_{v \in S} \partial f(v) & [\text{保存条件}] \\ & = \sum_{v \in S}\sum_{w} f(v \rightarrow w) - \sum_{v \in S} \sum_{u} f(u \rightarrow v) & [\partial \text{ の定義}] \\ & = \sum_{v \in S}\sum_{w \notin S} f(v \rightarrow w) - \sum_{v \in S} \sum_{u \notin S} f(u \rightarrow v) & [S \text{ から } S \text{ への辺を削除}] \\ & = \sum_{v \in S}\sum_{w \in T} f(v \rightarrow w) - \sum_{v \in S} \sum_{u \in T} f(u \rightarrow v) & [\text{カットの定義}] \\ & {\color{red}\leq} \sum_{v \in S}\sum_{w \in T} f(v \rightarrow w) & [f(u \rightarrow v) \geq 0] \\ & {\color{red}\leq} \sum_{v \in S}\sum_{w \in T} c(v \rightarrow w) & [f(u \rightarrow v) \leq c(v \rightarrow w)] \\ & = \|S, T \| & [\text{定義}] \end{aligned} \]

二つ目のステップでは、全ての頂点 \(v \in S \backslash \lbrace s \rbrace\) において \(\partial f(v) = 0\) なことからゼロを足しているだけである。また四つ目のステップでは全ての \(x, y \in S\) に対するフローの値 \(f(x \rightarrow y)\) を削除しているが、これが可能なのはこの値が二つの和の両方で出現するためである。つまり、\(v = x\) と \(w = y\) のときに一度、\(v = y\) と \(u = x\) のときに一度出現する。

式変形中の最初の不等号は \(f\) が \(T\) から \(S\) への辺を全て避けるときに限って等号となる。同様に二つ目の不等号は \(f\) が \(T\) から \(S\) への辺を全て飽和させるときに限って等号となる。 \(\Box\)