Rado–Edmonds

matroid：贪心最优的充要条件

交换论证是逐题写的：换一道题，选取规则变了，「换成贪心的选择不会变差」那一步就得重证。反复写上几遍会看出这些证明共享同一个骨架，于是自然要问：能不能一次性刻画出「贪心可行」的那一类问题。答案是可以，而且是充要的——条件落在问题的可行解结构上，与权重无关。

本页的全部内容围绕一个抽象对象：一个有限集，加上一族被称为「独立」的子集。区间调度、生成树、匹配、按期完工的作业集，都能写成这个形状；能不能贪心，只取决于这一族子集满不满足一条公理。

1 · 独立系统与遗传性

**定义 1.1（independence system）**设 $E$ 是有限集， $\mathcal{I}$ 是 $E$ 的一族子集。若 $\emptyset \in \mathcal{I}$ ，且 $B \in \mathcal{I}$ 、 $A \subseteq B$ 蕴含 $A \in \mathcal{I}$ ，则称 $(E, \mathcal{I})$ 为独立系统， $\mathcal{I}$ 中的成员称为独立集。

第二条即遗传性：独立集的任何子集仍独立。它几乎是免费的：绝大多数组合优化问题的可行解天然满足它，因为可行性通常是「不许出现某种冲突」，去掉元素不会凭空造出冲突。本页用到的五个系统都满足遗传性：

系统	ground set	独立的含义
graphic	图的边	边集无环
uniform	任意 5 个元素	元素个数不超过 2
scheduling	单位耗时的作业	存在一个排产使全部按期完工
matching	图的边	边集两两不共端点
interval	一组区间	区间两两不交

遗传性对贪心毫无帮助。它只保证「已经收下的部分永远合法」，不保证收下的这一步不会堵死后面的路。区分五个系统的是另一条公理。

2 · 交换性质

**定义 2.1（matroid）**独立系统 $(E, \mathcal{I})$ 若还满足：对任意 $A, B \in \mathcal{I}$ 且 $|A| < |B|$ ，存在 $x \in B \setminus A$ 使 $A \cup \lbrace x \rbrace \in \mathcal{I}$ ，则称之为 matroid。这一条称为交换性质。

交换性质有一个便于检验的等价形式：对任意 $S \subseteq E$ ， $S$ 的所有极大独立子集大小相同。两者的等价是标准结论。若两个极大独立子集 $A, B \subseteq S$ 满足 $|A| < |B|$ ，交换性质给出可加进 $A$ 的 $x \in B \setminus A \subseteq S$ ，与 $A$ 在 $S$ 中极大矛盾；反方向同样直接。

本页的检验走的是后一种形式。理由不只是省事：等价形式找到的那个 $S$ 直接就是反例权函数的支撑集，而直接枚举 $(A, B)$ 对得到的见证还要再折算一次才能变成让贪心出错的输入。

图 2-1 · 逐个子集检验交换性质：列出该子集的全部极大独立子集并比较大小。可切换系统，看扫描停在哪一个子集上。

扫描按子集大小递增进行。三个 matroid 把全部 26 个候选子集走完而不停；matching 与 interval 两个系统各在一个三元素子集上停下，那正是它们最小的见证。

3 · Rado–Edmonds 定理

考虑最简单的贪心：把 $E$ 按权重降序排队，逐个测试，能保持独立就收下。这个算法只与独立性打交道，不知道问题的任何其它结构。

**定理 3.1（Rado–Edmonds）**独立系统 $(E, \mathcal{I})$ 是 matroid，当且仅当对一切非负权函数 $w$ ，上述贪心都给出最大权独立集。

证明必要性用反证。设某个 $S \subseteq E$ 有两个极大独立子集 $A$ 、 $B$ ， $|A| = p < q = |B|$ 。取 $\varepsilon$ 满足 $0 < \varepsilon < q / p - 1$ ，令 $A$ 中元素权重为 $1 + \varepsilon$ ， $S \setminus A$ 中元素权重为 $1$ ，其余为 $0$ 。贪心先收下 $A$ 的全部 $p$ 个元素，此后 $S$ 里再无可加者（ $A$ 在 $S$ 中极大），得到的权重是 $p(1 + \varepsilon) < q$ ，而 $B$ 的权重是 $q$ 。贪心不最优。

充分性设 $(E, \mathcal{I})$ 是 matroid，贪心的输出为 $g_1, \dots, g_k$ （权重递减），任取独立集 $B = b_1, \dots, b_m$ （权重递减）。先证 $k \ge m$ ： $g_1, \dots, g_k$ 在 $E$ 中极大，若 $k < m$ ，交换性质给出可加进它的元素，与极大矛盾。再证 $w(g_i) \ge w(b_i)$ 对一切 $i \le m$ 成立：若不然，取最小的 $i$ 使 $w(g_i) < w(b_i)$ ，则 $A = \lbrace g_1, \dots, g_{i-1} \rbrace$ 与 $B_i = \lbrace b_1, \dots, b_i \rbrace$ 都独立且 $|A| < |B_i|$ ，交换性质给出 $x \in B_i \setminus A$ 使 $A \cup \lbrace x \rbrace$ 独立；而 $w(x) \ge w(b_i) > w(g_i)$ ，说明贪心在轮到 $g_i$ 之前就该收下 $x$ ，矛盾。逐项相加得 $w(B) \le \sum_{i \le m} w(g_i) \le w(G)$ 。∎

图 3-1 · 权重降序贪心与暴力枚举的最大权独立集对照。可切换系统与权重取反，观察差值在哪几个系统上不为零。

必要性那一半的构造在页面上能直接对上。matching 系统的三条边权重取 2、3、2，正是构造里 $p = 1$ 、 $q = 2$ 、 $\varepsilon = 1/2$ 再整体乘 2 的结果：贪心先收下中间那条权重 3 的边，两端的边随即都加不进来，拿到 3；而两端的边合起来是 4。

**警示 ·**定理的前提是权重非负，页面的实现没有替它兜底。 $U_{2,5}$ 上把五个权重全取成负数，贪心仍会收下最不亏的两个、拿到负的总权重，而最大权独立集是空集、权重为 $0$ 。这一处差异与 matroid 无关，纯粹是「贪心不检查正负」。教科书叙述通常把非负条件写在定理里，实现里则很容易漏掉。

4 · graphic matroid 与 Kruskal

给定无向图 $G = (V, E)$ ，令 $\mathcal{I}$ 为全部无环边集，得到的独立系统称为 graphic matroid。它满足交换性质：若无环边集 $A$ 比 $B$ 小， $A$ 在图上划出的连通分量比 $B$ 多， $B$ 中必有一条边的两端落在 $A$ 的两个不同分量里，把它加进 $A$ 不成环。图 2-1 的扫描在这个系统上走完全部子集而不停，与这段论证一致。

推论 4.1Kruskal 算法给出最小生成树。

推论的得出要多绕一步，因为定理说的是最大权而 Kruskal 求最小权。把每条边的权重换成 $C - w(e)$ （ $C$ 取任意大于最大边权的常数），权重的大小顺序整体翻转，任一固定大小的边集其新权重之和等于 $C \cdot |A| - w(A)$ ；由于图连通时所有极大无环边集都恰有 $|V| - 1$ 条边，最大化新权重与最小化原权重在这些边集上完全等价。定理保证降序贪心拿到新权重最大者，翻译回去就是原权重最小的生成树，而降序处理 $C - w$ 恰是升序处理 $w$ ，即 Kruskal 的循环。

页面的底图是 4 个点 5 条边的图。原权重下贪心取到 $e_1, e_4, e_3$ ，总权重 18；把权重换成 $10 - w$ 后取到 $e_2, e_3, e_5$ ，按原权重计是 12，正是这张图的最小生成树。Prim 与 Kruskal 一页用 cut theorem 证明同一件事，两条路径互不依赖：cut theorem 直接针对生成树，matroid 则把生成树换成任何满足交换性质的结构后论证一字不改。判环那一步的实现见并查集。

5 · 崩掉的独立系统

matching 与 interval 两个系统只差交换性质这一条，贪心在它们上面立刻失去保证。

matching 的最小见证是一条 4 个点的路径，三条边 $e_1$ 、 $e_2$ 、 $e_3$ 依次相接。取 $S$ 为全部三条边：极大 matching 有 $\lbrace e_2 \rbrace$ 与 $\lbrace e_1, e_3 \rbrace$ 两种，大小分别是 1 和 2。中间那条边一旦选中就把两端都堵死，而它自己只值一条边。

interval 的见证同样只要三个元素： $A = [0, 10)$ 、 $B = [0, 4)$ 、 $C = [5, 10)$ ，权重 10、6、6。 $\lbrace A \rbrace$ 与 $\lbrace B, C \rbrace$ 都是极大的两两不交子集，大小 1 与 2。贪心先拿权重最大的 $A$ ，得 10；最优是 12。这解释了交换论证那一页末尾留下的问题：无权版本的 interval scheduling 能贪心，靠的不是这个独立系统的结构，而是 earliest finish time 这条特定规则加上「目标函数是计数」这个特定权函数。Rado–Edmonds 要求的是对一切权函数都成立，区间系统达不到，所以带权版本只能退回动态规划。

值得留意的是，五个系统里哪些是 matroid，页面并没有写死结论去展示。每个系统只带一个标注，测试断言的是「标注与实测扫描的结果一致」——扫描找不到见证才算 matroid。同一个测试还断言「贪心权重等于暴力最优」这件事在五个系统上的真假模式与标注完全对齐，两项独立检查互为佐证。

6 · 参考文献

Whitney, H. (1935). On the abstract properties of linear dependence. American Journal of Mathematics, 57(3), 509–533.
Rado, R. (1957). Note on independence functions. Proceedings of the London Mathematical Society, s3-7(1), 300–320.
Edmonds, J. (1971). Matroids and the greedy algorithm. Mathematical Programming, 1(1), 127–136.
Oxley, J. (2011). Matroid theory (2nd ed.). Oxford University Press.