拟阵学习笔记

拟阵学习总结

By Tuifei_oier

Part 1 定义

首先给出一些基本的定义：

一、子集系统

给定二元组 (M=(S,I))，若满足以下条件：

(S) 为一个有限集。
(I) 为一个元素为 (S) 的子集的有限非空集，空集属于 (I)。
(forall Ain I,Bsubseteq A) 满足 (Bin I)。

则称 (M) 为一个子集系统。
其中，第三条性质一般称为遗传性。
特别地，称 (I) 中元素为独立集。
称一个集合 (A) 为极大独立集，当且仅当 (forall x,Acup{x} otin I)，也称极大独立集为基。
定义秩函数 (r(U)) 为 (U) 中最大独立集的大小，事实上，通过秩函数的性质，我们可以反过来推导出原子集系统的性质，例如：证明其为一个拟阵。

二、拟阵

给定一个子集系统 (M=(S,L))，若满足：

(forall Ain L,Bin L,|A|<|B|,exist;xin B-A)，满足 (Acup{x}in L)。

则称 (M) 为一个拟阵。
其中，该性质一般称为交换性。

三、对偶拟阵

称 (M^*) 为 (M=(S,I)) 的对偶拟阵，即 (M^*=(S,I^*))，其中 (I^*={x:) 存在 (M) 中的一个极大独立集 (Asubseteq Sackslash x})。

以及，我们可以定义一系列拟阵的运算：

删除：对于 (M=(S,I),Zsubseteq S)，定义 (Mackslash Z) 为 (M) 删除子集 (Z) 的拟阵，即 (Mackslash Z=(Sackslash Z,I'))，其中 (I') 的定义与 (I) 类似，实质是把原来的 (S) 变为 (Sackslash Z)，其他的定义不变。
收缩：对于 (M=(S,I),Zsubseteq S)，定义 (M/Z) 为 (M) 关于子集 (Z) 收缩后的拟阵，即 (M/Z=(M^*ackslash Z)^*)，可以证明收缩的意义为 (M/Z) 的任意一个独立集并上 (Z) 中的任意一个独立集后仍然是原 (M) 中的一个独立集，可以利用秩函数来研究它。

事实上，这两个运算一般用于证明拟阵。

Part 2 性质

拟阵有一些优美的性质：

次模性：(r(Acup B)+r(Acap B)le r(A)+r(B))。
拟阵 (M=(S,I)) 中 (I) 中的所有极大独立集大小相等。

当然，并不止这些，它最适用于我们的性质将在下文提到。

一些经典的拟阵：

均匀拟阵 (U^k_n=(S,I))，其中 (|S|=n,I={xsubseteq S:|x|le k})，不难证明这是一个拟阵。
图拟阵：对于无向图 (G=(V,E))，令 (M=(E,I),I={xsubseteq E:x) 无环 (})，则 (M) 为拟阵，证明如下：
1. 遗传性证明显然；
2. 对于交换性，由 (|A|<|B|) 知 (A) 连成的连通块数量大于 (B)，因此一定存在一个 (A) 中不连通而 (B) 中连通的块，加入该边即可。
需要注意的是，对于有向图是不成立的。
匹配拟阵：对于无向图 (G=(V,E))，匹配拟阵 (M=(V,I),I={xsubseteq V:x) 中所有点可被至少一个匹配完全覆盖 (})，证明略去。
连通拟阵：对于无向图 (G=(V,E))，考虑删边角度，连通拟阵 (M=(E,I),I={x:) 删除 (x) 中边后图连通 (})，不难证明其为拟阵（类似图拟阵）。事实上，连通拟阵就是图拟阵的对偶拟阵。

Part 3 OI 应用

在 OI 中，拟阵目前有两种常用用法：

一、拟阵与贪心

对于拟阵 (M=(S,I))，给定一个函数 (w:S ightarrow N^*)，定义 (S) 一个子集的权值 (w(x)=sum_{ein x}w(e))，拟阵的最优化问题即找一个最大的 (w(x)) 满足 (xin I)。

如果可以证明一个组合优化问题本质是拟阵的最优化问题，就可以套用下面的贪心算法来求解：

将 (S) 中元素 (e) 按 (w(e)) 从大到小排序。
维护集合 (A)，初始为空集，依次考虑每个 (e)，如果 (Acup{e}in I)，则 (Agets Acup{e})，最后答案即为 (w(A))。

证明略过，读者自证（查资料）不难。

以下是一些可以被证明等价于拟阵最优化问题的问题：

最小/大生成树。
二分图匹配。

只要构造出拟阵，问题就可以被大大简化了。

二、拟阵交

首先定义拟阵交。

对于两个拟阵 (M_1=(S,I_1),M_2=(S,I_2))，称集合 (A={x:xin I_1) 且 (xin I_2}) 为拟阵 (M_1,M_2) 的交。
此时，我们就有两种最优化问题：

求 (A) 中的最大独立集。
定义函数 (w:S ightarrow N^*)，求 (A) 中权值最大的独立集的权值。

对于两种问题，我们有一个相同的算法来求解，先介绍求 (A) 种最大独立集的算法。

初始有一个集合 (A=emptyset)。
每次将属于 (A) 的元素放在左部点，将属于 (Sackslash A) 的元素放在右部点，同时新建起点 (s) 和终点 (t)，按以下方式连边：

a. 对于右部点 (y)，如果满足 (Acup{y}in I_1)，由 (s) 向 (y) 连边；如果满足 (Acup{y}in I_2)，由 (y) 向 (t) 连边。

b. 对于左部点 (x) 和右部点 (y)，如果满足 (Aackslash{x}cup{y}in I_2)，由 (y) 向 (x) 连边；如果满足 (Aackslash{x}cup{y}in I_1)，由 (x) 向 (y) 连边。
之后，每次找一条从 (s) 到 (t) 的最短路，将该路径上原本属于 (A) 的元素从 (A) 中删除，不属于 (A) 的元素加入 (A)（称该操作为增广），然后重新建图，直至不存在最短路。
此时 (A) 即为拟阵交中的一个最大独立集。

算法的正确性在此略去证明，大致可以发现每次增广后 (|A|) 恰好 (+1)。
设 (r=max(r_1(S),r_2(S)),n=|S|)，则增广次数不超过 (r)，每次增广的复杂度为 (O(rn))，于是复杂度为 (O(r^2n))。

对于第二个问题，我们使用与上文类似的算法：每个节点赋点权，左部点的权值为 (-w(e))，右部点的权值为 (w(e))，然后将找 (s) 到 (t) 的最短路改为找 (s) 到 (t) 的最大点权路径，在此基础上尽可能短即可，此时由于存在负点权，使用 spfa，时间复杂度为 (O(r^2n^2))（当然也可以是 (O(r^2nk))，虽然但是，(k=n)）。
事实上可以证明，每次增广后的 (A) 都是大小为 (|A|) 时的一个最优解。

Part 4 例题

Pro A Rainbow Graph

给定一张 (n) 个点 (m) 条边的无向图，每条边有三种颜色 R,G,B 之一，同时带有边权 (w_i)，选择恰好 (k) 条边使得分别保留选出边中颜色为 R,G 的边和颜色为 G,B 的边时，都使得所有点连通，同时选出的 (k) 条边的边权和最小，对于 ([1,m]) 每一个 (k) 求出最小权值和。

(tips:1le n,mle100,1le w_ile1000)。

Pro B Colorful Graph

给定一张 (n) 个点 (m) 条边的无向图，每条边有两个属性：(w_i) 表示边权，(c_i) 表示颜色。
选出一个边集，满足：

该边集连通所有点；
每种颜色在边集中至少出现一次；

求最小的边集权值和。

(tips:1le nle mle200,1le c_ile m,1le w_ile10^9)。

Pro C 二分图匹配

给定二分图 (G=(V,E))，其中 (V=V_1+V_2)，求最大匹配。

Part 5 例题题解

Pro A

设 R,G,B 颜色边集分别为 (E_R,E_G,E_B)，则构造连通拟阵 (M_1=(E_R+E_G,I),M_2=(E_G+E_B,I))，然后带权拟阵交即可，由于每次增广后当前 (A) 都是大小为 (|A|) 时的一个最优解，直接将当前的 (w(A)) 作为 (Ans_{m-|A|}) 即可。

时间复杂度 (O(r^2n^2))。

Pro B

构造拟阵 (M_1) 为连通拟阵，(M_2=(E,I),I={x:) 每种颜色在 (x) 中都没有全部出现 (})，则直接求带权拟阵交即可。

Pro C

考虑构造 (M_1={E,I_1},I_1={x:V_1) 中所有点在图 ((V,x)) 中度数 (le1})，类似定义 (M_2)，然后最大拟阵交即可。

Part 6 后记

咕了。