拟阵，在贪心问题中得以应用的数学工具。本文需要线性代数基础的前置知识。

拟阵

        有限拟阵是一个序偶$(S,I)$，其中$S$为一个有限集合，而$I$为$S$中某些子集组成的有限非空集合。即有$x\in I$，则$x\subseteq S$。
        对于拟阵的组成，遵循下面的三个公理：

  • $\varnothing \in I$
  • 【遗传性】若$A\in I$且$B\subseteq A$，则有$B\in I$。
  • 【增广性（交换性）】对于$A,B\in I$,若$|A|<|B|$，则$\exists x\in B-A$，有$A\cup \{x\}\in I$。

        称$I$中的集合为独立集。

基与环

        对于拟阵$(S,I)$，若$A\in I$，且$A\cup\{x\}\not \in I,\forall x\in S-A$，则称$A$为一个极大独立集，或称基。
        对于$A\subseteq S$，若有$A\not \in I$且$A-\{x\}\in I,\forall x\in A$，则称$A$为极小非独立集，或称环，也叫回路。
        容易得到下面这一个性质：

  • 对于一个拟阵，其基的大小都相同。

        证明可以使用反证法。若两个基$A$与$B$大小不同并令$|A|<|B|$，则根据增广性，$\exists x\in B-A$，有$A\cup\{x\}\in I$，这样$A$便得到了扩展，这与$A$为基矛盾。
        其次，我们还可以得到一个重要的定理：

  • 【基交换定理】对于拟阵$(S,I)$，若$A$与$B$是拟阵的基，且$A\not=B$，则$\forall x\in A-B$，$\exists y\in B-A$，使得$(A-\{x\})\cup \{y\}\in I$。

证明：
        根据遗传性，$A-\{x\}\in I$。然后由增广性，$\exists y\in B-(A\cup \{x\})$即$\exists y\in B-A$，使得$(A-\{x\})\cup \{y\}\in I$。

        对于拟阵$(S,I)$ ，则$\forall A\subseteq S$ ，定义其秩函数为， $A$的子集中极大独立集的大小，记作$r(A)$。

常见拟阵

组合拟阵

        对于一个有限集合$S$，令$I=\{A||A|\leq k\}$，则$(S,I)$组成一个拟阵。记为$U_n^k$。
        很容易证明该拟阵遵循三条公理。

向量拟阵

        对于一组$n$维向量集合$S$，令$I=\{A\subseteq S|A$线性无关$\}$，则$(S,I)$是拟阵。
        容易发现线性无关的向量集合子集仍是线性无关的，重点在于证明其满足增广性质，使用反证法。对于两个向量集合$A,B\in I$，假定$|A|<|B|$，若$\forall x\in B-A$都有$A\cup \{x\}\not \in I$，这说明$A$能够线性表示$B$。这样$B$的秩应该为$|A|$，但是由于$B\in I$，$B$的秩又应该为$|B|$，矛盾。由此可知增广性质成立。

匹配拟阵

        对于二分图$(U,V,E)$，令$I=\{A\subseteq U|A$可以与$V$完美匹配$\}$，则$(U,I)$为拟阵。证明略。

环拟阵

        对于无向图$G(V,E)$，令$I=\{A\subseteq E|A$无环$\}$，则$(S,I)$为拟阵。
        这里只证明第三条公理成立。对于$A,B\in I$，且$|A|<|B|$，由于两者都无环，可知$G(V,A)$以及$G(V,B)$都是森林，且$G(V,A)$中的连通块数量多于$G(V,B)$，那么必然可以从$B-A$中得到一条边$x$，使得$A\cup\{x\}$仍无环。

带权拟阵

        对于拟阵$(S,I)$，我们给$S$中每一个元素$x$赋予一个非负权值$w(x)$，则成为了带权拟阵。此时一个集合的权值定义为其中元素的权值之和。
        易知，权值最大的集合必然为基。寻找权值最大的基是一个重要的问题，该问题可以用贪心算法解决。伪代码如下：

1
2
3
4
5
6
7
Set get(M,w){
	对M.S按权值w(x)从大到小排序
	A=∅
	for x in M.S:
		若A∪{x}∈M.I，则A=A∪{x}
	return A
}

        这里返回一个集合，$M=(S,I)$是拟阵。
        这个算法是正确的，考虑利用拟阵的性质来简单地证明。
        首先假定$A=\{x_1,x_2,\cdots,x_n\}$是权值最大的集合（$x$按权值降序排列），则根据遗传性，$\{x_1\},\{x_1,x_2\},\cdots,\{x_1,x_2,\cdots,x_n\}$必然都在$I$中，也就是说，利用这个算法是可以取到的。
        另一方面，若$x$是权值最大的元素，且$\{x\}\in I$，则我们将会把它加入$A$，这样的正确性在于：我们确定x必然是某一个权值最大集合的元素，证明如下：
        若权值最大的集合为$B$，包含$x$的权值最大集合为$A$，假设$w(A)<w(B)$。令$C=A\cap B$，则$w(A-C)<w(B-C)$，将$A-C,B-C$表示为$A-C=\{x\}\cup A’,B-C=\{y\}\cup B’$，这里$y$是$B-C$中某一元素，那么根据基交换定理，可知$D=C\cup B’\cup\{x\}\in I$。显然有$w(D)=w(C)+w(B’)+w(x)\geq w(C)+w(B’)+w(y)=w(B)$，其中有$x\in D$，这样就得到了一个包含$x$但是权值不小于$B$的集合，矛盾。因此可知$x$必然在某一个权值最大的集合中，由此归纳下去，可知贪心算法正确。
        该算法的时间复杂度为$O(nlogn+nf(n))$，其中$f(x)$是判断元素是否在$I$中的代价。

拟阵与最小生成树

        我们尝试用拟阵来解决最小生成树问题。
        构造无向图$G(V,E)$的环拟阵$M=(S,I)$，容易发现，求最小生成树就是求拟阵的最小权值集合。上文中探讨的是最大权值，我们可以将边权取反，再加常数使得转化为等价的最大权值问题。
        根据最大权值集合的贪心算法，我们可以将权值从大到小排序（就是原边权最小到大排序），然后依次放入，判断能否出现在$I$中，即判断是否有环出现。环可以用并查集维护，这就得到了kruskal算法。这就是kruskal算法正确性的数学解释。

拟阵交

        对于同一个集合$S$，构造两个拟阵$M_1=(S,I_1),M_2=(S,I_2)$，定义$M_1\cap M_2=(S,I_1\cap I_2)$。
        在很多情况下，我们希望得到拟阵交的最大的集合元素数目。然而，两个以上的拟阵交是NP问题，不过对于两个拟阵的交，有着一个优美的多项式算法。由于这个算法证明及相关理论复杂，这里暂不展开证明，直接给出算法步骤：
        初始化答案集合$A=\varnothing$。然后构造图$G(V,E)$，这里$V=S$，$E$的定义如下：

  • 对于$x\in A,y\in S-A$，若$(A-\{x\})\cup\{y\}\in I_1$，则$< x, y >\in E$。
  • 对于$x\in A,y\in S-A$，若$(A-\{x\})\cup\{y\}\in I_2$，则$< y, x >\in E$。

        这个图叫做交换图，记为$D_M(A)$。
        构造$X_1=\{x\not \in A|A\cup\{x\}\in I_1\}$，$X_2=\{x\not \in A|A\cup\{x\}\in I_2\}$，然后在交换图上求$X_1$到$X_2$的最短路径$P$，更新$A$为$(A\cup P)-(A\cap P)$。重复上面的步骤，直到$P=\varnothing$。
        该算法的时间复杂度为$O(r^2n)$，其中$r$是两个拟阵秩的较大者，$n$为$|S|$。在某种程度上可以认为是$O(n^3)$。