次模函数

次模函数（submodular function）是在有限集合的子集上取值、满足特定并交不等式的集合函数。其等价的边际解释是：在已有元素较多的集合上，加入同一个新元素所增加的值不会更大。这种递减关系描述重复覆盖、独立方向的冗余及割的结构，和函数值是否始终上升是两个不同条件。

考虑三台教学用传感器，覆盖的编号分别为 $C_a=\{1,2,3\}$、$C_b=\{3,4\}$、$C_c=\{2,4,5\}$。令 $f(S)$ 为选中传感器覆盖到的不同编号数。空选时加入 $b$ 增加二；已有 $a$ 时加入 $b$ 只增加编号四，增量为一。编号三已被覆盖，不应重复计数。

按列数已覆盖的不同对象；b 在 a 之外只提供一个新编号。

并交条件与边际条件等价

设 $E$ 为有限底集，$f:2^E\to ℝ$。若对任意 $A,B\subseteq E$， $$f(A)+f(B)\ge f(A\cup B)+f(A\cap B),$$ 则称 $f$ 次模。定义 ${\Delta }_e(A)=f(A\cup \{e\})-f(A)$，其中 $e\notin A$。次模性等价于：对所有 $A\subseteq B\subseteq E$、$e\in E\setminus B$， $${\Delta }_e(A)\ge {\Delta }_e(B).$$ 注意比较的是同一个新元素，且两个背景集合必须有包含关系。

证明。 若已知并交条件，将它用于 $A\cup \{e\}$ 和 $B$；二者的交为 $A$、并为 $B\cup \{e\}$，移项即得到边际递减。

反之，给定任意 $X,Y$，将 $X\setminus Y$ 枚举为 $e_1,\dots ,e_k$。从 $X\cap Y$ 出发按此顺序加元素，最终得到 $X$；从 $Y$ 出发按同一顺序加元素，最终得到 $X\cup Y$。每一步前一背景包含于后一背景，且新元素尚未在任一背景中出现，所以逐步使用边际递减并相加，得 $$f(X)-f(X\cap Y)\ge f(X\cup Y)-f(Y).$$ 移项便是并交条件。即使 $k=0$，两边差分都是零，结论仍成立。

覆盖与割的两种行为

对覆盖函数，${\Delta }_e(A)$ 正是 $C_e\setminus \bigcup _{i\in A}{C}_i$ 的大小。随着 $A$ 增大，已覆盖集合增大，这个差集只能缩小，所以覆盖函数次模，同时也是单调非减且 $f(\varnothing )=0$ 的。

开头取 $X=\{a,b\}$、$Y=\{b,c\}$。前者覆盖 $\{1,2,3,4\}$，后者覆盖 $\{2,3,4,5\}$，均为四；并集覆盖五，交集 $\{b\}$ 覆盖二，因此 $4+4\ge 5+2$。严格的一单位来自两组选择都覆盖了编号二，却不是通过共同选择的传感器 $b$ 覆盖它。

另一例是无向非负加权图的割函数 $g(S)=\sum _{uv:u\in S,v\notin S}{w}_{uv}$。对 $v\notin S$， $${\Delta }_v(S)=\sum _{u\notin S\cup \{v\}}{w}_{uv}-\sum _{u\in S}{w}_{uv}.$$ 一个其他顶点从外部移入 $S$ 时，其边权从正号变成负号，边际只会减小，故割函数次模。但它一般不单调：只有一条权一边 $uv$ 时，$g(\{u\})=1$ 而 $g(\{u,v\})=0$。由此，边际递减不等于边际非负。

变式。 在传感器例中，已有 $\{a,c\}$ 后再加 $b$，增量多少？$a,c$ 已覆盖全部五个编号，答案为零。若删去 $c$，只比较空集、$\{a\}$ 这两个背景，加 $b$ 的增量分别为二和一，仍满足递减关系。

与其他集合函数的边界

若并交式始终取等号，函数称为模函数，可写为 $f(S)=c+\sum _{e\in S}{w}_e$。权重可正可负，所以模函数也不必单调。把所有不等号反向得到超模函数，其边际递增。非负倍数之和保留次模性；任意乘积则没有这样的保证，例如两个单元素指示函数相乘，会奖励“两个都选”，产生超模的互补效应。

拟阵的秩函数是特殊的整数值、归一化、单调次模函数；多拟阵把更一般的此类容量转为连续可行域。次模性本身没有承诺任意受约束优化都能被贪心精确求解：它描述函数结构，具体优化结论还须列明约束、单调性和目标方向。