定义
拟阵 Matroid
给定全集 X 和 X 上的一个集族 I，我们可以定义拟阵 M=⟨X,I⟩。
对 I∈I，称 I 是一个独立集。
以及要求有以下性质：
X 是有穷集合。
（遗传性）I′⊆I∈I⟹I′∈I。
（交换性）A,B∈I∧|A|<|B|⟹∃x∈B∖A,A∪{x}∈I。
基 Basis
拟阵 M 的基 B 是所有极大独立集。由性质，显然同时也是所有最大独立集。
环 Circuit
拟阵 M 的环是所有极小非独立集。
秩 Rank
拟阵 M=⟨X,I⟩ 有秩函数 r:2X→N，其中为 r(S) 为 S 的极大独立子集的大小。显然同时也是最大独立子集。
一些关键性质：
（有界性）0≤r(S)≤|S|。
（单调性）T⊆S⟹r(T)≤r(S)。
（次模性）r(A)+r(B)≥r(A∪B)+r(A∩B)。
关于次模性的证明，考虑 A∩B 的一个基 Z，通过交换性我们可以找出 A∪B 的一个基 ZAB⊇Z，然后我们注意到 (ZAB∩(A∖B))∪Z 是独立集，B∖A 同理，而显然 Z=ZAB∩A∩B，因而命题得证。
不过笔者在网络上看到了另一种更直观的见解，就是将命题改写为
A⊆B⟹r(A∪{x})−r(A)≥r(B∪{x})−r(B)
x∈B 的情况是 trivial 的。对于 x∉B，若右侧是 0 则命题成立，若右侧是 1 则表示 B∪{x} 的所有基都包含 x，进一步由交换性得 B 的所有基都与 x 独立，因而左侧也为 1。
同时容易该命题与原先给出的命题等价，留作读者练习。
之所以说它直观，是因为这给出了一种类似「凸性」的性质，也就是集合越大的时候添加一个新元素的影响越小。
强基交换引理 Strong Basis Exchange Lemma
定义 span(A)={x∈X∣r(A∪{x})=r(A)}。
性质 1
A⊆B⟹span(A)⊆span(B)
证明：考虑 x∈span(A)，有 0=r(A∪{x})−r(A)≥r(B∪{x})−r(B)，因而 r(B∪{x})=r(B)。
性质 2
x∈span(A)⟹span(A∪{x})=span(A)
证明：只需考虑证明 span(A∪{x})⊆span(A)。考虑 y∈span(A∪{x})，我们有 0=r(A∪{x})−r(A)≥r(A∪{x,y})−r(A∪{y})，因而 r(A∪{y})=r(A∪{x,y})=r(A∪{x})=r(A)。
性质 3
span(span(A))=span(A)。
引理
对于 B,B′∈B 且 B≠B′，∀x∈B∖B′，∃y∈B′∖B 使得 B∖{x}∪{y}∈B 且 B′∖{y}∪{x}∈B。
证明：考虑 x∈B∖B′，易知 B′∪{x} 包含一个环 C∋x。
因而我们有 x∈span(C∖{x})，于是 x∈span((B∪C)∖{x})，从而 span((B∪C)∖{x})=span(B∪C)=X。
因而 ∃B″⊆(B∪C)∖{x},B″∈B，且 |B″|>|B∖{x}|。由交换性得 ∃y∈B″∖(B∖{x}),(B∖{x})∪{y}∈B。
而 B″∖(B∖{x})⊆(B∪C)∖{x}∖(B∖{x})⊆C∖{x}，结合上一行即 ∃y∈C∖{x},(B∖{x})∪{y}∈B。
同时由于 C 是一个环，也有 (B′∖{y})∪{x}∈B。
独立性谕示 Independence Oracle
拟阵相关的很多算法需要在一些特殊条件下高效判定独立性。
常见拟阵
省略一些证明。当然，其中有一些由于独立性谕示较为困难，在应用中并不常见。
均匀拟阵 Uniform Matroid
I={I⊆2X∣|I|≤k}。
k=0 称为 Trivial Matroid。k=|X| 称为 Complete Matroid。
划分拟阵 Partition Matroid
给定 X 的一组划分 X1,X2,…,Xm 以及参数 d1,d2,…,dm，I∈I 当且仅当 |I∩Xi|≤di。
di=1 称为有色拟阵 Colorful Matroid。
图拟阵 Graphic Matroid
对于 G=(V,E)，取 X=E，I∈I 当且仅当 I 的导出子图无环。
基环拟阵 Bicircular Matroid
对于 G=(V,E)，取 X=E，I∈I 当且仅当 I 的导出子图中每个连通分量至多有一个环，即基环树森林。
线性拟阵 Linear Matroid
X 是一些向量，独立定义为线性无关。
横截拟阵 Transversal Matroid
给一二分图，左右部分别为 U,V。令 X=U，I 独立定义为 I 能被一组匹配覆盖。
匹配拟阵 Matching Matroid
无向图版本。
截断拟阵 Truncated Matroid
在不破坏拟阵性质的情况下可以增加一些限制。比如有色拟阵限制颜色数，图拟阵限制连通块数。
部分拟阵
将 X 变为一个子集。
拟阵的和
将两个不影响独立性的独立集族做笛卡尔积。
Rado-Edmonds 算法
求拟阵的最小权基。
对于不带权的情况，显然直接逐个加入即可。
对于带权的情况，考虑大小为 k 的最小权独立集 A 和大小为 k+1 的最小权独立集 B。
考虑 x∈B∖A 使得 A∪{x}∈I，则由最小有 w(A)≤w(B∖{x}) 和 w(B)≤w(A∪{x})。
在第一个式子中左右两边同时加入 x 有 w(A∪{x})≤w(B)。因此 w(A∪{x})=w(B)。
这说明带权的情况我们依然可以应用交换性，每次加入最小权的可加入的元素即可。
拟阵交
例子就省略了。值得注意的是，Hamilton 回路问题是三个拟阵的交。
交换图
对 Strong Basis Exchange Lemma 加以推广（即在截断拟阵上应用），可知相同大小的独立集之间也是可以交换的。
对于 S∈I，定义二分图 D(S)，其中 (x,y) 有边当且仅当 x∈S,y∈X∖S,S∖{x}∪{y}∈I。
引理
对于两个独立集 |S|=|T|，D(S) 存在 S∖T 和 T∖S 的完美匹配。
证明：将拟阵的独立集截断到 |S|，考虑 x∈T∖S，由 Strong Basis Exchange Lemma，∃y∈T∖S 使 S∖{x}∪{y},T∖{x}∪{y} 都是独立集。
因而 (y,x) 一定是 D(S) 的一条边。
从而我们令 T←T∖{x}∪{y} 即可一直归纳。
引理
对于独立集 S 和集合 T 满足 |S|=|T|，若 D(S) 中存在 S∖T 到 T∖S 的唯一匹配，则 T 是独立集。
不想证了，放两个图：
未完待续。