拟阵与拟阵交学习笔记

九月 27, 2019 · OI 算法

本文以矩阵交相关内容为主，忽略掉了大部分证明，感兴趣的读者请自行阅读集训队论文。

拟阵的定义

记 $M = (S, L)$ 表示一个定义在有限集 $S$ 上，独立集的集合为 $L$ 的拟阵。其中 $L$ 是 $S$ 的一些子集构成的集合。拟阵 $M$ 满足以下公理：

(遗传性). 如果 $I \in L, J \subseteq I$，那么 $J \in L$。
(交换性). 如果 $I,J \in L$ 且 $|I| < |J|$，那么 $\exists x \in J \setminus I$ 满足 $I \cup \{x\} \in L$。

如果 $I \in L$，我们称 $I$ 是独立的，也称 $I$ 是独立集；否则，我们称 $I$ 是不独立的，也成 $I$ 是非独立集。通常，我们认为 $\varnothing$ 是独立的。

图拟阵

对于一个无向图 $G = (V, E)$，我们可以定义拟阵 $M = (E, L), L = \{F \in E | F \text{无环}\}$。

一般的有向图无法对应到一个拟阵上。

拟阵的基和环

对于拟阵 $M = (S,L)$ 中的一个独立集 $I$，如果 $I$ 加入任何一个属于 $S \setminus I$ 的元素都会变成非独立集，则称 $I$ 是拟阵的一个基，也叫极大独立集。

对于拟阵 $M = (S,I)$ 中的一个非独立集 $I’$，如果 $I’$ 去掉任何一个属于 $I’$ 的元素都会变成独立集，则称 $I’$ 是拟阵的一个环，也叫极小非独立集。

一个图拟阵中，一个基就是图的一个极大生成森林，一个环是一个简单环。特别的，如果这个图联通，那么一个基就是一个生成树。

基的性质

对于任意拟阵 $M$，所有基的大小相同。
(基交换定理). 对于任意拟阵 $M$，如果存在两个不同的基 $A, B$，那么对于任意一个 $z \in A\setminus B$，都存在一个 $y \in B\setminus A$，满足 $A − \{z\} + \{y\}$ 是独立集。

环的性质

令 $C(M)$ 表示拟阵 $M$ 的所有环。

如果存在环 $X, Y \in C(M)$，且 $X \subseteq Y$，那么 $X = Y$ 。
如果存在环 $X, Y \in C(M), e \in X ∩ Y$，且 $X \neq Y$ 。那么存在环 $C \in C(M)$ 满足 $C ⊆ X ∪ Y − \{e\}$ 。
令 $I$ 是拟阵 $M = (S, I)$ 的一个基，$e \notin I$ 。那么 $I + e$ 包含一个唯一的环。

秩函数

对于拟阵 $M = (S, I)$，基的元素的个数称为拟阵的秩，对于任意一个 $S$ 的子集 $U$，定义秩函数 $r(U)$ 表示 $U$ 中极大独立集的大小。

秩函数拥有如下几种性质。

(有界性). $∀U ⊆ S, 0 ≤ r(U) ≤ |U|$；
(单调性). $∀A ⊆ B ⊆ S, r(A) ≤ r(B)$；
(次模性). $∀A, B ⊆ S, r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B)$。

对偶拟阵

对于拟阵 $M = (S, I)$，定义 $M$ 的对偶拟阵 $M^∗ = (S, I^∗)$，其中 $I^∗ = \{I : \text{存在}M\text{中的基} B ⊆ S \setminus I \}$。

一个拟阵的对偶一定还是一个拟阵可以用拟阵的秩函数相关知识证明，此处略过。

拟阵交

给定两个定义在相同基础集上的拟阵 $M_1 = (S, L_1), M_2 = (S, L_2)$，定义 $M_1$ 和 $M_2$ 的交是所有的集合 $L$，满足 $L$ 同时在两个拟阵内都是独立的。

注意到两个拟阵的交不一定是一个拟阵，故不可以通过朴素的贪心解决。

最小最大定理

$\max_{I \in L_{1} \cap L_{2}} |I| = \min_{U \subseteq S}\left(r_{1}(U)+r_{2}(S \setminus U)\right)$

其一个方面是易证的：即

$|I| = |I \cap U| + |I \cap (S \setminus U)| \leq r_1(U) + r_2(S \setminus U)$

另一个方面可以通过矩阵的交算法证明。

另外，这个算法也为增量法求解矩阵的交提供了依据。

算法流程

令初始解 $I$ 为空集，即没有边被删除。
每条边作为有向图中的一个点，并新建源点 $S$ 和汇点 $T$。
对于 $x \notin I$ 的某条边 $x$，将 $x$ 的点权设置为 $w_x$，表示额外删掉这条边的代价。若 $I ∪ x$ 满足 $M_1$，则连边 $S \rightarrow x$；若 $I ∪ x$ 满足 $M_2$，则连边 $x \rightarrow T$。
对于 $x \in I$ 的某条边 $x$，将 $x$ 的点权设置为 $−w_x$，表示取消删除这条边的代价。
对于 $x \in I$ 的某条边 $x$ 以及 $y \notin I$ 的某条边 $y$，若 $I - \{x\} + \{y\}$ 满足 $M_1$ ，则连边 $x \rightarrow y$；若 $I - \{x\} + \{y\}$ 满足 $M_2$，则连边 $y \rightarrow x$。
在构造出来的图中 SPFA 找到 $S$ 到 $T$ 的最长路作为增广路，将上面每条边的选择情况取反，得到新的解 $I’$，此时 $I’$ 的大小比 $I$ 刚好大 1。不断重复构图找增广路直至 $I$ 的大小满足要求。