拟阵
拟阵基本概念
拟阵$M=(S,\mathcal I)$，其中$S$是全集，而$I$是$S$的一个子集族。拟阵需要满足下面的三大公理：
- $\emptyset\in \mathcal I$
- 如果$A\subset B$，且$B\in \mathcal I$，则一定有$A\in \mathcal I$
- 如果$A,B\in \mathcal I$，有$|A|<|B|$，则一定存在一个元素$x\in B/A$，满足$\left\{ x \right\}\cup A \in \mathcal I$
$I$中的集合元素我们称之为独立集，而其余$S$的子集我们称为非独立集。我们称最大独立集为基。
对于$T\subseteq S$，我们记$r(T)$表示$T$中最大的独立集子集的大小，称为$T$的秩。$r(T)$满足下面的三个性质：
- $0\leq r(T)\leq |T|$
- 若$A\subseteq B$，则有$r(A)\leq r(B)$
- $r(A\cup B)+r(A\cap B)\leq r(A)+r(B)$
我们可以通过拟阵的性质推出秩函数的性质，反之亦然。换言之，如果我们在某个集合$S$上定义了所有满足上面三个性质的秩函数，则记$I=\left\{T|T\subseteq S\land r(T)=|T| \right\}$，则$M=(S,\mathcal I)$就是拟阵。
定义拟阵$M=(S,\mathcal I)$的对偶拟阵为$M^*=(S,\mathcal I^*)$，其中$\mathcal I^*=\left\{ X | r(S/X)=r(S) \right\}$，很显然$M^*$也是一个拟阵。
对于拟阵$M_1=(S_1,\mathcal I_1)$和拟阵$M_2=(S_2,\mathcal I_2)$，$M=(S_1\cup S_2, I_1\times \mathcal I_2)$也是一个拟阵，其中$I_1\times \mathcal I_2$是直积。
很多问题都可以建模成拟阵。
- 颜色拟阵：给定$n$个元素，每个元素都有自己的颜色。一个集合是独立集当且仅当集合中所有元素的颜色不同。
- 图拟阵：给定$n$个顶点和$m$条边，一个边集是独立集当且仅当集合中的边不形成任意环。
- 代数拟阵：给定$n$个向量，一个向量集合是独立集当且仅当集合中的所有向量线性无关。
- 删边图拟阵：给定$n$个顶点和$m$条边，一个边集是独立集当且仅当删除这些边后图依旧保持连通。
下面是一些拟阵的额外命题（这些定理的证明来自拟阵划分）：
定义1：设$M=(E,\mathcal I)$为一拟阵，$A\subseteq E$，$I\subseteq A$且$I\in \mathcal I$。设$S=I\cup \left\{e\in A:I\cup \left\{e\right\}\notin \mathcal I\right\}$，$S$被称为$\mathcal I$在$A$中的闭包（对于拟阵$M$）。
引理一：对任何拟阵$M=(E,I)$，如果$A\subseteq E$并且$I\subseteq A$且$I\in \mathcal I$，则$I$在$A$中的闭包$S$是$\left\{S\subseteq A:I\subseteq S,r(S)=|I|\right\}$中的极大集（唯一）。
引理二：考虑拟阵$M=(E,I)$上的$I\in I$和$e\in E$，$I\cup \left\{e\right\}$至多包含$M$的一个圈。
最大独立集与最大权独立集
通过拟阵的第三条公理，可以得到一个寻找最大独立集的算法：
我们从维护一个空集$X$开始，之后依次不断尝试所有的元素$e$，如果$e$加入$X$不破坏$X$的独立性，则加入。
而对于最大权独立集，我们可以把所有元素按照权值从大到小排序后进行上面算法，可以保证最后得到的独立集在保证最大的前提下，权值最大。
两个算法都只需要执行多项式次判断某个集合是否是独立集，如果判断某个集合是否是独立集可以在多项式时间复杂度内实现，那么总的时间复杂度就是多项式的。
拟阵交的最大独立集和最大权独立集
给定两个拟阵$M_1=(S,I_1),M_2=(S,I_2)$，记$M_{1,2}=(S,I_1\cap I_2)$为$M_1$和$M_2$的拟阵交。两个拟阵的交不一定满足拟阵的第三条公理，当然也不能保证是一个拟阵。
一般对三个或更多拟阵的交求最大独立集是NP-hard的，因为哈密顿路径可以描述为三个拟阵的交。但是神奇的是对于两个拟阵的交我们有多项式时间复杂度的算法计算拟阵的最大独立集。
算法流程如下：
我们从维护一个空集$X$开始。
将集合$X$和$S/X$建立为二分图的顶点，同时加入额外的两个源点$s$和汇点$t$。对于$x\in X,y\in S/X$，如果$X-\left\{x\right\}+\left\{y\right\}$是$M_1$中的独立集，则从$x$到$y$连一条有向边，如果$X-\left\{x\right\}+\left\{y\right\}$是$M_2$中的独立集，则从$y$到$x$连一条有向边，如果$X+\left\{y\right\}$是$M_1$中的独立集，我们从$s$向$y$连一条有向边，如果$X+\left\{y\right\}$是$M_2$中的独立集，我们从$y$向$t$连一条有向边。
之后我们找到一条$s$到$t$的最短路径，很显然路径上的$S/X$中的顶点数目比$X$中顶点数目多$1$。之后我们将$s$和$t$从路径中删除，路径上剩下顶点组成的集合记做$P$,之后$X$与$P$取亦或（就是仅保留在$X$和$P$中总共出现一次的元素）的到新的$X$集合。
直到无法找到一条从$s$到$t$的有效路径，算法结束。这时候的到的$X$是拟阵交的最大独立集。
如果想要求最大独立集，则需要修改上面流程，为每个顶点赋予一个点权，其中$X$中的点权为它本身权重取负，而$S/X$中的点权为它本身的权重。可以保证图中没有负环，因此我们可以在图上跑SPFA算法即可。以路径总点权作为第一关键字，经过边数作为第二关键字，找最短路（点权最大，但是经过边数最少的路径）。
如果判断某个集合是否是独立集可以在多项式时间复杂度内实现，那么两个算法的时间复杂度就是多项式的。
很多问题都可以表述为拟阵交。
题目1：给定二分图要求找最大匹配和最大权匹配。
第一个拟阵要求左边每个顶点度数不超过$1$，第二个拟阵要求右边每个顶点度数不超过$1$（其实两个拟阵都是颜色拟阵），它们的交的最大独立集就是二分图最大匹配，而最大权独立集，就是二分图最大权匹配。
题目2：给定$n$个分组，每个分组有若干个整数，问是否有可能从每个分组中挑选一个整数，且挑选出来的所有数的任意子集的亦或和都非$0$，如果有找到一种方案。其中$1\leq n\leq 100$，且整数数量不超过$10000$。
提供一道题目。
这个问题可以分解为两部分，第一部分为每个分组挑选最多一个数，第二部分为挑选出来的整数线性无关。我们可以将两部分都表述为拟阵，之后算拟阵交的最大独立集即可，时间复杂度为$O(64n(m+n))$。
题目3：给定$n$个分组，每个分组有若干条边，尝试每组选择一条边，构成一株生成树。
老规矩，分成颜色拟阵和图拟阵的交求解即可。提供一道题目。
题目4：给定$n$个顶点和$m$条带权无向边，每条边的颜色为红蓝绿三色中的一种。要求对于所有$k=1,2,\ldots,m$，判断是否可能取其中一些边，满足删除所有红边或蓝边后图依旧连通。如果有解，则输出最少的费用，其中费用为所有选中的边的边权之和。
提供一道题目。
红绿边为第一个删边拟阵，蓝绿边为第二个删边拟阵，我们要求的其实是计算拟阵交的最大权独立集的中间产物。时间复杂度为$O((nm)^2)$。
拟阵划分
拟阵划分是指将集合中的元素划分成最少的不想交的独立集。
定理一：存在互斥的$I_i\in \mathcal I_i$，满足$E=\bigcup_{i=1}^kI_i$，当且仅当对任何$A\subseteq E$，
\[|A|\leq\sum_{i=1}^kr_i(A)\]特别地，如果这$k$个$I_i$是同一个$I$，则可以叙述为：$E$可以被表示为小于等于$k$个独立集的并，当且仅当对任何$A\subseteq E$，
\[|A|\leq k\cdot r(A)\]下面拟阵划分的算法来自WIKI。
一开始我们创建一个单独的空独立集。之后我们重复下面流程：
- 如果所有元素都已经被分配到某个独立集了，那么结束流程。
- 否则我们建立一幅图，每个元素和独立集都对应一个顶点。如果某个元素$i$可以加入到独立集$j$中，使得独立性不被破坏，那么我们从独立集$j$向元素$i$连一条有向边。如果某个已分配的元素$i$，可以在其所属的独立集中通过元素$j$替换元素$i$而不失独立性，则从$i$向$j$连一条有向边。之后我们从所有独立集对应的顶点开始跑多源BFS。
- 如果至少有一个未分配元素可达，那么找到距离最近的一个未分配元素，并沿着最短做对应的替换操作。操作完成后，未分配元素会减少$1$。距离最近非常重要，否则不能保证替换操作不会破坏独立性。
- 如果所有未分配元素都不可达，就新增一个单独的空独立集。
提供一道题目。
再提供一道题目，需要利用双生成树求解一个欧拉环。
参考资料
- [Tutorial] Matroid intersection in simple words
- 《浅谈拟阵的一些拓展及其应用》by 杨乾澜
- 拟阵划分
- matroid partition wiki