拟阵笔记

Posted on 2018-10-07 Views:

拟阵是很多贪心算法的基础，也可以帮助我们验证自己的贪心算法的正确性，接下来是我从抄《算法导论》中整理出来的一些关于拟阵的性质：

定义

吐槽：虽然说拟阵叫拟阵，但是这个“阵”和矩阵的阵几乎一点关系都没有（名字的由来纯粹是历史遗留问题），拟阵和矩阵的关系就像JavaScript和Java，雷锋和雷峰塔一样……

拟阵：拟阵是一个二元组 M = (S, I) ，其中为一个有限集，为的一个族（即子集的集合）并满足如下性质：

遗传性：若 $B \in I$ 且 $A \subseteq B$ ，则 $A \in I$ 。
交换性：若 $A \in I, B \in I$ 且，那么存在元素 $x \in B \setminus A$ ，使得 $A \cup \{x\} \in I$ 。（又是一个误导性的名字……）

中的集合成为的独立子集。

图拟阵：对于一个图 G = (V, E) ，我们定义它的图拟阵为 M_G = (S_G, I_G) ，当中 S_G 为边集，而的子集 $A \in I_G$ 的当且仅当中无环（森林）。图拟阵与最小生成树有关（这也解释了为什么最小生成树的算法都是贪心）。由于森林的子图还是森林，因此该拟阵的遗传性显然。而该拟阵的交换性也在算法导论中有详细的证明，简单讲起来就是对于森林 A, B ， |A| < |B| ，我们知道中有 |V| - |A| 棵树，中有 |V| - |B| 棵树比少，因此一定存在一条边 (u, v) 使得 u, v 在中分别属于两棵树，而在中却在一棵树上，显然 $A \cup \{(u, v)\} \in I_G$ ，证毕。

拓展：对于集合，若存在元素使得 $A \cup \{x\} \in I$ ，则称是的一个拓展。

最大独立子集：不存在拓展的独立子集。

定理：所有的最大独立子集等大小。

证明：反证，假设存在最大独立子集 A, B 使得 |A| < |B| ，由交换性，必然存在 $x \in B \setminus A$ 是的一个拓展，证毕。

加权拟阵：若存在一个权函数为所有的元素定义了严格正的权值，则称为加权拟阵，定义独立子集的权值为：

$w(a) = \sum_{x \in A} w(x)$

和贪心的关系

很多贪心问题可以转化为在拟阵上求最大权独立子集，或者称为拟阵的最优子集。

例：最小生成树算法当中我们可以对于边定义权重 $w(e) = l_{max} - l(e)$ ，其中 l(e) 为边的长度， $l_{max}$ 为一个极大的数。在图拟阵上最大化独立子集权重必然等价于在图上最小化生成树边权（因为生成树的边数总是固定的）。

求解最优子集的算法：将的所有元素按照 w(x) 从大到小排序，初始化 $A = \emptyset$ ，然后依次从大到小考虑每个元素，并尽可能地用去拓展，最后得到的集合必定是最优子集。

这个算法的贪心本质暴露无遗，接下来我们证明这个算法的正确性：

引理1（贪心选择）：若将的元素从大到小排序，令为排序后第一个使得 $\{x\} \in I$ 的元素，那么必然存在一个包含的最优子集。

证明：如果不存在，则最优子集为空，显然。

否则，假设我们有一个不含的最优子集，显然由遗传性，对于 $y \in B$ 都有 $\{y\} \in I$ ，又因为我们选择的方式显然由 $w(x) \ge w(y)$ 。我们初始化 $A = \{x\}$ ，利用和交换性不断拓展直至 |A| = |B| ，此时必定存在另一元素，使得 $A \setminus \{x\} = B \setminus \{y\}$ ，又因为 $w(x) \ge w(y)$ ，那么一定不会比差，得证。