图的次模性与割函数 我们首先明确图\(G=(V,E)\)上的割函数。对于任意顶点子集\(S \subseteq V\)，割函数\(c:2^V \rightarrow \mathbb{R}\)定义为： \[ c(S) = |\delta(S)| \] 其中\(\delta(S)\)表示一个端点在\(S\)内、另一个端点在补集\(V\setminus S\)内的所有边构成的集合，即边割集。 接下来介绍次模性。设\(f:2^V \rightarrow \mathbb{R}\)是定义在顶点集幂集上的集合函数。若对任意子集\(A, B \subseteq V\)，均满足： \[ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) \] 则称\(f\)是次模函数。 现在证明图的割函数具有次模性。考虑任意\(A, B \subseteq V\)，需验证： \[ c(A) + c(B) \geq c(A \cup B) + c(A \cap B) \] 通过分析边在割集中的贡献可完成证明：将边按端点所属区域（\(A \cap B\)、\(A \setminus B\)、\(B \setminus A\)、\(V \setminus (A \cup B)\)）分类，逐类讨论每条边在不等式左右两边的计数次数，可发现每条边在左侧的计数总不小于右侧，等号成立当且仅当边连接特定区域对时两侧计数相等。 次模性在图算法中有重要应用，例如最小割问题。利用次模函数的最小化算法（如最小割最大流算法）可高效求解全局最小割。进一步地，次模性还支撑了多端割等问题的近似算法设计。