割函数是子模函数

标签：cut end 函数 cup cap overline 子模 aligned

然而 Ishy 并不会证这个标题。但是 Ishy 会证那个最具标志性的不等式。

---

记 \(\mathrm{cut}(A)\) 表示点集 \(A\) 与其在流网络上的补集的切割值，\(\mathrm{cut}(A, B)\) 表示点集 \(A\) 向 \(B\) 的广义切割值（即起点在 \(A\)、终点在 \(B\) 的边权和）。

记 \(A / B\) 表示 \(A\) 中去除掉包含于 \(B\) 中的元素后剩下的集合。

则有结论：

\[\begin{aligned} \newcommand\cut[1]{\mathrm{cut}#1} \colorbox{yellow}{$\cut(A \cup B) + \cut(A \cap B) \le \cut(A) + \cut(B)$} \\ \end{aligned} \]

证明：建议画个韦恩图出来，能够更加直观地理解推导过程。

\(\cut(A \cup B)\)：

\[\begin{aligned} \cut(A \cup B) &= \cut(A \cup B, \overline{A \cup B}) \\ &= \cut(\overline{A \cup B}, A / B + B / A) + \cut(\overline{A \cup B}, A \cap B) \\ \end{aligned} \]

\(\cut(A \cap B)\)：

\[\begin{aligned} \cut(A \cap B) &= \cut(A \cap B, A / B + B / A) + \cut(A \cap B, \overline{A \cup B}) \\ \end{aligned} \]

简化左式（以凑出一些项具有完整的 \(A , B\)）：

\[\begin{aligned} LHS &= \cut(\overline{A \cup B}, A / B + B / A)+ \cut(\overline{A \cup B}, A \cap B) + \cut(A \cap B, A / B + B / A) + \cut(A \cap B, \overline{A \cup B}) \\ &= \cut(A \cap B, A / B + B / A) + \left( \cut(\overline{A \cup B}, A / B) + \cut(\overline{A \cup B}, A \cap B) \right) + \left( \cut(\overline{A \cup B}, B / A) + \cut(\overline{A \cup B}, A \cap B) \right) \\ &= \cut(A \cap B, A / B) + \cut(A \cap B, B / A) + \cut(\overline{A \cup B}, A) + \cut(\overline{A \cup B}, B) \\ \end{aligned} \]

展开右式（以贴合左式的形式）：

\[\begin{aligned} RHS &= \cut(A, B / A + \overline{A \cup B}) + \cut(B, A / B + \overline{A \cup B}) \\ &= \cut(B, A / B) + \cut(A, B / A) + \cut(\overline{A \cup B}, A) + \cut(\overline{A \cup B}, B) \\ \end{aligned} \]

由于 \(\cut(B, A / B) \ge \cut(A \cap B, A / B)\)，\(\cut(A, B / A) \ge \cut(A \cap B, B / A)\)，所以 \(LHS \le RHS\)。得证。

标签：cut,end,函数,cup,cap,overline,子模,aligned
From： https://www.cnblogs.com/Schucking-Sattin/p/17966544