擬陣貪婪定理（matroid-greedy theorem）

與其為每個貪婪演算法另創新的正確性證明，若有一條定理能一次認證一整個族群呢？擬陣貪婪定理正是如此。它說：取任何擬陣，給每個元素附上權重，那麼「在保持獨立的同時抓取重元素」這條簡單貪婪規則，永遠產生一個最大權基。不需要逐問題的巧思。

精確地說：令 M 為基底集 E 上的擬陣，每個元素帶非負權重。執行貪婪——把 E 由重到輕排序，從空集開始，依序考慮每個元素，當且僅當加入後仍獨立時才加入。定理保證所得獨立集在所有獨立集中總權最大（且是一個基）。值得注意的是逆命題也成立：若這條貪婪規則對「每一種」權重選擇都產生最佳獨立集，則該獨立系統必為擬陣。所以擬陣恰好是「加權貪婪普遍正確」的結構——這有時稱為拉多-埃德蒙茲定理。貪婪可行的證明關鍵在交換性質：每當貪婪的部分集比某個假設更好的集更小，交換性質讓貪婪借入一個它尚未拒絕的元素，而因為貪婪總取最重的可加入元素，它從不換差。這本質上是把交換／領先論證提升到完全一般的層次。

套用到圖擬陣（圖的森林），此定理立刻證明克魯斯卡最小生成樹演算法最佳——你免費得到切割性質的正確性作為特例。它真正的價值是診斷性的：要知道一個貪婪想法是否安全，你可以問「可行集是否構成擬陣？」而非自製一個量身證明。誠實的限制：許多真正的貪婪問題（最多工作數的區間排程、霍夫曼編碼）並非自然的擬陣，仍需自己的交換論證；而定理假設你要的是最大權獨立集，而非別的目標。它是一個強而有力的充分條件，並非所有貪婪的普遍解釋。