拟阵是用来证明一些关于贪心问题的结论——尤其是图论上贪心问题的结论——的很有力的工具。

现在考虑一个线性空间。考虑一些向量集合，一个向量集合被称为独立的当且仅当其中向量皆线性无关。

我们都知道，向量集合的独立性有很多优秀的性质（下文会提），那么，我们能不能放宽限制，即原集合不一定是一个线性空间而可能是别的一些东西，而这些性质仍然保留呢？

1. 拟阵的来源

抽象的说，现有集合 $E$，在 $2^{E}$ 中抽出一些集合并钦定它们是独立的，把这些集合的全体记为 $\mathcal I$。我们提出一个自然的要求：

$\varnothing\in\mathcal I$：空集是独立的。这……总不能不满足吧？

若 $B\subseteq A\in\mathcal I$，则 $B\in I$：一个独立集的子集一定独立。这也很自然。

如果不满足这两个性质，简直难以想象这个所谓独立性会是什么鬼样子。

由于向量已经不存在了，所有的加法数乘全都灰飞烟灭了，我们再来看看有什么可以保留。

回想线性空间的情况。当时我们会把一个极大的，即不能再加元素的独立集称作基。我们自然希望基的大小都是相等的。不过这样表述也太不美观了，非常强行。

再考虑一下：我们可以试着要求任何没有达到基的大小的独立集都不极大。但是这样我们要找到基的大小，还是不大自然。先找到一个极大的独立集再要求其他独立集不极大也太怪了。

下面是第三个性质的最终定稿。

若 $A,B\in\mathcal I$，$|B|<|A|$，则 $B$ 必不极大，而且可以通过加入一个 $A$ 中的元素来变为一个更大的独立集。

于是，

我们把满足上述三个条件的二元组 $(E,\mathcal I)$ 称作一个拟阵。

2. 过于经典的例题

2.1. 线性基

为什么一个元素进了线性基就不会再出来呢？很神奇对不对？

我们来证明，这样求出的独立集（下文称为“假基”）总是极大的。

假设这是我们第一次出错，以前维护的假基一直是对的（是一个实实在在的基）。我们以一个随便取的基（下文称为“真基”）作为比较。

• 如果一次插入没有使真基变大，那么也一定不会使假基变大（假基大小当然不可能超过真基）。故不会有“真基没变假基却变大了”的情况。

• 如果一次插入使真基变大，而且没有使假基变大。我们来证明这种情况也不可能发生。如果它发生了，则必有一属于真基的元素可被成功插入到假基中，这个元素不可能是刚刚被假基拒绝的那个（显然），也不可能是其他元素，理由如下。

• • 如果这个元素能插入于假基中，也一定能插入曾经的假基，至少是上一步插入后的假基（当时该元素一定已被试图插入假基过了），也就是说我们当时维护错了。这违反了假设。

从而唯一的可能就是：我们的算法从不出错。上面的论证可比什么“换不换都一样”的鬼话靠谱多了。

注意——上述论证可没有用到任何线性基的细节，比如上三角矩阵或模 $2$ 之类的东西。你完全可以把它照抄一遍来证明另一个拟阵问题。

2.2. 最大权值线性基

我们立即可以由之前的定义推出一个显然但重要的定理，基交换定理：

现有两个基 $A,B$。对于任意 $x\in A/B$，必有 $y\in B/A$ 使得 $A/\{x\}\cup \{y\}$ 也独立，从而是一个基。

下面我们来证明，最大权值线性基的算法（如果你不知道的话：把元素按权值排序然后直接跑线性基）总是真的能求出最大权值线性基。

假设这是我们第一次出错，以前维护的假最大权值基一直是最大权值的。设在这次分歧中，标准答案选了 $x$ 而我们的算法选了 $x'$。

显然必定有 $w(x)<w(x')$，那么标准答案为了扳回劣势必然会在接下来的至少一次选择中选出 $w(y')<w(y)$，但是根据基交换定理，假最大权值基 $/\{y'\}\cup\{y\}$ 也是基，也就是说假最大权值基也会优先选择 $y$，即标准答案没有机会翻盘。

从而唯一的可能就是：我们的算法从不出错。

注意——上述论证可没有用到任何线性基的细节，比如上三角矩阵或模 $2$ 之类的东西。你完全可以把它照抄一遍来证明另一个拟阵问题，比如最小生成树。

3. 秩

众所周知，在向量空间的情况下，秩函数是非常重要的特征，我们自然希望在拟阵的情况下也是如此。

• 对于一个 $E$ 的子集 $S$，称它的秩为它基的大小，记为 $r(S)$。秩函数当然需要满足以下性质：

• $0\le r(S)\le |S|$。 $B\subseteq A\Rightarrow r(B)\le r(A)$。

• 但是这还不够。显然，一个子集 $S$ 中增加一个“向量”最多只能使它的秩变动 $1$；如果这个“向量”本身就并不独立，那么 $S$ 的秩就不会变化。类似地我们有如下总结。

• • 如果 $A,B$ 不交，则 $r(A\cup B)-r(A)\le r(B)$。

• 另外，一个子集 $S$ 中删去一个秩为 $r$ 的集合对 $S$ 秩的影响不会超过 $r$。我们把这两点总结如下的次模性：

• $r(A\cup B)+r(A\cap B)\le r(A)+r(B)$。

• （它也可以很简单地，不用上面的玄学分析地证明）

• 事实证明，这就够了。具体来说，给定秩函数，我们定义它推出的独立集为 $r(S)=|S|$ 的所有 $S$。满足上述三个条件的秩函数总是能倒推出满足文章开头的三个条件的独立集。这里不作推导。

4. 拟阵交

他 来 了

考虑这样一个问题：

现有拟阵 $M_1=(E,\mathcal I_1),M_2=(E,\mathcal I_2)$，求 $M_1\cap M_2=(E,\mathcal I_1\cap \mathcal I_2)$ 的基大小。

必须注意 $M_1\cap M_2$ 甚至可能不是一个拟阵。

这个问题的意义不可谓不重大。二分图匹配（左图度皆不大于一 $\cap$ 右图度皆不大于一，可以验证这两个都是拟阵）和最小树形图（看作无向图时无环 $\cap$ 每个点入度不超过一，特别地根入度为零）都是标准的拟阵交问题，要是我们能解决拟阵交问题，这些题不全都乱杀了吗！

然而三个及以上的拟阵交是 $\mathsf{NPHard}$ 的……

不过两个拟阵的交问题的确能得到较为优秀的解决方案，主要依赖于以下定理（的证明）：

$$\max_{I\in\mathcal I_1\cap\mathcal I_2}|I|=\min_{S\subseteq E}r_1(S)+r_2(E/S)$$

4.1. 简单的部分

首先我们来证明，总是有

证明如下。

$$|I|=|I\cap S|+|I\cap (E/S)|=r_1(I\cap S)+r_2(I\cap (E/S))\le r_1(S)+r_2(E/S)$$

4.2. 一个构造

现在的任务只剩下构造一组取到等号的 $I$ 和 $S$：其实也就是解决拟阵交中最大独立集大小的问题。思路是从 $I=\varnothing$ 开始逐步调整。

构造一幅有向二分图，左点集为 $I$，右点集为 $E/I$。存在边 $(x\in I,y\in E/I)$ 当且仅当 $I/\{x\}\cup \{y\}$ 是 $M_1$ 的独立集，而存在边 $(y\in E/I,x\in I)$ 则当且仅当它是 $M_2$ 的独立集。

记点集 $X_1=\{x\in E/I,(I\cup\{x\}\in\mathcal I_1)\}$，$X_2$ 亦然。

我们在上图中找到一条最短的，由 $X_1$ 某点至 $X_2$ 的一条路径（长度可以为 $0$，即只有一个单独的点），并记这条路径上经过的所有点（包括首尾）为 $P$。

赋 $I$ 为 $I\oplus P$，回到开头。找不到 $P$ 时停止算法。

这里我们不打算证明该算法的正确性。易知这个算法的复杂度为 $O(r^2n)$，其中 $r=\max(r_1(E),r_2(E))$。

4.3. 带权拟阵交

只需在点上赋权：若 $x\in I$ 则设为 $-w(x)$，否则设为 $w(x)$，然后求权值最小、在权值最小时边数最小的路径即可。可以证明总是没有负环。

5. 过于经典的例题

你肯定很想把刚才的算法应用到二分图匹配和最大匹配上，不幸的是它被匈牙利和 KM 吊打了。

你肯定很想把刚才的算法应用到最小树形图上，不幸的是它被 2020 张哲宇集训队论文吊打了。

所以拟阵交有什么用呢……咱也不懂啊。