前言
为了简便，我们使用 \(X + x\) 表示 \(X \cup \{x\}\)，\(X - x\) 表示 \(X \setminus \{x\}\)。
定义
拟阵
拟阵（matroid）是对向量空间中线性独立这一概念的概括与归纳。
拟阵形如 \((E, \mathcal I)\)，其中 \(E\) 为 基集（ground set），\(\mathcal I\) 为 \(E\) 的子集族（family of set，由 \(E\) 的子集构成的“集合”），其中元素叫做 独立集（independent set），需要满足以下公理：
- \(\varnothing \in \mathcal I\)；
- 遗传性：\(\forall X \subseteq Y \in \mathcal I, X \in \mathcal I\)；
- 交换性：\(\forall X, Y \in \mathcal I, |X| < |Y|, \exists e \in Y \setminus X, X + e \in \mathcal I\)。
基
基（basis）是极大独立集，有如下性质：
- 每个基都是最大独立集，两两互不包含；
- 每个独立集都包含于一个基。
所有基的集合记作 \(\mathcal B\)。
圈
圈（circuit）是极小不独立集，有如下性质：
- 两两互不包含；
- 每个不独立集都包含一个圈；
- 两个圈的并，删掉任意一个元素后仍独立。
所有基的集合记作 \(\mathcal C\)。
秩
集合 \(X \subseteq E\) 的 秩（rank）是 \(X\) 的最大独立子集大小，记作 \(r(X)\)。拟阵的秩是最大独立集的大小，也就是基集的秩。令 \(X, Y \subseteq E\)，秩有如下性质：
- \(0 \le r(X) \le Y\)（两边等号分别在 \(X = \varnothing\) 与 \(X \in \mathcal I\) 时取到）；
- \(X \subseteq Y \Rightarrow r(X) \le r(Y)\)；
- 次模性（submodularity）：\(r(X) + r(Y) \ge r(X \cap Y) +r(X \cup Y)\)。
基集给定后，只要满足对应的性质，基的集合、圈的集合与秩函数，任意一个都可以精确描绘一个拟阵。
生成空间
集合 \(X \subseteq\) 的 生成空间（span）是加入到 \(X\) 前后秩不变的元素（可以在 \(X\) 中）的集合。令 \(X, Y \subseteq E\)，生成空间有如下性质：
- \(X \subseteq Y \Rightarrow \operatorname{span}(X) \subseteq \operatorname{span}(Y)\)；
- \(\forall x \in \operatorname{span}(X), \operatorname{span}(X) = \operatorname{span}(X + x)\)。
强基交换
强基交换（strong basis exchange）引理：
由于所有等大的独立集可以看作一个截断矩阵的基，这个定理对于等大的独立集也成立。
独立性谕示
独立性谕示（independence oracle）相当于一个黑箱，可以回答一个子集是否独立。
对于不同的拟阵，它的复杂度可能不同。下面一些算法的复杂度会与此相关。
常见拟阵
均匀拟阵（uniform matroid）：\(X\) 独立当且仅当 \(|X| < k\)。
平凡（trivial）、自由（free）拟阵是 \(k=0\) 和 \(n\) 时的特例。
线性拟阵（linear matroid）：元素为向量，\(X\) 独立当且仅当 \(X\) 中的向量线性独立。
有色拟阵（colorful matroid）：元素带颜色，\(X\) 独立当且仅当 \(X\) 中的颜色互不相同。
图拟阵（graphic matroid）：元素为无向图的边，\(X\) 独立当且仅当 \(X\) 中的边不成环。
划分拟阵（partition matroid）：元素被划分为 \(E_1, \dots, E_m\)，相应有 \(m\) 个自然数 \(d_1, \cdots, d_m\)。\(X\) 独立当且仅当 \(\forall i \in [1, m], |X \cup E_i| \le d_i\)。
均匀、有色拟阵都是它的特例。
截断拟阵（truncated matroid）：把一个拟阵的所有大小大于 \(k\) 的独立集删除，得到一个新的拟阵，称为截断拟阵。
部分拟阵：把一个拟阵的基集变成它的子集，只保留元素都在其中的独立集，得到一个新的拟阵，称为部分拟阵。
拟阵直和：两个基集不交的拟阵，如果交集不变，且其中元素不影响彼此的独立性，那么我们可以简单的把两个拟阵合并起来。如 \(M_1 = (E_1, \mathcal I_1), M_2 = (E_2, \mathcal I_2)\)，其并为 \(M = (E_1 \cup E_2, \mathcal I_1 \times \mathcal I_2)\)，\(\times\) 为集合的笛卡尔积。
Rado–Edmonds 算法
Rado–Edmonds 算法可以找到拟阵的一个基。
不带权时，尝试一个一个加入元素，最后就可以得到一个基。
带权时，先排序，再按上面的方法操作，即可得到权值最大 / 小的基。
拟阵交
有两个基集相同的拟阵，求在它们中都独立的最大集合。
交换图
对于拟阵和一个独立集 \(X\)，交换图 \(\mathcal D(X)\) 是一张二分图。当 \(X - x + y \in \mathcal I\) 时，连边 \((x, y)\)。
有引理：独立集 \(X\)、\(Y\)，\(|X|=|Y|\)，则 \(\mathcal D\) 中存在 \(X \setminus Y\) 和 \(Y \setminus X\) 间的完美匹配。
独立集 \(X\) 与集合 \(Y\)，\(|X|=|Y|\)，若 \(\mathcal D\) 中存在 \(X \setminus Y\) 和 \(Y \setminus X\) 间的唯一匹配，则 \(Y\) 独立。
增广路
对于两个拟阵 \(M_1 = (E_1, \mathcal I_1), M_2 = (E_2, \mathcal I_2)\) 和 \(X \in \mathcal I_1 \cap \mathcal I_2\)，交换图 \(\mathcal D(X)\) 是一张有向二分图。当 \(X - x + y \in \mathcal I_1\) 时，连边 \((y, x)\)；当 \(X - x + y \in \mathcal I_2\) 时，连边 \((y, x)\)。