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

拟阵

        有限拟阵是一个序偶$(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)$。