Lesson 4

Theorem. Let \((L,R)\) be a minimum cut in \(G'\). Then \((L \setminus \{s\}, R \setminus \{t\})\) is an optimal segmentation.

Proof. Let \(F=L \setminus \{s\}\), \(B=R \setminus \{t\}\). The cut \((L,R)\) includes three types of edges:

• \((i,j)\) where \(i \in F\), \(j \in B\);


• \((s,i)\) where \(i \in B\),


• \((i,t)\) where \(i \in F\).

Then, \[\begin{align*}\operatorname{capacity}(L,R)&=\sum_{i \in B}f_{i}+\sum_{i \in F}b_{i}+\sum_{\substack{\{i,j\} \in E\\|B \cap \{i,j\}|=1}}p_{ij}=\\&=\left(\sum_{i}(f_{i}+b_{i})-\sum_{i \in F}f_{i}-\sum_{i \in B}b_{i}\right)+\sum_{\substack{\{i,j\} \in E\\|B \cap \{i,j\}|=1}}p_{ij}=\\&=\sum_{i}(f_{i}+b_{i})-q(F,B) \ .\end{align*}\] Thus, by minimizing the cut, we maximize the value \(q(F,B)\).◼