【学习笔记】拟阵

“拟阵是向量空间的 ‘线性无关’ 概念的推广。” —— 知乎网友

用 $⊊$ 表示 “不包含于”。

壹、定义

1.拟阵

拟阵（$\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{o}\mathrm{i}\mathrm{d}$）$\mathcal{M}=(\mathbb{U},\mathcal{I})$，其中 $\mathcal{I}$ 是 $\mathbb{U}$ 上的集族，满足

• 遗传性：对于 $I\in \mathcal{I},J\subseteq I$ 有 $J\in \mathcal{I}$ 。
• 基交换性 或 扩张性：对于 $I,J\in \mathcal{I},|I|<|J|$ 有 $\exists x\in J\setminus I$ 使得 $I\cup \{z\}\in \mathcal{I}$ 。

不妨规定 $|\mathcal{I}|\ne 0$，因此 $\varnothing \in \mathcal{I}$ 。

对于 $I\in \mathcal{I}$，称 $I$ 为 独立集，即 $I$ 是独立的。否则称 $I$ 为不独立的。

2.基与环

基（$\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}$）是极大独立集，环（$\mathrm{c}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{u}\mathrm{i}\mathrm{t}$）是极小非独立集。

Lemma 1. 矩阵中的所有基具有相同的大小。

Corollary 1. 对于不同的环 $X,Y$，若存在 $e\in X\cap Y$，则 $X+Y-\{e\}$ 是不独立的。

Proof. 显然存在 $f\in X\setminus Y$，设 $Z$ 为 $X\cup Y$ 中包含 $X\setminus \{f\}$ 的最大独立集，因 $Y⊊Z$ 得 $|Z|<|X+Y-\{f\}|=|X+Y-\{e\}|$，因为 $Z$ 是最大的，所以原命题得证。$■$

Corollary 2. 对于 $I\in \mathcal{I}$，若 $I\cup \{e\}\notin \mathcal{I}$ 则 $I\cup \{e\}$ 中有唯一的环。

Proof. 若存在两个环 $C_1,C_2$，显然 $e\in C_1\cap C_2$，由 $\text{corollary 1}$ 知 $C_1+C_2-\{e\}$ 不独立，与 $I$ 是独立集矛盾。$■$

3.秩函数

对于 $S\subseteq \mathbb{U}$，定义 秩（函数）$r(S)$ 为 $S$ 中极大独立集的大小。

• 有界性：$0⩽r(S)⩽|S|$ 。
• 单调性：$\forall A\subseteq B$ 有 $r(A)⩽r(B)$ 。
• 次模性（$\text{submodular}$，也称子模）：$r(A\cup B)+r(A\cap B)⩽r(A)+r(B)$ 。

Proof. 证明 $r(A\cup \{x\})-r(A)⩽r(B\cup \{x\})-r(B)$ 其中 $B\subseteq A$ 是平凡的。然后从 $*A,A\cap B*$ 开始，将 $B\setminus A$ 逐个加入 $A$ 则得到 $*A\cup B,A\cap B*$，加入 $A\cap B$ 则得到 $*A,B*$，在已经加入了 $S$ 时，前者在集合 $A+S$ 内增加，后者在 $(A\cap B)+S$ 内增加，更大。$■$

4.以秩定义

“我们将拟阵的组合问题转化为秩函数上的代数问题，通过研究秩函数的性质来求得拟阵的性质。”

依据满足上述三条性质的秩函数 $r:2^S\mapsto {\mathbb{N}}^{+}$，我们可以重新定义拟阵 $\mathcal{M}=(\mathbb{U},\mathcal{I})$，其中 $\mathcal{I}=\{I:r(I)=|I|\}$ 。

Proof. 遗传性：若 $r(B)=|B|,A\subseteq B$，由 次模性 知 $r(B)⩽r(A)+r(B\setminus A)$，由 有界性 知 $r(A)=|A|$ 。

交换性：反证法，设 $B=\{b_1,b_2,\dots ,b_{|B|}\}$，则 $r(A\cup \{b_i\})=|A|$ 。利用归纳法证明 $r(A\cup \{b_1,b_2,\dots ,b_n\})=|A|$ 。对 $n>1$，取 $X=A\cup \{b_1,b_2,\dots ,b_{n-1}\},Y=A\cup \{b_n\}$，由 次模性 有 $r(A\cup \{b_1,b_2,\dots ,b_n\})+r(A)⩽r(X)+r(Y)$，由 $r(A)=r(X)=r(Y)=|A|⩽r(A\cup \{b_1,b_2,\dots ,b_n\})$ 知归纳法成立。

然而 $r(B)=|B|>r(A\cup B)=|A|$ 违反了 单调性 。$■$

贰、线性拟阵和线性表出

“我们线性拟阵是你们图拟阵的老大哥！”

线性拟阵（$\text{linear matroid}$）即 $\mathbb{U}$ 为向量集合，而 $\mathcal{I}=\{I\in 2^{\mathbb{U}}:\dim (\text{span}(I))=|I|\}$ 的特殊拟阵。

线性表出（$\text{linear representation}$）即将 $\mathbb{U}$ 内每个元素映射到一个向量上，使得这些向量的线性拟阵得到的 $\mathcal{I}$ 就是原拟阵的独立集集族。

按：作为 $\mathrm{O}\mathrm{I}\mathrm{e}\mathrm{r}$ 我并不想去研究向量空间的基域，因此相关内容略写

若拟阵可以被线性表出，问题就变成线性拟阵上的了。

1.均匀拟阵

均匀拟阵（$\text{uniform matroid}$）为 $\mathcal{I}=\{I:|I|⩽k\}$ 。

它可以被线性表出为 $k$ 维向量 $v_i=(1,{\alpha }_i,{\alpha }_i^2,\dots ,{\alpha }_i^{k-1})$，其中 $\{{\alpha }_i\}$ 是两两相异的非零元：超过 $k$ 个肯定线性相关，但不超过 $k$ 个时，范德蒙德矩阵行列式为 ${\prod }_{i<j}({\alpha }_j-{\alpha }_i)\ne 0$，因此线性无关。

2.图拟阵

图拟阵（$\text{graph matroid}$）定义在无向图 $G=(V,E)$ 上，$\mathbb{U}=E$ 而 $\mathcal{I}$ 为不构成环的边集的集族。

给 $E$ 任意定向，对边 $e=(u,v)$，向量 $v_e$ 在第 $u$ 维上是 $1$，在第 $v$ 维上是 $-1$ 。不难验证其正确性。

“图拟阵是正则拟阵；任意的正则拟阵的基的计数都可以通过计算一个关联矩阵的行列式求得，而矩阵树定理是其中的特例。”

叁、最优化问题

1.最大权独立集

给定函数 $\omega :\mathbb{U}\mapsto \mathbb{R}$，求 ${\max }_{I\in \mathcal{I}}{\sum }_{x\in I}\omega (x)$ 。显然 $\omega (x)⩽0$ 可被忽略。

只需将 $\mathbb{U}$ 内元素按照 $\omega$ 单调不降的顺序排列，然后线性扫描之，可以加入就加入。

Proof. 令 $X=\{x_1,x_2,\dots ,x_r\}$ 是真正的最大权独立集，其中 $\omega (x_i)$ 单调不增，记 $X_n=\{x_1,x_2,\dots ,x_n\}$ 。令 $S_n$ 为加入第 $n$ 个元素后得到的独立集，归纳证明 $\omega (S_n)⩾\omega (X_n)$ 。对 $n⩾1$，设 $\{u\}=S_n\setminus S_{n-1}$，根据 扩张性 有 $\exists v\in X_n\setminus S_{n-1}$ 使得 $S_{n-1}\cup v\in \mathcal{I}$，然而根据算法流程 $\omega (u)⩾\omega (v)$，根据 $X$ 的排序方式 $\omega (v)⩾\omega (x_n)$，因此 $\omega (S_n)=\omega (S_{n-1}\cup \{u\})⩾\omega (X_{n-1})+\omega (x_n)=\omega (X_n)$ 。$■$

注：其中 $\omega (S)$ 是 ${\sum }_{x\in S}\omega (x)$ 的缩写。之后的问题中也可能这样简记。

2.最小权基

给定函数 $\omega :\mathbb{U}\mapsto \mathbb{R}$，求 ${\min }_{|I|=r(I)=r(\mathbb{U})}{\sum }_{x\in I}\omega (x)$ 。

流程与 最大权独立集 一样，只是不能去掉 $\omega (x)⩾0$ 的。

3.最大最小带权环

很遗憾，最大带权环在 $\omega =1$ 的图拟阵上可以判定哈密顿路的存在性，因此是 $\text{NP-hard}$ 。

最小带权环可以规约到 $\text{Even Set}$ 问题上，而 $\text{Even Set}$ 是 $\text{NPC}$ 问题，因此最小带权环也是 $\text{NP-hard}$ 。

肆、拟阵运算

1.对偶拟阵

${\mathcal{M}}^{\ast }=(\mathbb{U},{\mathcal{I}}^{\ast })$ 是 $\mathcal{M}=(\mathbb{U},\mathcal{I})$ 的 对偶拟阵（$\text{dual matroid}$），其中 ${\mathcal{I}}^{\ast }=\{I:\exists B\text{ is basis of }\mathcal{M},B\subseteq \mathbb{U}\setminus I\}$ 。

换句话说，记 $\mathcal{B}(\mathcal{M})$ 为 $\mathcal{M}$ 的所有 $\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}$ 的集族，则 $\mathcal{B}({\mathcal{M}}^{\ast })=\{\mathbb{U}-I:I\in \mathcal{B}(\mathcal{M})\}$ 。

Proof. 直接证明稍有困难；用 以秩定义 方法可行。
$$\begin{array}{rl}{r}^{\ast }(S)& =\max \{|S\setminus B|:B\in \mathcal{B}(\mathcal{M})\}\\ & =|S|-\min \{|S\cap B|:B\in \mathcal{B}(\mathcal{M})\}\\ & =|S|-r(\mathbb{U})+\max \{|B\cap (\mathbb{U}\setminus S)|:B\in \mathcal{B}(\mathcal{M})\}\\ & =|S|-r(\mathbb{U})+r(\mathbb{U}\setminus S)\end{array}$$

有界性、单调性显然。只需验证次模性。不难发现此时 $|S|-r(\mathbb{U})$ 可消去，事实上就等价于 “次模函数在取补集后仍是次模的”。而这是 $\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{a}\mathrm{l}$ 的。$■$

2.删除与收缩

对于 $\mathcal{M}=(\mathbb{U},\mathcal{I})$ 和 $S\subseteq \mathbb{U}$，定义 $\mathcal{M}$删除$S$ 的拟阵为 $(\mathbb{U}\setminus S,{\mathcal{I}}^{\prime })$ 其中 ${\mathcal{I}}^{\prime }=\{I:I\in \mathcal{I},I\subseteq \mathbb{U}\setminus S\}$，记为 $\mathcal{M}\setminus S$ 。定义 $\mathcal{M}$收缩$S$ 的拟阵为 $({\mathcal{M}}^{\ast }\setminus S{)}^{\ast }$，记为 $\mathcal{M}/S$ 。¹

前者即不再考虑这些元素。后者等价于 $S$ 内的基必选——在 ${\mathcal{M}}^{\ast }$ 中去掉 $S$，也就是不能不选嘛。

当然也可以从 $r$ 函数的角度考虑，有 $r_{\mathcal{M}/S}(Z)=r_{\mathcal{M}}(Z\cup S)-r_{\mathcal{M}}(S)$ 。

这些操作对拟阵是封闭的，这可以通过 $r$ 函数证明。这里我就选择相信论文了。

3.极小元

$\mathcal{M}$ 经过 $\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$ 和 $\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$ 得到的任意拟阵 ${\mathcal{M}}^{\prime }$ 是 $\mathcal{M}$ 的 极小元。

“不严谨的说，拟阵的极小元可以看成原拟阵的一个局部特征。”

4.拟阵并

对于给定的 $k$ 个拟阵 ${\mathcal{M}}_i=({\mathbb{U}}_i,{\mathcal{I}}_i)(1⩽i⩽k)$，定义这 $k$ 个 拟阵的并 为 $\mathcal{M}=(\mathbb{U},\mathcal{I})$，其中 $\mathbb{U}={\bigcup }_{i=1}^k{\mathbb{U}}_i,\mathcal{I}=\{{\bigcup }_{j=1}^k{I}_j:\forall j,I_j\in {\mathcal{I}}_j\}$ 。

其遗传性与扩张性显然，即该运算是封闭的。

这里是个坑，记得要填哦。🥺

暂时先略过其秩函数的变化规律，与独立集判定法。以后请提醒我补上。

伍、拟阵交

匈牙利算法才是万物的起源！——二分图匹配既是拟阵交，又是拟阵并。

由于 拟阵交 在拟阵上并不封闭，所以不列在 拟阵运算 当中。

$l$-拟阵交（$l\text{-matroid intersection}$）：给定 ${\mathcal{M}}_i=(\mathbb{U},{\mathcal{I}}_i)(1⩽i⩽l)$，求 $\max \{I:\forall j\in [1,l],I\in {\mathcal{I}}_j\}$ 。

Theorem 1. $3$-拟阵交问题是 $\text{NPC}$ 问题。

Proof. 二分图上哈密顿路问题是 $\text{NPC}$ 的。在两部点上，分别定义拟阵为 “边集不共用该部的顶点”，再与图拟阵求交，就可以求出二分图上哈密顿路，因此 $3$-拟阵交问题是 $\text{NPC}$ 的。$■$

所以我们只学会下面这个 $P$ 的 $2$-拟阵交问题就行啦！

Theorem 2.（最大最小定理） $\max \{|I|:I\in {\mathcal{I}}_1\cap {\mathcal{I}}_2\}={\min }_{S\subseteq \mathbb{U}}\{r_1(S)+r_2(\mathbb{U}\setminus S)\}$ 。

简单的一侧，即 $\text{LHS}⩽\text{RHS}$ 是显然的。而可以取等的证明就是构造性算法。

1.强基交换定理

定义 闭包（$\text{closure}$）算子 $\text{clos}(A)=\{x\in \mathbb{U}:r(A\cup \{x\})=r(A)\}$ 。

Lemma 2. 若 $A\subseteq S$ 则 $\text{clos}(A)\subseteq \text{clos}(S)$ 。

Proof. $x\in \text{clos}(A)$ 等价于 $A$ 的某个基 $B$ 满足 $B\cup \{x\}\notin \mathcal{I}$，而 $S$ 存在基 $B^{\prime }\supseteq B$，因此 $x\in \text{clos}(S)$ 立刻成立。$■$

Lemma 3. 若 $x\in \text{clos}(A)$ 则 $\text{clos}(\text{clos}(A))=\text{clos}(A)=\text{clos}(A\cup \{x\})$ 。

Theorem 3.（强基交换定理） 对于 $\mathcal{M}$ 的两个不同的基 $A,B$，对于 $\forall x\in A\setminus B$ 都存在 $y\in B\setminus A$ 使得 $A-\{x\}+\{y\}$ 和 $B-\{y\}+\{x\}$ 都是拟阵的基。

Proof. 由 $\text{corollary 2}$ 得 $B+\{x\}$ 包含唯一的环 $C\supseteq \{x\}$ 。显然 $x\in \text{clos}(C-\{x\})$，由 $\text{lemma 2,3}$ 有 $\text{clos}((A\cup C)\setminus \{x\})=\text{clos}(A\cup C)=\mathbb{U}$，因此存在 $\mathcal{M}$ 的基 $A^{\prime }\subseteq (A\cup C)\setminus \{x\}$ 。由 交换性，存在 $y\in A^{\prime }\setminus (A-\{x\})$ 使得 $A-\{x\}+\{y\}$ 是 $\mathcal{M}$ 的基。

注意到 $A^{\prime }\setminus (A-\{x\})\subseteq ((A\cup C)\setminus \{x\})\setminus (A-\{x\})\subseteq C\setminus \{x\}$，所以 $B+\{x\}-\{y\}$ 把 $B+\{x\}$ 中的唯一环 $C$ 拆掉了，所以 $B-\{y\}+\{x\}$ 也是基。$■$

2.交换图

对于 $\mathcal{M}=(\mathbb{U},\mathcal{I})$ 和 $I\in \mathcal{I}$，定义 交换图$D_{\mathcal{M}}(I)$ 为 $\mathfrak{X}=I,\mathfrak{Y}=\mathbb{U}\setminus I$ 的二部图，其中 $x\in \mathfrak{X}$ 和 $y\in \mathfrak{Y}$ 之间有边当且仅当 $I-\{x\}+\{y\}\in \mathcal{I}$ 成立。

Lemma 4. 若 $I,J\in \mathcal{I}$，且 $|I|=|J|$，则 $D_{\mathcal{M}}(I)$ 中存在 $I\setminus J$ 和 $J\setminus I$ 的完美匹配。

Proof. 不妨令独立集大小均不超过 $|I|$，则 $I,J$ 是两个基。根据 强基交换定理，$\exists x\in I\setminus J,y\in J\setminus I$ 使得 $I-\{x\}+\{y\}$ 是基。因此 $*x,y*$ 可匹配，然后递归 $J^{\prime }=J-\{y\}+\{x\}$ 即可。$■$

Theorem 4. 若 $I\in \mathcal{I},|I|=|J|$ 且 $D_{\mathcal{M}}(I)$ 中存在唯一的 $I\setminus J$ 和 $J\setminus I$ 的完美匹配，则 $J\in \mathcal{I}$ 。

Proof. 令 $P$ 是唯一的匹配，将 $P$ 中的边定向为 $\mathbb{U}\setminus I$ 到 $I$，其余反之。匹配唯一说明不存在有向环，用拓扑序重编号（编号小的点指向编号大的点）。设 $P=\{*y_i,x_i*\}$，其中 $y_i\in J\setminus I$ 。重排使得 $x_i\to y_j(i<j)$ 不存在边。

假设 $J$ 不独立，取环 $C\subseteq J$ 与最小的 $i$ 使得 $y_i\in C$，这样的 $i$ 显然存在。此时 $\forall y\in C\setminus \{y_i\}$，因为 $y$ 的实际位置比 $y_i$ 更大，因此 $x_i\to y$ 不存在边，即 $I-\{x_i\}+y\notin \mathcal{I}$，即 $C\setminus \{y_i\}\subseteq \text{clos}(I\setminus \{x_i\})$ 。此时有 $y_i\in \text{clos}(C\setminus \{y_i\})\subseteq \text{clos}(I\setminus \{x_i\})$，这与 $*x_i,y_i*$ 是交换图里的边矛盾。$■$

3.拟阵交算法

定义 交换图$D_{{\mathcal{M}}_1,{\mathcal{M}}_2}(I)$ 为 $\mathfrak{X}=I,\mathfrak{Y}=\mathbb{U}\setminus I$ 的有向二部图，其中 $x\in \mathfrak{X}$ 和 $y\in \mathfrak{Y}$ 之间有 $*x,y*$ 边当且仅当 $I-\{x\}+\{y\}\in {\mathcal{I}}_1$ 成立，有 $*y,x*$ 边当且仅当 $I-\{x\}+\{y\}\in {\mathcal{I}}_2$ 。

初始令 $I=\varnothing$ 。每次令 $X_i=\{x\notin I:I\cup \{x\}\in {\mathcal{I}}_i\}(i=1,2)$，然后在 $D_{{\mathcal{M}}_1,{\mathcal{M}}_2}(I)$ 中找到 $X_1$ 到 $X_2$ 的最短路 $P$，然后令 $I=I\oplus P$，这里 $\oplus$ 表示对称差。直到找不到路径。此时就得到了最大的 $|I|$，以及 最大最小定理 中的 $S=\{z:z\text{ can reach }{X}_2\}$ 。

3.1.独立性

令最短路 $P=\{y_0,x_1,y_1,x_2,y_2,\dots ,x_t,y_t\}$，令 $J=\{y_1,y_2,\dots ,y_t\}\cup (I\setminus \{x_1,x_2,\dots ,x_t\})$ 。可以得到 $|I|=|J|$，且 $I\setminus J$ 和 $J\setminus I$ 在 $D_{{\mathcal{M}}_1}(I)$ 里有唯一完美匹配（在只保留 $\mathfrak{X}\to Y$ 边的图上；因为是最短路）。

由 $\text{theorem 4}$ 即得 $J\in {\mathcal{I}}_1$ 。又因为 $P$ 最短可知 $y_i\notin X_1(1⩽i⩽t)$ 即 $I\cup \{y_i\}\notin {\mathcal{I}}_1$ 即 $r_1(I\cup J)=r_1(I)$ 。由于 $I\cup \{y_0\}\in {\mathcal{I}}_1$ 故 $J\cup \{y_0\}\in {\mathcal{I}}_1$，而 $J\cup \{y_0\}=I\oplus P$ 。

同理，令 $J=I\oplus P\oplus \{y_t\}$ 则 $J\in {\mathcal{I}}_2$，由 $r_2(I\cup J)=r_2(I)$ 得 $J\cup \{y_t\}\in {\mathcal{I}}_2$ 。$■$

3.2.最大最小

先证明 $r_1(S)⩽|I\cap S|$ 。反证法。设 $r_1(S)>|I\cap S|$，根据定义即 $\exists x\in S\setminus I$ 使得 $(I\cap S)\cup \{x\}\in {\mathcal{I}}_1$ 。由于 $x\in S$ 即 $x$ 可到达 $X_2$，必然有 $x\notin X_1$ 即 $I\cup \{x\}\notin {\mathcal{I}}_1$ 。

由 独立性 知 $I\cup \{x\}$ 存在唯一环 $C\supseteq \{x\}$ 。由 $(I\cap S)\cup \{x\}\in {\mathcal{I}}_1$ 知 $C⊊(I\cap S)$ 。于是 $\exists y\in C\setminus (I\cap S)$ 使得 $I-\{y\}+\{x\}\in {\mathcal{I}}_1$ 。

上式说明 $y\to x$ 边存在，因此 $y\in S$，与 $y\in C\setminus (I\cap S)$ 矛盾（注意 $C\subseteq I$ 哦）。$■$

3.3.复杂度

寻找增广路的复杂度是 $\mathcal{O}(r^{2}n)$ 其中 $r=\min \{r_1(\mathbb{U}),r_2(\mathbb{U})\}$ 。

我们还有一些更好的 没有应用价值的 上界：增广路径长度和是 $\mathcal{O}(|I|\log |I|)$ 的，其中 $I$ 是最大公共独立集 [3]；$n$ 点 $m$ 边的图拟阵的拟阵交可以在下面的复杂度内完成 [4]：

• $\mathcal{O}(n^{1/2}m)$ 其中 $m=\Omega (n^{3/2}\log n)$ 。
• $\mathcal{O}(n{m}^{2/3}{\log }^{1/3}n)$ 其中 $m=\Omega (n\log n)$ 且 $m=\mathcal{O}(n^{3/2}\log n)$ 。
• $\mathcal{O}(n^{4/3}{m}^{1/3}{\log }^{2/3}n)$ 其中 $m=\mathcal{O}(n\log n)$ 。

4.带权拟阵交

这一节 $\mathsf{O}\mathsf{n}\mathsf{e}\mathsf{I}\mathsf{n}\mathsf{D}\mathsf{a}\mathsf{r}\mathsf{k}$ 没看懂，如果有人懂可不可以讲讲啊 🥺

类似于 最优化问题：给定 $\omega :\mathbb{U}\mapsto \mathbb{R}$ 求 $\max \{{\sum }_{x\in I}\omega (x):I\in {\mathcal{I}}_1\cap {\mathcal{I}}_2\}$ 。按：疑为 ${\mathbb{R}}^{+}$ 。

使用带权的 最大最小定理
$$\underset{I\in {\mathcal{I}}_1\cap {\mathcal{I}}_2}{\max }\sum _{x\in I}\omega (x)=\underset{{\omega }_1,{\omega }_2}{\min }\{\max \{{\omega }_1(I):I\in {\mathcal{I}}_1\}+\max \{{\omega }_2(I):I\in {\mathcal{I}}_2\}\}$$

其中 ${\omega }_1,{\omega }_2$ 是两个 $\mathbb{U}\mapsto \mathbb{R}$ 的函数满足 $\forall x\in \mathbb{U},{\omega }_1(x)+{\omega }_2(x)=\omega (x)$ 。

在算法实现中，我们在交换图中定义点权
$$\nu (x)=\{\begin{array}{ll}\omega (x),& x\notin I\\ -\omega (x),& x\in I\end{array}$$

求最短路改为求 $X_1$ 到 $X_2$ 的路径中，在点权最小的前提下使得经过的边数最小。

“可以证明交换图中不存在负权环，因此这个算法一定有解。”

陆、参考

[1] 杨乾澜，浅谈拟阵的一些拓展及其应用，$\mathrm{I}\mathrm{O}\mathrm{I}2018$ 中国国家队候选队员论文。

[2] 好地方bug，拟阵及应用，知乎专栏。

[3] William H. Cunningham, Improved Bounds for Matroid Partition and Intersection Algorithms.[J]. SIAM J. Comput.,1986,15(4). 10.1137/0215066.

[4] H. N. Gabow and M. Stallman, Efficient algorithms for graphic matroid intersection and parity, extended abstract, in Automata, Languages and Programming, Lecture Notes in Computer Science, Springer, Berlin, 1985. 10.1007/BFb0015746.

[5] zghtyarecrenj，从拟阵基础到 Shannon 开关游戏，luogu-blog.

---

1. 英文名为 $\text{deletion}$ 和 $\text{contraction}$，论文作者未找到标准翻译。 ︎