拟阵贪心定理

贪心选择看似只比较当前元素，但增广公理约束了所有竞争者：一个有 $k$ 个元素的独立集，不可能在第 $i$ 重的位置超过贪心而又完全避开当前可扩充元素。否则增广公理会指出一个更重且本来就能加入的元素，直接与扫描过程矛盾。

反过来，若增广失败，就把那个较小却无法扩充的集合稍微加权。贪心会先全部选入它，随后被困住；较大的独立集却有更高总权。这个构造说明，普遍正确性恰好需要拟阵结构。

四列矩阵的完整扫描 ​

使用秩与闭包页理路拟阵的秩与闭包Matroid rank · Matroid closure · Matroid flat证明有限拟阵秩的子模性及秩公理的逆向重建，由此推出闭包交换，并用同一个四列矩阵计算秩、平坦与依赖证书。的同一个有理数矩阵

并赋权

因此扫描次序为 $c,d,a,b$。

结果 $ac$ 的权重为 $10$。为独立核对这个有限例子，全部五个基及其权重为

非负权重保证任意独立集可扩充到一个权重不减的基，因此 $10$ 同时是独立集最优值。这个五项核算检验算例；下面的增广证明才负责任意拟阵。

权重符号决定是否必须继续填满 ​

对最大权基问题，即使剩余元素权重为负，也必须继续扩充到基。对任意权重的最大权独立集问题，负权元素一定可以删去而改善目标，所以只需扫描非负权元素，遇到负权部分便停止。

例如在上述矩阵上改用权重 $(-1,-2,-3,-4)$，完整扫描选出 $ab$，它是最大权基，权重为 $-3$；最大权独立集却是权重为 $0$ 的空集。当所有权重非负时，零权元素不改变值，一个最优独立集可以扩充为同值的最优基，但它本身未必已经是基。

只有遗传性时的失败 ​

取

算法先接受 $a$，随后无法加入 $b$ 或 $c$，只得到权重 $3$；独立集 $bc$ 的权重为 $4$。失败对应 $a$ 无法从更大的 $bc$ 中吸收任何元素，违反增广公理。

一般背包约束也不自动满足拟阵增广性；不能把本定理理解为“任何向下封闭约束都适合按权重贪心”。

正向：每个成功前缀都按分量压过竞争者 ​

设贪心依次接受 $g_1,\dots ,g_r$，其权重非增。扫描结束时所得独立集是极大的：某元素若曾被拒绝，当时的集合加它已依赖，后续更大的集合加它也不可能独立。因此在拟阵上最终 $r=r(E)$。

固定 $k\le r$，取任意 $k$ 元独立集 $J=\{j_1,\dots ,j_k\}$，也按权重非增排列。我们证明

若某个 $i$ 不成立，令

它们独立且 $|G|=i-1<|J_i|=i$。增广公理给出 $e\in J_i\setminus G$，使 $G+e$ 独立。又因

元素 $e$ 必定在 $g_i$ 之前被扫描。当时已选集合 $H$ 是 $G$ 的子集，遗传性使 $H+e$ 也独立，算法本应接受 $e$，使它进入 $G$，矛盾。

对式 (1) 求和，即得

证明没有用权重非负性，所以适用于全部实权重。取 $k=r$，所有拟阵基大小均为 $r$，得到第 3 条。若权重非负，任意独立集能扩充为权重不减的基，再用基最优性，得到第 2 条。相等权重的次序也不影响论证，因为反证只在严格不等式处使用先后顺序。

逆向：把失败的增广变成统一反例 ​

设独立系统不是拟阵。已有遗传性，故存在独立集 $S,T$，使

记 $m=|S|$。必有 $m>0$：若 $S=\varnothing$，$T$ 的任一单元素子集都独立，不可能增广失败。赋予非负权重

算法先扫描 $S$，因 $S$ 独立而全部接受，随后每个 $T\setminus S$ 中的元素都被拒绝。之后可能接受零权元素，却不会增加目标值。因此最终权重恰为

但

这违反第 2 条。若目标是基，把 $T$ 扩充为某个极大独立集 $B_T$；系统有限，故扩充能够结束，又因权重非负而有 $w(B_T)\ge w(T)$。算法自身也返回极大独立集，于是它同样不是最大权基，违反第 3 条。逆向不需要事先假定所有极大独立集等势。

秩前缀、算法接口与两拟阵边界 ​

记扫描前 $i$ 个元素的集合为 $P_i$，扫描后的已选集为 $G_i$。在拟阵上，$G_i$ 是 $P_i$ 的极大独立子集，所以

这把算法的接受记录变成秩增量理路拟阵的秩与闭包Matroid rank · Matroid closure · Matroid flat证明有限拟阵秩的子模性及秩公理的逆向重建，由此推出闭包交换，并用同一个四列矩阵计算秩、平坦与依赖证书。：第 $i$ 个元素被接受，当且仅当 $r(P_i)-r(P_{i-1})=1$。四列例子中前缀秩依次为 $1,1,2,2$，正好记录“接受、拒绝、接受、拒绝”。

若独立性以 oracle 给出，排序后完整扫描至多作 $|E|$ 次独立性查询；定理保证组合正确性，不保证 oracle 本身便宜。贪心算法理路贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。在图拟阵理路图拟阵Graphic matroid以图边为底集、以无环边集为独立集的拟阵。上成为最大权生成森林算法；将权重取负可处理最小权基。

两个拟阵的共同独立集族通常不再满足增广公理。例如三边路径的匹配中，中间一边无法吸收两端边中的任一边。此时应使用拟阵交的增广与秩证书理路拟阵交定理Matroid intersection theorem · Edmonds matroid intersection theorem两个有限拟阵的最大共同独立集大小，等于一次底集切分上的两侧秩之和的最小值。及其既有算法接口；单拟阵贪心定理不会自动延伸到两个约束的交。