Copyright Quack.

拟阵?type=header

拟阵的定义与常见性质 & 拟阵交算法

拟阵的定义与常见性质

独立集系统和拟阵

定义独立集系统$S=(E，\mathcal{I})$，$E$是基本元素的集合，$\mathcal{I} \subseteq 2^{E}$，$\mathcal{I}$中的元素称为独立集。

$\mathcal{I}$需要满足遗传性：如果$A \in \mathcal{I}，B \subseteq A$，那么$B \in \mathcal{I}$。

举例：

定义在无向图$G(V，E)$上的独立集系统，$\mathcal{I}$是不构成环的边集合，显然满足遗传性。

求无向图的最大生成树，实际上是先给$E$中每个元素赋予一个权值(边权)，然后求一个权值最大的独立集。

回忆一下kruskal算法，每次选一条边权最大的边，如果把它加入答案不形成环，就把它加入答案。

推广一下，给定任意独立系统，任意给每个元素一个非负的权值，要求权值最大的独立集，容易得到下面的贪心算法:

1. 将元素按权值从大到小排序。
2. 按顺序依次考虑每个元素，如果把这个元素加入答案后仍然是一个独立集，就加入答案。

不幸的是，这个算法只有在特定条件下才会给出最优解。

比如考虑求二分图图的最大权值匹配，定义独立集为可以形成匹配的边集。考虑一个4个点3条边的图$V=\{u\_1, u\_2, u\_3, u\_4\}, w(u\_1,u\_2)=w(u\_3, u\_4)=5, w(u\_1, u\_4)=8, w(u\_2, u\_3) = 1$，贪心算法会选择边$(u\_1, u\_4), (u\_2, u\_3)$，权值是9，最优解是$(u\_1, u\_2), (u\_3,u\_4)$，权值是10。

我们把贪心算法能够使用的独立集系统称为拟阵(matroid)，比如上面定义在无向图边集上的独立集系统(一个边集是独立集当且仅当不包含环)，贪心算法实际上就是kruskal算法，为了方便，给它一个名字叫图拟阵(graphic matroid)。

特别地，很多问题只要求取一个最大的独立集，即元素权重都是单位1的特殊情况，如果这个独立集系统是拟阵，我们称这种拟阵叫做unweighted matroid。

拟阵的性质

那么如何判定一个独立集系统$M$是不是拟阵呢？下面三条定义是等价的:

1. $M$是拟阵，任意给元素分配非负的权值，贪心算法能得到最优解。
2. 假设有2个独立集$I\_1, I\_2, |I\_2| = |I\_1|+1$，那么$\exists e \in I_1 - I_2, I_1 \cup e \in \mathcal{I}$。 通俗地讲，就是如果2个独立集大小相差1，那么一定可以从大的独立集那里拿一个给小的，使新的集合还是独立集。
3. 若$A \subseteq E$，$I\_1, I\_2 \subseteq A$是$A$上的极大独立集，那么$|I\_1|=|I\_2|$。也就是$E$的任意子集上的极大独立集大小相同。

接下来引入几个概念:

1. 秩(Rank)：根据上面第3条，$E$的任意子集$A$上的极大独立集大小相等。这个大小就是$A$的秩，记为$r(A)$。
2. 基(Basis)：$A$的基上的任意极大独立集称为$A$的基。
3. 回路(Circuit)：极小的非独立集（相关集），即它本身不是独立集，但删掉任意一个元素后都是独立集。

为了方便理解，我们以图拟阵为例子.
图拟阵中任意边集$A \subseteq E$，$r(A)$是其生成子图的生成森林边数, 基就是任意生成森林，回路就是一个简单环。

再看一个独立集系统，它的元素集合是一些维数相同的向量，独立集的定义就是线性无关的向量集合。根据线性代数的知识，任意向量集合的极大线性无关组大小相同，即满足上面的判断独立集是否是拟阵的第3条，所以该独立集系统是一个拟阵，之后我们称它为线性拟阵。
线性拟阵的秩，基都和线性代数中吻合，回路就是极小的线性相关组。

为了后面证明的方便，再引入一个概念：

4. 闭包(closure)：$cl(A)=\lbrace e|r(A+e)=r(A)\rbrace$。

闭包的性质：若$e \in cl(A)$，则$cl(A) = cl(A+e)$，也就是说，$cl(A)=cl(cl(A))$。

拟阵交

问题定义

有两个拟阵$M\_1=(E,\mathcal{I}\_1),M\_2=(E,\mathcal{I}\_2)$，求$I \in \mathcal{I}\_1 \cap \mathcal{I}\_2$且使得$|I|$尽量大。

注意这里的$\mathcal{I}\_1,\mathcal{I}\_2$是“集合的集合”，$I$是“集合”。

算法感性认识

类比二分图最大匹配

许多时候，一个组合优化问题并不能表示成一个拟阵，但是却可以表示成两个拟阵甚至更多拟阵的交。比如二分图匹配，之前我们已经举了一个反例说明它虽然是个独立集系统，但并不是一个拟阵。然而，我们可以把它表示成两个拟阵的交:

我们用$G(L,R,E)$表示一个二分图，$L,R$分别是两边的顶点集合，$E$是边集，也是拟阵的基本元素集合。

定义拟阵$M\_1=(E,\mathcal{I}\_1)$: 边集$A \in \mathcal{I}\_1$ 当且仅当$A$中边的左端点互不相同。

定义拟阵$M\_2=(E,\mathcal{I}\_2)$: 边集$A \in \mathcal{I}\_2$ 当且仅当$A$中边的右端点互不相同。

$M\_1,M\_2$是拟阵这一点可以自行验证。那么$I \in \mathcal{I}\_1 \cap \mathcal{I}\_2$且$|I|$尽量大的$I$就是二分图的一组最大匹配。

然后回忆匈牙利算法的过程，实际上就是找增广路。假设我们是从左边的点出发找到了增广路，设这条路的边为$e\_1,e\_2,\cdots,e\_{2k},e\_{2k+1}$（下标为偶数的边是之前的一些匹配边），之前的整个匹配边集为$I$，那么$I+e\_1-e\_2+\cdots-e\_{2k}+e\_{2k+1}$是新的一个匹配边集。

我们从拟阵的角度来看这个过程，$I+e\_1$仍然是拟阵$M\_1$的独立集，即$I+e\_1 \in \mathcal{I}\_1$。但多了一条边之后，右边的某个点就会和$2$条边相关，右边的独立性被破坏。所以又变成$I+e\_1-e\_2 \in \mathcal{I}\_2$，又让右边满足独立，而且是去掉一个元素，左边肯定还是独立。

最终$I+e\_1-e\_2+\cdots-e\_{2k}+e\_{2k+1}$在保持左边独立性的前提下让独立集大小增加1，而且右边也是独立的，于是就找到了一条增广路。

这个过程本质上是在奇数步尝试增加一个元素，并且保持$M\_1$的独立性，然而这可能会导致$M\_2$的独立性被破坏，所以在偶数步又去掉一个元素，使得重新满足$M\_2$中的独立性，直到在某个奇数步能找到一个元素，使得加上这个元素也不会破坏右边的独立性。我们也尝试把这种方法应用在一般的拟阵交问题上。

但是有一个问题，用上面的方法找增广路，在第$i$步找一个元素$e\_i$，它符不符合要求是和$e\_1,e\_2,\cdots,e\_{i-1}$的选择有关的，这样搜索空间就相当大了，所以我们需要把增广路的条件放宽一点，后面会证明放宽之后找到的解也一定是最优解。

考虑奇数步，原本的条件是$I+e\_1-e\_2+\cdots-e\_{2k}+e\_{2k+1} \in \mathcal{I}\_1$，但是这个条件太难了，我们放宽成$I-e\_{2k}+e\_{2k+1} \in \mathcal{I}_1$。同理偶数步放宽成$I-e\_{2k}+e\_{2k-1} \in \mathcal{I}_2$。

算法流程

有两个拟阵$M\_1=(E,\mathcal{I}\_1),M\_2=(E,\mathcal{I}\_2)$，求交。

设目前得到的答案集合$I$，初始时$I$为空集。显然$I$是$E$的子集。

对$E$中每个元素建一个点，属于$I$的元素为左部，不属于的为右部，建成二分图。再另建源点$S$和汇点$T$。

• 如果$e \in E - I, I + e \in \mathcal{I}_1$，连边$(S,e)$。
• 如果$e \in E - I, I + e \in \mathcal{I}_2$，连边$(e,T)$。
• 如果$e\_x \in I, e\_y \in E - I, I - e\_x + e\_y \in \mathcal{I}_1 $，连边$(e\_x,e\_y)$。
• 如果$e\_x \in I, e\_y \in E - I, I - e\_x + e\_y \in \mathcal{I}_2 $，连边$(e\_y,e\_x)$。

然后对这个图求$S$到$T$的最短路，把最短路中在集合$I$中的元素从集合$I$中去掉，把最短路中不在集合$I$中的元素（$S$和$T$除外）加入集合$I$，进行下一次建图。

易知每次$I$的大小会增加$1$，算法在$S$到$T$不连通时终止，此时$I$就是答案。

令$r=\max(r(M\_1),r(M\_2)),n=|E|$，我们每次构建出来的图都是$n$个点，$rn$条边的图。由于增广次数不超过$r$，时间复杂度$O(r^2n)$。

算法正确性证明

正确性证明分为两个方面：

• 证明对于每一步增广得到的$I$，$I \in \mathcal{I}_1 \cap \mathcal{I}_2$。
• 证明不能再增广的时候得到的是大小最大的$I$。

一方面

对于这个问题，我们的证明思路是，设增广路上的左部点是$x\_1,\cdots,x\_n$，右部点是$y\_1,\cdots,y\_n,y\_{n+1}$。我们想证明的是$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_1$且$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_2$。

先证$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_1$，由于$y\_1$这个点是直接和$S$相连的，满足$I + y\_1 \in \mathcal{I}_1$，我们只需要证$I$和$I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1}$具有相似的性质，以至于在$I + y\_1 \in \mathcal{I}_1$式中，可以直接把$I$替换为$I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1}$。

具体来说，可以先证$I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_1$。假设我们已经证明了，由于增广路是最短路，所以$I+y\_i \notin \mathcal{I}_1 (i \ge 2)$，所以$r(I)=|I|=r(I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1})=r(I+y\_2+\cdots+y\_n+y\_{n+1})$（第三个等号成立是由于两个集合的闭包相等），又因为$I + y\_1 \in \mathcal{I}_1$，那么沿用拟阵上最优化问题的思路，相当于集合里面的元素为$I + y\_1$，加进去不形成环就往里加，最终所有的元素都能加进去。现在集合里面的元素增加了，变成$I+y\_1+\cdots+y\_n+y\_{n+1}$，在排序的时候把$y\_i$排到$x\_i$前面，加进去不形成环就往里加，最终加进去的元素集合就是$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n+y\_{n+1}$。

所以说剩下就是如何证$I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_1$。

对拟阵$M=(E,\mathcal{I})$定义交换图$D\_M(I)(I \in \mathcal{I})$。交换图是一个二分图，左部是$I$，右部是$E-I$，如果对于$x \in I,y \in E-I$，有$I-x+y \in \mathcal{I}$，那么就连无向边$(x,y)$。我们证明一个辅助证明的定理：

设$I \in \mathcal{I}$，$J$是一个大小等于$I$的由$E$中元素组成的集合，如果在$D\_M(I)$中存在唯一一个$I-J$到$J-I$的完美匹配，则$J \in \mathcal{I}$。

令$N$为完美匹配，把$N$中的边重定向，从$E-I$连向$I$，其余边从$I$连向$E-I$。由于匹配是唯一的，那么图中不存在环，所以可以拓扑排序，即可以把所有点重标号，使得边都是从标号小的指向标号大的。又因为从右部连回左部的边只有匹配大小这么多条，且是一一对应的连边，所以在处理右部连回左部的边时，我们给右部和左部的点相同大小的标号，那么这个图就有一个关键性质：左部点连向的右部点满足右部点的标号都不小于左部点的标号。

接下来使用反证法，设$J$不是独立集，那么$J$中必定存在环$C$，设$y\_i$是环中标号最大（且为$i$）的右部元素，由于之前的构造，对于环中其他的右部元素$y$，其匹配点$x\_i$到$y$是没有边的。没有边就说明$I-x\_i+y \notin \mathcal{I}$，也就是说$y \in cl(I-x\_i)$，即$C-y\_i \subset cl(I-x\_i)$。

两边同时取闭包$cl(C-y\_i) \subset cl(I-x\_i)$，因为$C$是环，所以$y\_i \in cl(C-y\_i)$，所以$y\_i \in cl(I-x\_i)$，但是这和$(x\_i,y\_i)$是交换图的匹配边矛盾。这样我们就证明了这个定理。

证$I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_1$，只需让$J=I-x\_1-\cdots-x\_n+y\_2+\cdots+y\_n+y\_{n+1}$，那么由最短路可知匹配是完美且唯一的，这样就证出来了。

证明另外一边$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n+y\_{n+1} \in \mathcal{I}_2$也是一样的，容易想到是利用$I+y\_{n+1} \in \mathcal{I}_2$，然后证明$I$和$I-x\_1-\cdots-x\_n+y\_1+\cdots+y\_n$是差不多的东西。

另一部分

直接证Min-Max Formula。

$$\max\_{I \in \mathcal{I}}|I| = \min\_{U \subseteq E}{r\_1(U)+r\_2(E - U)}$$

首先容易证明$\forall I \in \mathcal{I}, \forall U \subseteq E, |I| \leq r\_1(U)+r\_2(E - U)$。

• 把$I$分成$A=I \cap U$和$B=I-A$两部分。
• $A \subseteq U, A \in \mathcal{I}\_1 \rightarrow r\_1(U) \geq |A|$
• $B \subseteq E - U, B \in \mathcal{I}\_2 \rightarrow r\_2(E - U) \geq |B|$

我们设$U$为交换图中可以到达$T$的点集。上面我们证了$r\_1(U) \geq |I \cap U|$。现在我们证$r\_1(U) \le |I \cap U|$。反证法，如果$r\_1(U) > |I \cap U|$，这就说明能到达$T$的点组成$M_1$的独立集的大小是要大于在交换图的左部且能到达$T$的点数，也就是说存在一个交换图中右部的点$y$，使得$I \cap U + y \in \mathcal{I}\_1$。有可能是$I + y \in \mathcal{I}\_1$，但这说明$S$要向$y$连边，而$y$又能到$T$，那么$S$和$T$依旧连通，矛盾。也有可能是存在一个$x \in I-U$，使得$I - x + y \in \mathcal{I}\_1$，但这说明$x$要向$y$连边，而$y$又能到$T$，那说明$x$也能到$T$，但$x \notin U$，也矛盾。对于$r\_2(E - U) \le |I - A|$的证明也类似，这里就不再重复。

综上，我们证明了算法结束的时候存在一个$U$，使得$|I|$能取到最大值，这就证明了算法的正确性。

推广

带权拟阵交

相当于每个元素有权值，求独立集的交，使得权值和最大。

依赖于拓展的Min-Max Formula。

实际的算法中，我们只要在交换图中定义点权，左部点（$x \in I$）的点权设为$-w(x)$，右部点（$y \in E-I$）的点权设为$w(y)$，求最短路的过程改为求一条从$S$到$T$的路径，第一关键字是点权最大，第二关键字是经过的边数最小即可。证明略。

多个拟阵交

由于拟阵的交不是拟阵，所以不能两两求交。可以把多个拟阵的交规约到哈密顿路问题上，从而证明多个拟阵的交是NP-hard的。证明略。

例题

二分图匹配

上面的分析就用的二分图匹配。这里略。

最小树形图

定义拟阵$M\_1=(E,\mathcal{I}\_1)$: 边集$A \in \mathcal{I}\_1$ 当且仅当$A$的边看作无向边时无环。

定义拟阵$M\_2=(E,\mathcal{I}\_2)$: 边集$A \in \mathcal{I}\_2$ 当且仅当$A$的边每个点入度不超过一，特别地根入度为零。

Colorful Tree

给定带权无向图 $G(V, E)$ ，每条边拥有一个 $1$ 到 $n−1$ 中的颜色，求一个权最大的生成树，满足每种颜色只出现一次。

定义拟阵$M\_1=(E,\mathcal{I}\_1)$: 边集$A \in \mathcal{I}\_1$ 当且仅当$A$的边无环。

定义拟阵$M\_2=(E,\mathcal{I}\_2)$: 边集$A \in \mathcal{I}\_2$ 当且仅当$A$的边每种颜色出现次数不超过一。