拟阵学习笔记（杂记）

拟阵基础

拟阵是一个二元组 $M = (U , I)$，其中 $U$ 是一个有限集合，一般是待研究元素全集，$I$ 是 $U$ 的一些子集的集合，一般是满足给到限制的子集的集合。

拟阵要满足两个性质：

遗传性：$\forall S \in I , T \subseteq S$ 满足 $T \in I$。
交换性：$\forall A \in I,B \in I,|A| < |B|$ 满足 $\exist x \in B , x \not \in A$ 使得 $A \bigcup \{x\} \in I$。

拟阵可以直接解决一类贪心：给定映射 $f : U \rightarrow R$，要在 $I$ 中找到一个 $S$ 使得 $\sum_{x \in S} f(x)$ 最大。

这类贪心实际上都可以将 $U$ 元素从大到小排序，依次加入当前集合，如果当前集合加上该元素过后还在 $I$ 内则添加。想想看，为什么对。

考虑这类做法有普适性的原因，因为我们可选集合都属于 $I$，而 $I$ 满足拟阵性质，我们尝试使用拟阵性质进行分析。

任意时刻，我们的当前集合都是属于 $I$ 的。

那么必然存在一个最优集合 $B$。

我们可以根据拟阵的交换性不断添加元素说明，最大的元素一定在 $B$ 中，类似地，我们可以说明最大的加上最大的可以并上去的集合也是 $B$ 的子集。

证毕！哇，我觉得这个交换性的性质巨强！

一个拟阵贪心的常见例子就是最小生成树的 Kruscal 算法。

例一：「BJWC 2011」元素

考虑构造其拟阵。显然全集就是所有元素。

不妨定义其 $I$ 为所有没有子集属性异或和为 $0$ 的集合。显然满足遗传性，那么交换性呢？

考虑两个集合 $A，B$ 满足 $|A| < |B|$，先把两个集合相交的部分做一个线性基 $S$，则我们依次考虑 $x \in B，x \not \in A$，如果不能加入 $A$ 则加入线性基 $S$，因为 $B$ 中元素线性无关，所以线性基大小会加一。在 $B$ 中元素被全部考虑之前，会有 $S = A$，因为 $S$ 的每一个元素都能被 $A$ 张成，因此剩下的元素均可以加入 $A$。

好厉害的拟阵！

例二：「CQOI 2013」新 Nim 游戏

？这不和上道题一模一样？

例三：

题意：给出 $n$ 个任务，每个任务有一个单位完成时间，截止时间 $d_i$ 和超时惩罚 $p_i$。同一时间只能做至多一个任务，最小化超时惩罚之和。

考虑去构造这样一个拟阵。令全集是所有任务，令集合 $I$ 表示所有能够被完全完成的任务集合。

分析其性质。显然满足遗传性。考虑交换性，设两个集合 $|A|<|B|$，考虑 $A$ 的最长被占满前缀，大小显然不超过 $|A|$，所以 $B$ 中一定存在可以加入 $A$ 的元素。证毕。

所以只用每次选择惩罚最大的任务去考虑能否完成即可。

补充

1. 基： 拟阵 $M = (S , I)$ 中的一个极大独立集。以下是一些基本性质：

因为交换性，对于一个拟阵 $M$，所有基的大小相同。

2. 环： 拟阵 $M = (S,I)$ 中的一个极小非独立集。不妨记 $C(M)$ 表示 $M$ 的所有的环，以下是一些基本性质：

如果存在环 $X,Y \in C(M)$，且 $X \subseteq Y$，那么 $X= Y$。
如果存在环 $X,Y \in C(M)$，$e \in X \cap Y$，且 $X \not = Y$。那么存在环 $C \in C(M)$ 满足 $C \subseteq X \cup Y - \{e\}$。
- 证明： 即证 $X \cup Y - \{e\}$ 不是独立集。设 $f \in X \backslash Y$，则 $X - \{f\}$ 是独立集，假设 $X \cup Y$ 中包含 $X - \{f\}$ 的最大独立集是 $Z$。由于 $Y$ 不是独立集，所以 $|Z| \leq |X \cup Y - \{f\}| - 1 < |X \cup Y - \{e\}|$。
令 $X$ 是拟阵 $M = (S,I)$ 的一个基，$e \not \in X$。那么 $X + e$ 包含一个唯一的环。
- 证明： 假设 $X+e$ 存在两个不同的环 $C_1,C_2$，由于 $e$ 的加入导致环的产生，所以 $e \in C_1 \cap C_2$，而 $C_1 \cup C_2 - \{e\}$ 包含环，这与 $X$ 是独立集矛盾。

3. 秩 rank： 秩函数 $r(S)$ 表示 $S$ 的最大独立子集的大小。以下是一些基本性质：

$r(S) \leq |S|$。
$S$ 的子集的秩不大于 $S$ 的秩。
次模性： $r(A) + r(B) \geq r(A \cup B) + r(A \cap B)$。

4. 闭包算子： 对于拟阵 $M = (S,I)$ 和 $A \subseteq S$，我们定义 $A$ 的闭包算子 $cl(A) = \{e \in S:r(A \cup \{e\}) = r(A) \}$。闭包算子有如下性质：

对于拟阵 $M = (S,I)$，如果 $A \subseteq B$，那么 $cl(A) \subseteq cl(B)$。
- 证明： 设 $e \in cl(A)$，由次模性可得：$r(A \cup \{e\}) + r(B) \geq r((A \cup \{e\}) \cap B) + r(B \cup \{e\}) = r(A) + r(B \cup \{e\})$。所以可得 $r(B) \geq r(B \cup \{e\})$，所以有 $r(B) = r(B \cup \{e\})$。证毕。
对于拟阵 $M = (S,I)$ 和 $A \subseteq S$，如果 $e \in cl(A)$，那么 $cl(A) = cl(A \cup \{e\})$。
- 证明： 首先易得 $cl(A) \subseteq cl(A \cup \{e\})$。所以我们只需要证明 $cl(A \cup \{e\}) \subseteq cl(A)$ 即可。然后类似之前的证明，利用次模性导一下式子即可。

5. 强基交换定理 Strong Basis Exchange Lemma： 对于任意一个元素 $x \in A \backslash B$，都存在一个元素 $y \in B \backslash A$，满足 $A - \{x\} + \{y\}$ 和 $B - \{y\} + \{x\}$ 都是拟阵的基。

证明： $B$ 是基，那么 $B + \{x\}$ 包含一个唯一的环 $C$，且 $x \in C$。所以 $x \in cl(C - {x}) $，由闭包算子定理可以得到 $x \in cl((A\cup C) - \{x\}) = cl(A \cup C)$。既然 $A$ 是基，那么 $S = cl(A) \subseteq cl(A \cup C)$，由此可以得到 $A \cup C - \{x\}$ 含有一个基，令它为 $A'$。所以一定存在元素 $y \in A' \backslash (A - \{x\})$ 使得 $A - \{x\} + \{y\}$ 是基。由于 $A' \backslash (A - \{x\}) \subseteq C - \{x\}$，所以也存在元素 $y \in C - \{x\}$，满足 $A - \{x\} + \{y\}$ 是基，另一方面由于 $C$ 是环，所以 $B - \{y\} + \{x\}$ 也是基。

拟阵交

即去求两个拟阵中都存在独立性的最大集合。

例子：

1. 找到一个生成树使得生成树每种颜色的边不超过一条。
2. 给定向量，找到最大的不同颜色的向量集合，使得他们线性无关。
3. 二分图匹配。这个解释一下，一个拟阵的限制是不共用左边顶点，一个是右边。
4. 哈密顿路问题。不共用起点，不共用终点，无环。但多个拟阵交是没有多项式时间复杂度的做法的。

定理 1（最大最小定理）： $\max\limits_{I \in \mathcal I_1 \cap \mathcal I_2} |I| = \min\limits_{U \subseteq S}(r_1(U) + r_2(S \backslash U))$。

这个定理是解决拟阵交问题的关键。先证明较简单的一面 $\max \leq \min$：

\[|I| = |I \cap U| + |I \cap (S \backslash U)| \leq r_1(U) + r_2(S \backslash U) \]

另一面我们在下面给出构造证明。

定义 1. 对于给定的拟阵 $M = (S,\mathcal I)$，和一个独立集 $I \in \mathcal I$，定义 $M$ 中 $I$ 的交换图 $D_M(I)$ 是这样一种二分图。它的两部分点集各自由 $I$ 和 $S \backslash I$ 构成，一条连接 $y \in I$ 和 $x \in S \backslash I$ 的边存在，当且仅当 $I - \{y\} + \{x\} \in \mathcal I$ 成立。

引理 1. 令 $I$ 和 $J$ 都是拟阵 $M$ 的独立集，且 $|I| = |J|$。那么在 $D_M(I)$ 中存在一个关于 $I \backslash J$ 和 $J \backslash I$ 的完美匹配。

证明： 带入强交换定理即可。

定理 2. 令 $I$ 是拟阵 $M$ 的独立集，$J$ 是一个大小与 $I$ 相同的集合。如果在二分图 $D_M(I)$ 中存在一个唯一的 $I \backslash J$ 到 $J \backslash I$ 的完美匹配，那么 $J$ 也是独立集。

感觉就很对，累了，不想证了。

定义 2. 给定两个拟阵 $M_1,M_2$，和一个集合 $I \in \mathcal I_1 \cap I_2$，定义关于 $I$ 的交换图 $D_{M_1,M_2}(I)$ 是这样一个二分图：它的两部分点集各自由 $I$ 和 $S \backslash I$ 构成，一条从 $y \in I$ 指向 $x \in S \backslash I$ 的有向边存在，当且仅当 $I - \{y\} + \{x\} \in \mathcal I_1$ ，一条从 $x \in S \backslash I$ 指向 $y \in I$ 的有向边存在，当且仅当 $I - \{y\} + \{x\} \in \mathcal I_2$。

算法流程：

令初始的 $I$ 为 $\phi$。我们定义集合 $X_1 = \{x \not \in I: I + \{x\} \in \mathcal I_1 \}$，$X_2 = \{x \not \in I:I + \{x\} \in \mathcal I_2 \}$。
算法将会每次在当前的交换图 $D_{M_1,M_2}$ 中找到一条从 $X_1$ 到 $X_2$ 的路径，满足没有任何一条边能够缩短这条路径的长度，令其为 $P$。这一步的意义其实就是尝试将 $I$ 扩展一步，先让其满足 $X_1$ 的限制，然后取反悔，找到一个两个限制都满足的位置。
然后我们令 $I$ 变为 $I \Delta P$（其中 $\Delta$ 表示对称差）。我们称这样的一次过程为一次增广过程，重复增广过程，直到找不到路径。我们就得到了最大的 $I$，并找到了 $U = \{z \in S : z \text{可以到达} X_2 \}$。

为了说明这个算法是正确的，我们需要说明是 $|I| = r_1(U) + r_2(S \backslash U)$，这样才可以保证我们求得的 $I$ 是最大的。

即，我们要证明 $r_1(U) \leq |I \cap U|$。如果 $r_1(U) > |I \cap U|$，那么存在元素 $x \in U \backslash I$ 使得 $(I \cap U) + \{x\} \in \mathcal I_1$。但如果 $I + \{x\}$ 也是 $M_1$ 的独立集的话，那么 $x \in X_1$，即存在一条从 $X_1$ 到 $X_2$ 的路径，所以 $I + \{x\}$ 不是 $M_1$ 的独立集。证毕。