[知识点] 拟阵交

本文适合试图读 yql 论文然后 zbl 的选手,主要内容就是把 yql 论文中从强基交换定理到拟阵交的部分用人话 (我能直接理解的语言) 描述了一遍,对前面的内容不作描述,直接当做定理来使用。

为了方便理解,我们用线性拟阵来作类比 (这样会比用图拟阵类比方便很多)。

强基交换定理

定理 1 (强基交换定理) 对于拟阵 \(M\),如果存在两个不同的基 \(A,B\),那么对于任意一个 \(x \in A \setminus B\),都存在一个元素 \(y \in B \setminus A\),满足 \(A - \{x\} + \{y\}\)\(B - \{y\} + \{x\}\) 都是拟阵的基。

我们先考虑在一个线性拟阵中证明这个命题。

线性拟阵中强基交换定理的证明 由于 \(B\) 是一组基,\(B + x\) 包含一个唯一的环 \(C\)。在线性拟阵中,环满足任意元素都可以被其他元素线性表出。对于 \(C\) 中的任意一个元素 \(z \neq x\)\(z\) 可以被 \(C - \{z\}\) 线性表出,而 \(C- \{z\} \subseteq B + \{x\} - \{z\}\),所以 \(z\) 可以被 \(B + \{x\} - \{z\}\) 线性表出,从而 \(r(B+\{x\}-\{ z \} ) = r(B + \{x\}) \ge r(B)\),因为 \(B\) 是一组基,\(\lvert B + \{x\} - \{z\} \rvert = \lvert B \rvert\),所以 \(B + \{x\} - \{z\}\) 是一组基。我们只需证明 \(C - \{x\}\) 中存在一个元素 \(z\) 不能被 \(A - \{x\}\) 线性表出即可。假设 \(C - \{x\}\) 中所有元素都可以被 \(A - \{x\}\) 线性表出,那么 \(x\) 也可以被 \(A - \{x\}\) 线性表出 (因为 \(x\) 可以被 \(C - \{x\}\) 线性表出),这与 \(A\) 是独立集矛盾。所以一定存在一个 \(y \in C - \{x\}\) 使得 \(A - \{x\} + \{y\}\)\(B - \{y\} + \{x\}\) 都是拟阵的基。

接下来试着把这个证明推广到拟阵上。可以想到,如果要在拟阵上用上述思路证明这个命题,关键是要引入一个类似线性表出的概念。

定义 1 对于拟阵 \(M=(S, \mathcal I)\)\(A \subseteq S\),我们定义 \(A\) 的闭包算子 \(cl(A)=\{e \in S: r(A \cup\{e\})=r(A)\}\)

有了这一概念,在线性拟阵上,\(x\) 可以被 \(A\) 线性表出可以对应为 \(x \in cl(A)\)\(cl(A)\) 等价于向量组 \(A\) 张成的子空间。

引理 1 对于拟阵 \(M = (S, \mathcal I)\),如果 \(A \subseteq B\),那么 \(cl(A) \subseteq cl(B)\)

在线性拟阵上,引理 1 等价于,如果 \(A \subseteq B\),若 \(x\) 能被 \(A\) 线性表出,则 \(x\) 也能被 \(B\) 线性表出,这一命题是显然的。现在我们在一般的拟阵上用秩函数的性质证明这个命题,这大概是本文中唯一一个技巧性较强的证明,可以当做结论记下来。

引理 1 的证明 假设 \(e \in cl(A)\),若 \(e \in A\),显然有 \(e \in cl(B)\),否则

\[r(A \cup \{e\}) + r(B) \ge r((A\cup \{e\}) \cap B) + r(B \cup \{e\}) \ge r(A) + r(B \cup \{e\})\]

左右消去 \(r(A \cup \{e\})\)\(r(A)\) 得到 \(r(B) \ge r(B \cup \{e\})\),即 \(r(B) = r(B\cup \{e\})\),所以 \(e \in cl(B)\)。因此 \(cl(A) \subseteq cl(B)\)

引理 2 对于拟阵 \(M = (S, \mathcal I)\)\(A \subseteq S\),如果 \(e \in cl(A)\),那么 \(cl(A) = cl(A \cup \{e\})\)

在线性拟阵上,这等价于如果 \(e\) 能被 \(A\) 线性表出,那么 \(A\)\(A \cup \{e\}\) 张成的子空间相同。

引理 2 的证明 因为 \(A \subseteq cl(A)\),由 引理 1 可以得到 \(cl(A) \subseteq cl(cl(A))\)。假设 \(f \in cl(cl(A))\),则 \(r(A) = r(A+\{e\}) = r(A+\{e\}+\{f\})\),又因为 \(r(A) \le r(A +\{f\}) \le r(A + \{e\} + \{f\})\),所以 \(r(A+\{f\}) = r(A)\),即 \(f \in cl(A)\)。这就证明了 \(cl(cl(A)) \subseteq cl(A)\),所以 \(cl(A) = cl(cl(A))\)

引理 3 对于拟阵 \(M = (S, \mathcal I)\)\(A \subseteq S\)\(cl(A) = cl(cl(A))\)

这是 引理 2 的一个简单推论,证明就不详细写出了。

现在,我们用已经证明的引理替换只存在于线性拟阵中的概念和结论,给出强基交换定理在一般拟阵上的证明。(可以考虑对比着在线性拟阵上的证明阅读)

强基交换定理的证明 由于 \(B\) 是一组基,\(B + x\) 包含一个唯一的环 \(C\)。对于 \(C\) 中的任意一个元素 \(z \neq x\),有 \(z \in cl(C - \{z\})\),而 \(C- \{z\} \subseteq B + \{x\} - \{z\}\),由 引理 1 得到 \(z \in cl(B + \{x\} - \{z\})\),从而 \(r(B+\{x\}-\{ z \} ) = r(B + \{x\}) \ge r(B)\),因为 \(B\) 是一组基,\(\lvert B + \{x\} - \{z\} \rvert = \lvert B \rvert\),所以 \(B + \{x\} - \{z\}\) 是一组基。我们只需证明 \(C - \{x\}\) 中存在一个元素 \(z \not \in cl(A - \{x\})\) 即可。假设 \(C - \{x\} \subseteq cl(A - \{x\})\),由 引理 1 可以得到 \(cl(C - \{x\}) \subseteq cl(cl(A - \{x\})\),由 引理 3 得到 \(cl(C - \{x\}) \subseteq cl(A - \{x\})\)。因为 \(C\) 是环,由定义可得 \(x \in cl(C - \{x\})\),所以 \(x \in cl(A - \{x\})\),这与 \(A\) 是独立集矛盾。所以一定存在一个 \(y \in C - \{x\}\) 使得 \(A - \{x\} + \{y\}\)\(B - \{y\} + \{x\}\) 都是拟阵的基。

拟阵交

定义 2 给定两个定义在相同基础集上的拟阵 \(M_1 = (S, \mathcal I_1), M_2 = (S, \mathcal I_2)\),定义 \(M_1\)\(M_2\) 的交是所有的集合 \(I\),满足 \(I\) 同时在两个拟阵内都是独立的。

拟阵交问题要求的就是同属于两个拟阵的独立集中的最大的独立集。

我们的目标是要证明以下定理并给出构造:

定理 2 (最大最小定理) \(\max_{I \in \mathcal I_1 \cap \mathcal I_2} \lvert I \rvert = \min_{U \subseteq S} (r_1(U) + r_2(S \setminus U))\)

显然 \(\max_{I \in \mathcal I_1 \cap \mathcal I_2} \lvert I \rvert \le \min_{U \subseteq S} (r_1(U) + r_2(S \setminus U))\),我们只需找到任意一组能取到等号的 \(I\)\(U\) 就证明了这个命题,且 \(I\) 就是同属于两个拟阵独立集的最大独立集。

由于论文中这一段内容写得比较容易理解了,我抄一遍也没什么意义,所以下面只记录 (抄) 一下需要用到的定义、定理和构造算法 (自己复习用),引理的证明就不写了。

基本上抄论文的内容 (点击展开)

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

引理 4\(I\)\(J\) 都是拟阵 \(M\) 的独立集,且 \(|I|=|J|\),那么在 \(D_{M}(I)\) 中存在一个关于 \(I \setminus J\)\(J \setminus I\) 的完美匹配。

定理 3\(I\) 是拟阵 \(M\) 的独立集, \(J\) 是一个大小与 \(I\) 相同的集合。如果在二分图 \(D_{M}(I)\) 中存在一个唯一的 \(I \setminus J\)\(J \setminus I\) 的完美匹配,那么 \(J\) 也是独立集。

定义 4 给定两个拟阵 \(M_{1}, M_{2}\) 和一个集合 \(I \in \mathcal{I}_{1} \cap \mathcal{I}_{2}\), 定义关于 \(I\) 的交换图 \(D_{M_{1}, M_{2}}(I)\) 是这样一个二分图。它的两部分点集各自由 \(I\)\(S \setminus I\) 构成,一条从 \(y \in I\) 指向 \(x \in S \setminus I\) 的有向边存在,当且仅当 \(I-\{y\}+\{x\} \in \mathcal I_{1}\),一条从 \(x \in S \setminus I\) 指向 \(y \in I\) 的有向边存在,当且仅当 \(I-\{y\}+\{x\} \in \mathcal{I}_{2}\)

为了方便描述,我们定义这个二分图的左部为 \(I\),右部为 \(S\setminus I\)

令初始的 \(I\)\(\varnothing\),定义 \(X_1 = \{x \not \in I \mid I + \{x\} \in \mathcal I_1\}, X_2 = \{x \not \in I \mid I + \{x\} \in \mathcal I_2\}\) (注意 \(X_1,X_2\) 中的点都在右部)。如果交换图 \(D_{M_1,M_2}\) 中的从 \(X_1\) 中点出发到 \(X_2\) 中点的路径,找到一条 \(X_1\)\(X_2\)最短路,设这条路径为 \(P\),把 \(I\) 变为 \(I \Delta P\),其中 \(\Delta\) 为对称差,重复这一过程直到找不到路径为止,此时 \(I\) 就是一个最大的同时是两个拟阵独立集的集合。注意,如果 \(X \cap Y \neq \varnothing\),这个算法会直接增广一条长度为 \(0\) 的路径。

下面来验证这个算法的正确性。

首先,我们验证如果 \(I \in \mathcal I_1 \cap \mathcal I_2\),那么 \(I \Delta P \in \mathcal I_1 \cap \mathcal I_2\)

\(P\) 中的左部到右部的边和右部到左部的边分别构成了 \(M_1\)\(M_2\) 的交换图上的一个包含 \(P \cap I\) 的匹配。比如在下面的例子中,红边和绿边分别构成匹配。

例图
例图

\(P\) 的起点为 \(s \in X_1\),终点为 \(t \in X_2\),则 \(P\) 中左部到右部的边构成了 \(M_1\) 的交换图上 \(I \cap P\)\(P \setminus (I \cup \{s\})\) 的一个完美匹配,且这也是这两个点集在 \(M_1\) 的交换图上唯一的完美匹配(因为它们之间不存在其他边,否则与最短路矛盾)。由 引理 3 可得,\((I \Delta P) \setminus \{s\} \in \mathcal I_1\)。由于 \(P\) 是一条最短路,\(\forall x \in P \setminus (I \cup \{s\}),\ x \not \in X_1\),即 \(x \in cl(I)\)。所以 \(P \setminus (I \cup \{s\}) \subseteq cl(I)\),与之前类似地应用 引理 1引理 3 可得 \(cl(P \setminus (I \cup \{s\})) \subseteq cl(I)\),再应用 引理 2 可得 \(cl((P \setminus (I \cup \{s\})) \cup I) = cl(I \cup (P \setminus \{s\})) \subseteq cl(I)\),又因为 \(s \not \in cl(I)\),所以 \(s \not \in cl((I \Delta P) \setminus \{s\})\)。这就证明了 \(I \Delta P \in \mathcal I_1\)。类似地也可以证明 \(I \Delta P \in \mathcal I_2\)

接下来验证当找不到增广路时,\(I\) 是最大的同时是两个拟阵的独立集的集合。我们只需找到一个集合 \(U\) 并验证此时 定理 2 成立即可。

\[ U = \{x \in S \mid \text{$x$ 在 $D_{M_1,M_2}(I)$ 上可以到达 $X_2$} \} \]

考虑分别证明 \(r_1(U) \le \lvert U \cap I\rvert\)\(r_2(S \setminus U) \le \lvert (S \setminus U) \cap I \rvert\),后者与前者是类似的,只写出前者。

假设 \(r_1(U) > \lvert U \cap I \rvert\),那么存在 \(x \in S \setminus I\) 使得 \((U \cap I) \cup \{x\} \in \mathcal I_1\),可以通过反复对 \(I\) 使用交换性得到一个包含 \((U \cap I) \cup \{x\}\) 的大小与 \(I\) 相同的 \(J \in \mathcal I_1\),且 \(J \setminus I = \{x\}\),设 \(y\in I \setminus J\),显然 \(y \not \in U\),则 \(J = I + \{x\} - \{y\}\),所以 \(y\)\(x\)\(D_{M_1,M_2}(i)\) 中有一条有向边,\(x \in U\),这与 \(U\) 的定义矛盾。所以 \(r_1(U) \le \lvert U \cap I \rvert\)

\(r = \max(r_1(S), r_2(S))\),这个算法的时间复杂度为 \(\mathcal O(r^2 n)\)。(边数为 \(rn\),因为左部总是只有至多 \(r\) 个点)

在带权问题中,只要给左部点带上负权,右部点带上正权,每次第一关键字为权值和,第二关键字为边数找最短路即可。(不会证) 注意这里对找到的独立集的大小没有限制。