拟阵

Published: by Creative Commons Licence

  • Tags:

拟阵基本概念

拟阵$M=(S,I)$,其中$S$是全集,而$I$是$S$的一个子集族。拟阵需要满足下面的三大公理:

  1. $\emptyset\in I$
  2. 如果$A\subset B$,且$B\in I$,则一定有$A\in I$
  3. 如果$A,B\in I$,有$|A|<|B|$,则一定存在一个元素$x\in B/A$,满足${ x }\cup A \in I$

$I$中的集合元素我们称之为独立集,而其余$S$的子集我们称为非独立集。我们称最大独立集为基。

对于$T\subseteq S$,我们记$r(T)$表示$T$中最大的独立集子集的大小,称为$T$的秩。$r(T)$满足下面的三个性质:

  1. $0\leq r(T)\leq |T|$
  2. 若$A\subseteq B$,则有$r(A)\leq r(B)$
  3. $r(A\cup B)+r(A\cap B)\leq r(A)+r(B)$

我们可以通过拟阵的性质推出秩函数的性质,反之亦然。换言之,如果我们在某个集合$S$上定义了所有满足上面三个性质的秩函数,则记$I={T|T\subseteq S\land r(T)=|T| }$,则$M=(S,I)$就是拟阵。

定义拟阵$M=(S,I)$的对偶拟阵为$M^*=(S,I^*)$,其中$I^*=\left{ X | r(S/X)=r(S) \right}$,很显然$M^*$也是一个拟阵。

对于拟阵$M_1=(S_1,I_1)$和拟阵$M_2=(S_2,I_2)$,$M=(S_1\cup S_2, I_1\times I_2)$也是一个拟阵,其中$I_2\times I_2$是迪卡尔积。

很多问题都可以建模成拟阵。

  • 颜色拟阵:给定$n$个元素,每个元素都有自己的颜色。一个集合是独立集当且仅当集合中所有元素的颜色不同。
  • 树拟阵:给定$n$个顶点和$m$条边,一个边集是独立集当且仅当集合中的边不形成任意环。
  • 线性基拟阵:给定$n$个向量,一个向量集合是独立集当且仅当集合中的所有向量线性无关。
  • 删边图拟阵:给定$n$个顶点和$m$条边,一个边集是独立集当且仅当删除这些边后图依旧保持连通。

最大独立集与最大权独立集

通过拟阵的第三条公理,可以得到一个寻找最大独立集的算法:

我们从维护一个空集$X$开始,之后依次不断尝试所有的元素$e$,如果$e$加入$X$不破坏$X$的独立性,则加入。

而对于最大权独立集,我们可以把所有元素按照权值从大到小排序后进行上面算法,可以保证最后得到的独立集在保证最大的前提下,权值最大。

两个算法都只需要执行多项式次判断某个集合是否是独立集,如果判断某个集合是否是独立集可以在多项式时间复杂度内实现,那么总的时间复杂度就是多项式的。

拟阵交的最大独立集和最大权独立集

给定两个拟阵$M_1=(S,I_1),M_2=(S,I_2)$,记$M_{1,2}=(S,I_1\cap I_2)$为$M_1$和$M_2$的拟阵交。两个拟阵的交不一定满足拟阵的第三条公理,当然也不能保证是一个拟阵。

一般对三个或更多拟阵的交求最大独立集是NP-hard的,因为哈密顿路径可以描述为三个拟阵的交。但是神奇的是对于两个拟阵的交我们有多项式时间复杂度的算法计算拟阵的最大独立集。

算法流程如下:

我们从维护一个空集$X$开始。

将集合$X$和$S/X$建立为二分图的顶点,同时加入额外的两个源点$s$和汇点$t$。对于$x\in X,y\in S/X$,如果$X-{x}+{y}$是$M_1$中的独立集,则从$x$到$y$连一条有向边,如果$X-{x}+{y}$是$M_2$中的独立集,则从$y$到$x$连一条有向边,如果$X+{y}$是$M_1$中的独立集,我们从$s$向$y$连一条有向边,如果$X+{y}$是$M_2$中的独立集,我们从$y$向$t$连一条有向边。

之后我们找到一条$s$到$t$的最短路径,很显然路径上的$S/X$中的顶点数目比$X$中顶点数目多$1$。之后我们将$s$和$t$从路径中删除,路径上剩下顶点组成的集合记做$P$,之后$X$与$P$取亦或(就是仅保留在$X$和$P$中总共出现一次的元素)的到新的$X$集合。

直到无法找到一条从$s$到$t$的有效路径,算法结束。这时候的到的$X$是拟阵交的最大独立集。

如果想要求最大独立集,则需要修改上面流程,为每个顶点赋予一个点权,其中$X$中的点权为它本身权重取负,而$S/X$中的点权为它本身的权重。可以保证图中没有负环,因此我们可以在图上跑SPFA算法即可。以路径总点权作为第一关键字,经过边数作为第二关键字,找最短路(点权最大,但是经过边数最少的路径)。

如果判断某个集合是否是独立集可以在多项式时间复杂度内实现,那么两个算法的时间复杂度就是多项式的。

很多问题都可以表述为拟阵交。

题目1:给定二分图要求找最大匹配和最大权匹配。

第一个拟阵要求左边每个顶点度数不超过$1$,第二个拟阵要求右边每个顶点度数不超过$1$(其实两个拟阵都是颜色拟阵),它们的交的最大独立集就是二分图最大匹配,而最大权独立集,就是二分图最大权匹配。

题目2:给定$n$个分组,每个分组有若干个整数,问是否有可能从每个分组中挑选一个整数,且挑选出来的所有数的任意子集的亦或和都非$0$,如果有找到一种方案。其中$1\leq n\leq 100$,且整数数量不超过$10000$。

提供一道题目

这个问题可以分解为两部分,第一部分为每个分组挑选最多一个数,第二部分为挑选出来的整数线性无关。我们可以将两部分都表述为拟阵,之后算拟阵交的最大独立集即可,时间复杂度为$O(64n(m+n))$。

题目3:给定$n$个分组,每个分组有若干条边,尝试每组选择一条边,构成一株生成树。

老规矩,分成颜色拟阵和图拟阵的交求解即可。提供一道题目

题目4:给定$n$个顶点和$m$条带权无向边,每条边的颜色为红蓝绿三色中的一种。要求对于所有$k=1,2,\ldots,m$,判断是否可能取其中一些边,满足删除所有红边或蓝边后图依旧连通。如果有解,则输出最少的费用,其中费用为所有选中的边的边权之和。

提供一道题目

红绿边为第一个删边拟阵,蓝绿边为第二个删边拟阵,我们要求的其实是计算拟阵交的最大权独立集的中间产物。时间复杂度为$O((nm)^2)$。

参考资料