拟阵学习笔记

做一道联合省选题的时候遇到了这个，之前高爸也屡次♂邀请♂我学它，于是就有了本文。

本文旨在介绍拟阵的概念和应用，其中部分定理不会作出证明，详细的证明请阅读集训队论文。

拟阵第一定义

拟阵（Matroid）是指一个集合$S$与其幂集的子集（family of subset）$\mathcal{I}$（$\mathcal{I}\subseteq 2^S$）构成的二元组$(S,\mathcal{I})$使得$\mathcal{I}$满足：

1. 遗传性：若$I\in \mathcal{I}$，那么$\forall A\subseteq I$，有$A\in \mathcal{I}$。
2. 扩张性（也称交换性）：对于$A,B\in \mathcal{I}$且$|A| < |B|$，一定存在$e\in B\setminus A$使得$A+\{e\} \in \mathcal{I}$。

其中$S$被称为基础集，$I\in \mathcal{I}$被称为独立集，$\mathcal{I}$则是独立集的集合。

上述两个条件也被称作拟阵公理，它们是拟阵最基本的特征。基于拟阵公理，我们可以容易地理解以下模型的拟阵性。

图拟阵

图拟阵描述的是对于无向图$G=(V,E)$，以边集$E$做为基础集的拟阵$(E, \mathcal{I})$，其中$I\in \mathcal{I}$当且仅当$I$无环。

从拟阵公理的角度：

1. 图拟阵的遗传性是显然的。
2. 扩张性：对于$A,B\in \mathcal{I}$，若$|A| < |B|$，那么图$(V,A)$的连通块数一定多余$(V,B)$的连通块数，那么一定存在$B$的一个连通块，它在$A$里是不连通的，这时我们就可以找到一条边$e \in B\setminus A$使得$A+ \{e\}$无环，即$A\cup \{e\}$是独立集。则扩张性成立。

线性空间拟阵

这名字我起的，不够严谨。

线性空间拟阵描述的是以线性空间$S$做为基础集的拟阵$(S,\mathcal{I})$，其中$I \in \mathcal{I}$当且仅当向量组$I$线性无关。

同样地，从拟阵公理的角度：

1. 遗传性显然。
2. 扩张性：对于$A,B\in \mathcal{I}$，若$|A| < |B|$，则$B$中一定存在一个向量$e$不能被$A$中的向量线性表出（如果不存在，那么$B$就能被$A$表出，则$B$中的向量不可能互相线性无关）。

拟阵第二定义

拟阵的第二定义是从秩函数的角度出发。对于基础集$S$和其幂集的子集$\mathcal{I}$（$\mathcal{I}\subseteq 2^S$），定义秩函数（rank function）$r(U)$：

$$r(U) = \max_{I\subseteq U, I\in \mathcal{I}} |I|$$

即$U$的极大独立子集。

那么如果$r$满足如下三个性质，我们就称$(S,\mathcal{I})$是拟阵：

1. 有界性：$r(U)\le |U|$；
2. 单调性：$\forall A\subseteq B\subseteq S$，有$r(A) \le r(B)$；
3. 次模性：$\forall A,B\subseteq S$，$r(A\cup B) + r(A\cap B) \le r(A) + r(B)$。

如何理解次模性

次模性可以理解为边际效益递减，其有一个更直观的等价的表达式：

$\forall A\subseteq B\subseteq S$且$\forall e\notin B, e\in S$，有$r(A+\{e\}) - r(A)\ge r(B+\{e\}) - r(B)$。

也就是说我往$A$里加一个元素的秩的增量大于等于往$B$里加一个元素的秩的增量。

$B$是$A$已经吸纳了$B\setminus A$这部分元素得到的，于是$B$再吸纳$e$带来的收益就比不上$A$直接吸纳$e$带来的收益。

如果放在全序集合上，这其实就是凸性的体现。

拟阵第一定义和第二定义是可以互推的。

我们同样用两个例子来补充叙述这一定义。

图拟阵：对于图拟阵$(E, \mathcal{I})$，其秩函数$r(U)$实质上是$G[U]$的生成森林的边数。其单调性和有界性都很容易证明，而次模性可以使用其第二种表达式来证明。

线性空间拟阵：对于线性空间拟阵$(S,\mathcal{I})$，其秩函数$r(U)$描述的是$U$中的最大线性无关组（或者说线性基）的大小。证明不做详细阐述。

接下来我们用拟阵的两种定义来介绍更多关于拟阵的概念，以丰富它的工具性。

基与交换定理

对于拟阵$M = (S, \mathcal{I})$中的一个独立集$I$，若往$I$中加入任意一个元素都会让它变成非独立集，那么称$I$是拟阵$M$的一个基，也称极大独立集。

容易证明，拟阵的基大小相同。

基有另一个等价的定义形式：满足$|I| = r(S)$的独立集$I$是拟阵$M$的基。

关于基有两个定理，分别是（弱）基交换定理和强基交换定理。

弱基交换定理：对于任意拟阵$M$，若存在两个不同的基$A,B$，则$\forall x\in A\setminus B$，$\exists y\in B\setminus A$使得$A-\{x\} + \{y\}$是基。

强基交换定理：对于任意拟阵$M$，若存在两个不同的基$A,B$，则$\forall x\in A\setminus B$，$\exists y\in B\setminus A$使得$A-\{x\} + \{y\}$和$B-\{y\} + \{x\}$都是基。

具体的证明参见论文。

拟阵上的最优化问题

拟阵上的最优化问题定义为：给出拟阵$M=(S,\mathcal{I})$，给出价值函数$w:S\to\mathbf{R}$。对于$A\subseteq S$定义$W(A) = \sum_{e\in A}w(e)$。求$\max_{I\in \mathcal{I}}W(I)$。

拟阵上的最优化问题可以使用贪心算法，即将$e\in S$按照$w(e)$不升的顺序排列，令$I$初始为空集，然后从大到小在保证$I$独立的前提下将$e$加到$I$中，最后得到的就是最优解。

详细的证明不展开叙述。

最小生成树问题（MST）和和寻找线性基的问题都可以规约为拟阵上的最优化问题。有关的贪心算法的正确性因此得到了保证。

拟阵的基础操作

接下来介绍三种关于拟阵的操作，这可以帮助我们更深刻地理解拟阵模型的变换。

对偶

对于拟阵$M = (S,\mathcal{I})$，定义其对偶拟阵为$M^\ast = (S,\mathcal{I}^\ast)$，其中$\mathcal I^\ast = \{I : \exists B\in\mathcal I, |B|=r(S), B\subseteq S\setminus I\}$，即存在一个$M$中的基$B$使得$B\subseteq S\setminus I$。

这里我们断言拟阵的对偶仍是拟阵，这一点不论是用拟阵第一定义还是第二定义都可以证明。

对偶运算具有自反性，这从它的定义就可以得知。

举一个对偶拟阵的例子：图拟阵$(E, \mathcal I)$的对偶拟阵为$(E, \mathcal I^\ast)$，其中$I\in \mathcal I^\ast$当且仅当$E-I$存在基，即存在生成树，即连通。

换言之，$I\in \mathcal I^\ast$当且仅当删掉$I$中的边后，图仍然连通。

删除

对于拟阵$M = (S,\mathcal I)$和$Z\subseteq S$，定义$M$删除$Z$的拟阵是$M\setminus Z = (S - Z, \mathcal I')$，其中$\mathcal I' = \{I : I\subseteq S-Z, I\in \mathcal I\}$。

换言之，就是删掉$Z$中的部分得到的拟阵。

同样以图拟阵为例，$(E, \mathcal I)$删除$Z$（$Z\subseteq E$）的拟阵就是$G=(V, E-Z)$对应的图拟阵。

收缩

对于拟阵$M = (S,\mathcal I)$和$Z\subseteq S$，定义$M$收缩$Z$的拟阵是$M/Z = (M^\ast\setminus Z)^\ast$。

这东西看着不太直观，经过一番推导我们得到它的秩函数$r_{M/Z}(U) = r_M(Z\cup U) - r_M(Z)$。

通过这个秩函数，我们将收缩理解为强制选取了$Z$中的一组基。

仍然以图拟阵为例，对应$M_G = (E,\mathcal I)$：

• $M_G^\ast$的独立集$I$：删掉$I$中的边后图仍然连通。
• $M_G^\ast \setminus Z$的独立集$I$：强制$Z$中的边不能被删（即强制$I\cap Z = \varnothing$），删掉$I$中的边后图仍然连通。
• $(M_G^\ast \setminus Z)^\ast$的独立集$I$：强制$I$满足$I\cap Z$是$Z$的生成森林（基）。

因此图拟阵收缩$Z$可以理解为缩边操作。

拟阵的交

提示：这部分内容与拟阵的基础操作不太相关。

对于两个相同基础集$S$上的拟阵$M_1= (S, \mathcal I_1)$和$M_2 = (S, \mathcal I_2)$，定义它们的交$(S, \mathcal I_1\cap \mathcal I_2)$。

拟阵的交，不一定是拟阵。

（带权）拟阵交问题定义为：给出价值函数$w:S\to\mathbf{R}$。对于$A\subseteq S$定义$W(A) = \sum_{e\in A}w(e)$。则求$\max_{I\in \mathcal I_1 \cap \mathcal I _2} W(I)$。

为了描述求拟阵交的算法，我们先定义关于两个拟阵$M_1, M_2$的交换图$D_{M_1, M_2}(I)$：

• 其为二分图，左部和右部的点集分别为$I$和$S\setminus I$。
• 一条从$I$到$S\setminus I$的边$(u,v)$存在，当且仅当$I-\{u\} +\{v\}\in \mathcal I_1$。
• 一条从$S\setminus I$到$I$的边$(v,u)$存在，当且仅当$I-\{u\} +\{v\}\in \mathcal I_2$。

也就是说这个二分图里从左到右的边都是满足$\mathcal I_1$的，从右到左的边都是满足$\mathcal I_2$的。

我们还需要定义关于$I$的两个集合$X_1, X_2$：

• $X_1 = \{x \in S\setminus I: I+\{x\}\in \mathcal I_1\}$。
• $X_2 = \{x \in S\setminus I: I+\{x\}\in \mathcal I_2\}$。

以及一个关于$I$的点权函数：

$$f(u) = \begin{cases} w(u) & u\in S\setminus I\\ -w(u) & u\in I \end{cases}$$

接下来我们就可以描述求拟阵交问题的算法——称之为增广路算法足够恰当。

考虑逐步扩张$I$。初始$I=\varnothing$。每次我们找一条从$X_1$中的点出发，交替经过$I$和$S\setminus I$中的点，最后到达$X_2$中的点的点权和最小的简单路径$P$，然后令$I\gets I\Delta P$，即$I$和$P$的对称差。直到找不到$P$。最后得到的就是拟阵交的最大权独立集。

注意，若$X_1\cap X_2$非空，算法可能会直接扩张一个属于交集的元素。

算法的正确性证明见论文。

从算法应用的角度，我们关注的是如何快速求出二分图的边集，或者说在找增广路的过程中如何快速找到后继。若只考虑增广的复杂度，我们最多增广$r = \max(r_1(S), r_2(S))$次，则总复杂度$O(r^2n)$。

例题

时间有点晚，写一道吧，有时间再补补。

Rainbow Graph

给定一张带权无向图$G = (V, E)$，每条边是三种颜色红绿蓝之一。要求对于从$1$到$|E|$的每个$k$，都求出来：选出$k$条边并使得不含红色边的图和不含蓝色边的图都连通的最小权值，如果不存在则输出$-1$。

$|V|, |E| \le 100$。

将问题转化为：删除$k$条边使得不含红色边的图和不含蓝色边的图都连通。因此构造：

• $M_1 = (E,\mathcal I_1)$，$I\in \mathcal I_1$描述的是删掉$I$中的边后不含红色边的图连通。
• $M_2 = (E,\mathcal I_2)$，$I\in \mathcal I_2$描述的是删掉$I$中的边后不含蓝色边的图连通。

通过拟阵第一定义可以证明这两个都是拟阵。求拟阵交即可。由于拟阵交的增广路算法是从空集逐步拓展的，因此可以得到每个$k$的答案。

参考文献

杨乾澜 ，《浅谈拟阵的一些拓展及其应用》，IOI2018 中国国家集训队论文。