擬陣（matroid）
/ MAY-troid /
為何貪婪對某些問題運作得漂亮、對另一些卻失敗？擬陣理論給出單一的抽象答案。擬陣是一種數學結構，捕捉「獨立性」的本質——像一組沒有冗餘的向量，或一組沒有環的圖邊——其一般性足以一次解釋一整類貪婪的成功。
形式上，擬陣是一個基底集 E 連同一族稱為獨立集的子集，滿足三條公理。第一，空集是獨立的。第二，遺傳（向下封閉）：獨立集的每個子集都獨立。第三，也是關鍵的，交換性質：若 A 與 B 都獨立且 A 的元素少於 B，則 B 中某個元素可加入 A 而保持 A 獨立。兩個經典例子使其具體。圖擬陣：基底集＝圖的邊，獨立集＝無環邊集（森林）；加入不造環的邊使你保持獨立，而交換性質成立是因為較小的森林總能從較大的森林借一條邊而不造環。線性擬陣：基底集＝一組向量，獨立集＝線性獨立的子集。兩者中，極大獨立集稱為基（一棵生成樹，或一組向量基），而一個驚人的事實是：所有基大小相同——稱為秩——這由交換性質推出。
報酬就是擬陣貪婪定理：若你想在加權擬陣中求最大權獨立集，「由重到輕考慮元素、加入每個能保持獨立者」的貪婪規則可證為最佳——對每個擬陣皆然，無需另寫交換論證。這正是克魯斯卡最小生成樹可行的原因（圖擬陣）。它也使失敗的故事更鋒利：0/1 背包的可行集「不」構成擬陣（交換性質失敗），這就是貪婪在那裡崩壞的結構性原因。擬陣不涵蓋每個貪婪問題——有些需要自己的論證——但它一舉解釋了一大重要族群。
三角形上的圖擬陣（邊 AB, BC, CA）：獨立集是所有無環的邊子集——空集、每條單邊、以及每對邊。全集 {AB, BC, CA} 是相依的（一個環）。每個基（極大獨立集）是一對邊——一棵生成樹——皆大小為 2，即秩。
圖的森林構成擬陣；三條公理（含空集、遺傳、交換）正是貪婪達到最佳所需。
並非每個貪婪能解的問題都是擬陣，也並非每個貪婪的成功都需要擬陣理論——但當可行集構成擬陣時，由擬陣貪婪定理，貪婪最佳性自動成立。