来点散装拟阵交

散装指完全从google上学。。。

读了

1. https://math.mit.edu/~goemans/18433S11/matroid-intersect-notes.pdf

2. https://zhuanlan.zhihu.com/p/54713563

3. https://codeforces.com/blog/entry/69287

4. IOI2018 中国国家候选队论文集 浅谈拟阵的一些拓展及其应用 杨乾澜 p143

印象里4写的相当清楚，3比较直观但是缺少证明，2很简洁而且是中文，不过内容上基本和1一样，1里面有一些typo

另外我matroid也是散装的，直接在 https://en.wikipedia.org/wiki/ ctrl+f 就可以找到东西的定义

1 的思路：

首先给出

而且说明了这个theorem是怎么来的，对于任意的两个拟阵的independent set S和一个集合U，我们可以把S分成 S\cap U 和 S\cap (E\U)两部分，并且这两部分对于两个拟阵来说都仍然是independent set. 因此 |S| = |S\cap U| + |S\cap (E\U)| <= r1(U) + r2(E\U)，对这个不等式左边取max右边取min就可以很容易的得到这个定理，1接下来用matroid intersection的算法来说明可以取等。

然后是matroid intersection的算法（exchange graph）我认为exchange graph是非常奇怪的，也许可以用3的思路来解释一下，首先我们的问题是找一个最大的集合，对于两个拟阵都是independent set。但是我们解决他的方式是，思考假设已经有一个indepedent set，但是很小，我们想办法把他扩大，并且仍然保持independence。由于我们已经知道matroid intersection并不是一个matroid（例子https://math.stackexchange.com/questions/956805/example-intersection-matroid-is-not-a-matroid ，我觉得这也是matroid这个概念非常成功的一个表现），greedy显然是不可行的，为了把一个已有的independent set扩大，我们有时不得不改变其中一些元素（或者说之前加入了错误的元素，现在要删掉换成别的）

现在我们重新来看exchange graph，由于边的定义，我们可以更换这个二分图中边上的两个点，并且不影响S对于其中一个拟阵而言的independence，这里的想法非常像二分图匹配中找增广路。

而且我们有这样一个定理

回顾一下一些符号的定义，,X2 类似。算法中找的是一条从X1到X2的最短路P。考虑到exchange graph的结构，S和P的交集大小一定要比E\S和P的交集大小更小（少一个点），此时我们把S换成P和S的对称差，S一定会变大。假设S中有一个虚假的点，这个点T能走到P在X1中的起点，从P在X2中的重点也能走到T，由于我们找的是最短路，这确实是一个unique perfect matching（忽略边的方向），用上面的 proposition 5.5，我们知道对称差对于两个matroid都是独立的。