图的次模性与割函数 我们首先从集合函数的基本概念开始。设V是一个有限集合，一个函数f: 2^V → R（从V的所有子集到实数的映射）称为一个集合函数。在组合优化中，我们特别关注一类具有特殊性质的集合函数，称为次模函数。 次模性描述的是一种"收益递减"的性质。形式化地说，一个集合函数f是次模的，如果对于V的任意两个子集A和B，都满足以下不等式： f(A) + f(B) ≥ f(A∪B) + f(A∩B) 这个不等式的直观意义是：当我们向两个集合的并集和交集中添加元素时，函数值的总增益不会超过分别向两个集合中添加元素时的增益之和。 现在，让我们考虑图G=(V,E)上的一个特殊函数——割函数。对于任意顶点子集S⊆V，我们定义割函数cut(S)为连接S和V\S之间的边的数量。换句话说，cut(S)是图G中横跨集合S和其补集V\S的边的条数。 割函数具有一个非常重要的数学性质：它是一个对称的次模函数。我们来验证这一点： 首先，对称性：cut(S) = cut(V\S)，这是显然的，因为横跨S和V\S的边与横跨V\S和S的边是同一组边。 其次，次模性：对于任意两个顶点子集A和B，考虑横跨A∪B和A∩B的边。通过仔细分析边的分布，我们可以证明cut(A) + cut(B)确实大于等于cut(A∪B) + cut(A∩B)。这个性质的组合证明涉及到对连接四个区域（A∩B, A\B, B\A, 和V\(A∪B)）的边进行系统性的计数。 割函数的次模性在图论和组合优化中有着深远的影响。它保证了基于割函数的一系列优化问题（如最小割问题）具有良好的数学性质，使得我们可以设计出高效的算法来解决这些问题。次模性也是理解许多图分割算法和网络可靠性分析的理论基础。