形式陈述

设 $(E,\mathcal I)$$(E,\mathcal{I})$ 是有限独立系统，即 $\varnothing\in\mathcal I$$\varnothing \in \mathcal{I}$，且 $I\in\mathcal I$$I\in \mathcal{I}$、$J\subseteq I$$J\subseteq I$ 蕴含 $J\in\mathcal I$$J\in \mathcal{I}$。给定非负权重 $w:E\to\mathbb R_{\ge0}$$w:E\to {\mathbb{R}}_{\ge 0}$，按权重非增次序扫描元素，并在 $I\cup\{e\}\in\mathcal I$$I\cup \{e\}\in \mathcal{I}$ 时加入 $e$$e$。Rado–Edmonds 贪心刻画称：该算法对每个非负权重都产生最大权独立集，当且仅当 $(E,\mathcal I)$$(E,\mathcal{I})$ 是拟阵。若目标限定为最大权基，则允许任意实权重，结论等价。

直觉

交换公理保证任何较轻的局部选择都能被较重元素替换而不破坏可行性。反过来，一旦交换失败，就可专门设计权重，让贪心过早占用某个元素并错失更优组合。

例子与边界

在图拟阵上，算法就是 Kruskal 型的最大权生成森林算法；在线性拟阵上，它按权重选择保持线性无关的向量。非负条件对“最大权独立集”版本不可省略：若所有权重为负，空集优于任何非空基，而强制扫描并加入的算法会失败。对一般背包可行集，遗传性成立但交换性失败，按单位价值或总价值排序都不能获得普遍正确的贪心算法。定理只保证给定独立性判定器后的组合正确性，不自动保证判定本身高效。

推论与应用

该定理解释了为何生成树和线性基可由同一贪心模板求解，并给出识别“贪心对所有权重都正确”的结构性判据。它也是拟阵交、次模优化和组合优化对偶理论的起点。

参考资料

• James Oxley, Matroid Theory, 2nd ed., Oxford University Press, 2011，Ch. 1, the greedy characterization of finite matroids。
• J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001，Ch. 13, matroids and the greedy algorithm。