拟阵

Published: by Creative Commons Licence

  • Tags:

拟阵基本概念

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

  1. ∅∈I
  2. 如果A⊂B，且B∈I，则一定有A∈I
  3. 如果A,B∈I，有|A|<|B|，则一定存在一个元素x∈B/A，满足{x}∪A∈I

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

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

  1. 0≤r(T)≤|T|
  2. 若A⊆B，则有r(A)≤r(B)
  3. r(A∪B)+r(A∩B)≤r(A)+r(B)

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

定义拟阵M=(S,I)的对偶拟阵为M∗=(S,I∗)，其中I∗={X|r(S/X)=r(S)}，很显然M∗也是一个拟阵。

对于拟阵M1=(S1,I1)和拟阵M2=(S2,I2)，M=(S1∪S2,I1×I2)也是一个拟阵，其中I1×I2是直积。

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

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

下面是一些拟阵的额外命题（这些定理的证明来自拟阵划分）：

定义1：设M=(E,I)为一拟阵，A⊆E，I⊆A且I∈I。设S=I∪{e∈A:I∪{e}∉I}，S被称为I在A中的闭包（对于拟阵M）。

引理一：对任何拟阵M=(E,I)，如果A⊆E并且I⊆A且I∈I，则I在A中的闭包S是{S⊆A:I⊆S,r(S)=|I|}中的极大集（唯一）。

引理二：考虑拟阵M=(E,I)上的I∈I和e∈E，I∪{e}至多包含M的一个圈。

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

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

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

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

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

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

给定两个拟阵M1=(S,I1),M2=(S,I2)，记M1,2=(S,I1∩I2)为M1和M2的拟阵交。两个拟阵的交不一定满足拟阵的第三条公理，当然也不能保证是一个拟阵。

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

算法流程如下：

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

将集合X和S/X建立为二分图的顶点，同时加入额外的两个源点s和汇点t。对于x∈X,y∈S/X，如果X−{x}+{y}是M1中的独立集，则从x到y连一条有向边，如果X−{x}+{y}是M2中的独立集，则从y到x连一条有向边，如果X+{y}是M1中的独立集，我们从s向y连一条有向边，如果X+{y}是M2中的独立集，我们从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≤n≤100，且整数数量不超过10000。

提供一道题目。

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

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

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

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

提供一道题目。

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

拟阵划分

拟阵划分是指将集合中的元素划分成最少的不想交的独立集。

定理一：存在互斥的Ii∈Ii，满足E=⋃ki=1Ii，当且仅当对任何A⊆E，

|A|≤k∑i=1ri(A)

特别地，如果这k个Ii是同一个I，则可以叙述为：E可以被表示为小于等于k个独立集的并，当且仅当对任何A⊆E，

|A|≤k⋅r(A)

下面拟阵划分的算法来自WIKI。

一开始我们创建一个单独的空独立集。之后我们重复下面流程：

  • 如果所有元素都已经被分配到某个独立集了，那么结束流程。
  • 否则我们建立一幅图，每个元素和独立集都对应一个顶点。如果某个元素i可以加入到独立集j中，使得独立性不被破坏，那么我们从独立集j向元素i连一条有向边。如果某个已分配的元素i，可以在其所属的独立集中通过元素j替换元素i而不失独立性，则从i向j连一条有向边。之后我们从所有独立集对应的顶点开始跑多源BFS。
    • 如果至少有一个未分配元素可达，那么找到距离最近的一个未分配元素，并沿着最短做对应的替换操作。操作完成后，未分配元素会减少1。距离最近非常重要，否则不能保证替换操作不会破坏独立性。
    • 如果所有未分配元素都不可达，就新增一个单独的空独立集。

提供一道题目。

再提供一道题目，需要利用双生成树求解一个欧拉环。

参考资料