拟阵是很多贪心算法的基础，也可以帮助我们验证自己的贪心算法的正确性，接下来是我从抄《算法导论》中整理出来的一些关于拟阵的性质：
定义
吐槽：虽然说拟阵叫拟阵，但是这个 “阵” 和矩阵的阵几乎一点关系都没有（名字的由来纯粹是历史遗留问题），拟阵和矩阵的关系就像 JavaScript 和 Java，雷锋和雷峰塔一样……
拟阵：拟阵是一个二元组 \(M = (S, I)\)，其中 \(S\) 为一个有限集，\(I\) 为 \(S\) 的一个族（即子集的集合）并满足如下性质：
- 遗传性：若 \(B \in I\) 且 \(A \subseteq B\)，则 \(A \in I\)。
- 交换性：若 \(A \in I, B \in I\) 且 \(|A| < |B|\)，那么存在元素 \(x \in B \setminus A\)，使得 \(A \cup \{x\} \in I\)。（又是一个误导性的名字……）
\(I\) 中的集合成为 \(S\) 的独立子集。
图拟阵：对于一个图 \(G = (V, E)\)，我们定义它的图拟阵为 \(M_G = (S_G, I_G)\)，当中 \(S_G\) 为边集，而 \(E\) 的子集 \(A \in I_G\) 的当且仅当 \(A\) 中无环（森林）。图拟阵与最小生成树有关（这也解释了为什么最小生成树的算法都是贪心）。由于森林的子图还是森林，因此该拟阵的遗传性显然。而该拟阵的交换性也在算法导论中有详细的证明，简单讲起来就是对于森林 \(A, B\)，\(|A| < |B|\)，我们知道 \(A\) 中有 \(|V| - |A|\) 棵树，\(B\) 中有 \(|V| - |B|\) 棵树比 \(A\) 少，因此一定存在一条边 \((u, v)\) 使得 \(u, v\) 在 \(A\) 中分别属于两棵树，而在 \(B\) 中却在一棵树上，显然 \(A \cup \{(u, v)\} \in I_G\)，证毕。
拓展：对于集合 \(A\)，若存在元素 \(x\) 使得 \(A \cup \{x\} \in I\)，则称 \(x\) 是 \(A\) 的一个拓展。
最大独立子集：不存在拓展的独立子集。
定理：所有的最大独立子集等大小。
证明：反证， 假设存在最大独立子集 \(A, B\) 使得 \(|A| < |B|\)，由交换性，必然存在 \(x \in B \setminus A\) 是 \(A\) 的一个拓展，证毕。
加权拟阵：若存在一个权函数 \(w\) 为所有 \(S\) 的元素定义了严格正的权值，则称 \(M\) 为加权拟阵，定义独立子集 \(A\) 的权值为： \[ w(a) = \sum_{x \in A} w(x) \]
和贪心的关系
很多贪心问题可以转化为在拟阵上求最大权独立子集，或者称为拟阵的最优子集。
例：最小生成树算法当中我们可以对于边 \(e\) 定义权重 \(w(e) = l_{max} - l(e)\)，其中 \(l(e)\) 为边的长度，\(l_{max}\) 为一个极大的数。在图拟阵上最大化独立子集权重必然等价于在图上最小化生成树边权（因为生成树的边数总是固定的）。
求解最优子集的算法：将 \(S\) 的所有元素 \(x\) 按照 \(w(x)\) 从大到小排序，初始化 \(A = \emptyset\)，然后依次从大到小考虑每个元素 \(x\)，并尽可能地用 \(x\) 去拓展 \(A\)，最后得到的集合必定是最优子集。
这个算法的贪心本质暴露无遗，接下来我们证明这个算法的正确性：
引理 1（贪心选择）：若将 \(S\) 的元素从大到小排序，令 \(x\) 为排序后第一个使得 \(\{x\} \in I\) 的元素，那么必然存在一个包含 \(x\) 的最优子集。
证明：如果不存在 \(x\)，则最优子集为空，显然。
否则，假设我们有一个不含 \(x\) 的最优子集 \(B\)，显然由遗传性，对于 \(y \in B\) 都有 \(\{y\} \in I\)，又因为我们选择 \(x\) 的方式显然由 \(w(x) \ge w(y)\)。我们初始化 \(A = \{x\}\)，利用和 \(B\) 交换性不断拓展 \(A\) 直至 \(|A| = |B|\)，此时必定存在另一元素 \(y\)，使得 \(A \setminus \{x\} = B \setminus \{y\}\)，又因为 \(w(x) \ge w(y)\)，那么 \(A\) 一定不会比 \(B\) 差，得证。
引理 2：若元素 \(x\) 是 \(A\) 的一个拓展，那么 \(\{x\} \in I\)，换而言之，\(x\) 是 \(\emptyset\) 的拓展。
证明：由定义，\(A \cup \{x\} \in I\)，由遗传性显然。
推论（逆否命题）：若 \(x\) 不是 \(\emptyset\) 的拓展，那它也一定不是其他非空独立子集的拓展。
引理 3（最优子结构）：在如上算法中选择完 \(x\) 之后，在 \(M = (S, I)\) 中寻找最优子集等价于在 \(M'= (S', I')\) 中寻找最优子集，其中： \[ \begin{aligned} S' &= \{y \mid \{x, y\} \in S\} \\ I' &= \{B \mid B \subseteq S \setminus \{x\}, B \cup \{x\} \in I\} \end{aligned} \] 即我们可以忽略 \(x\) 继续我们的算法。
证明：如果我们在 \(M'\) 当中选出了最优子集 \(A'\)，则显然 \(A' \cup \{x\}\) 是 \(M\) 的独立子集，并且由 \(x\) 的选择方式可知也是最优子集，证毕。
贪心正确性的证明：由引理 2 的推论，我们知道贪心算法没能一开始用来拓展的 \(x\) 一定在后面也没有用。由引理 3，选择完 \(x\) 之后我们把问题缩小，还可以进一步贪心，此时贪心实质上是在 \(M'\) 上寻找最优子集。证毕。
从以上讨论我们可以看出，对于一类问题，如果我们可以以某种方式把它规约为在拟阵上求取最优子集，那你一定可以使用贪心解决，这给很多贪心算法（例如 Kruskal）提供了理论支持。