散裝指完全從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很簡潔而且是中文，不過內(nèi)容上基本和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。但是我們解決他的方式是，思考假設已經(jīng)有一個indepedent set，但是很小，我們想辦法把他擴大，并且仍然保持independence。由于我們已經(jīng)知道m(xù)atroid intersection并不是一個matroid（例子https://math.stackexchange.com/questions/956805/example-intersection-matroid-is-not-a-matroid ，我覺得這也是matroid這個概念非常成功的一個表現(xiàn)），greedy顯然是不可行的，為了把一個已有的independent set擴大，我們有時不得不改變其中一些元素（或者說之前加入了錯誤的元素，現(xiàn)在要刪掉換成別的）

現(xiàn)在我們重新來看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都是獨立的。