\[ \DeclareMathOperator{\span}{span} \]
定义
拟阵 Matroid
给定全集 \(X\) 和 \(X\) 上的一个集族 \(\mathcal I\)，我们可以定义拟阵 \(\mathcal M = \langle X, \mathcal I \rangle\)。
对 \(I \in \mathcal I\)，称 \(I\) 是一个独立集。
以及要求有以下性质：
\(X\) 是有穷集合。
（遗传性）\(I' \subseteq I \in \mathcal I \implies I' \in \mathcal I\)。
（交换性）\(A, B \in I \land |A| < |B| \implies \exists\, x \in B \setminus A, A \cup \{x\} \in I\)。
基 Basis
拟阵 \(\mathcal M\) 的基 \(\mathcal B\) 是所有极大独立集。由性质，显然同时也是所有最大独立集。
环 Circuit
拟阵 \(\mathcal M\) 的环是所有极小非独立集。
秩 Rank
拟阵 \(\mathcal M = \langle X, \mathcal I \rangle\) 有秩函数 \(r: 2^X \to \mathbb N\)，其中为 \(r(S)\) 为 \(S\) 的极大独立子集的大小。显然同时也是最大独立子集。
一些关键性质：
（有界性）\(0 \le r(S) \le |S|\)。
（单调性）\(T \subseteq S \implies r(T) \le r(S)\)。
（次模性）\(r(A) + r(B) \ge r(A\cup B) + r(A\cap B)\)。
关于次模性的证明，考虑 \(A \cap B\) 的一个基 \(Z\)，通过交换性我们可以找出 \(A \cup B\) 的一个基 \(Z_{AB} \supseteq Z\)，然后我们注意到 \((Z_{AB} \cap (A \setminus B)) \cup Z\) 是独立集，\(B \setminus A\) 同理，而显然 \(Z = Z_{AB} \cap A \cap B\)，因而命题得证。
不过笔者在网络上看到了另一种更直观的见解，就是将命题改写为
\[ A \subseteq B \implies r(A \cup \{x\}) - r(A) \ge r(B \cup \{x\}) - r(B) \]
\(x \in B\) 的情况是 trivial 的。对于 \(x \notin B\)，若右侧是 \(0\) 则命题成立，若右侧是 \(1\) 则表示 \(B \cup \{x\}\) 的所有基都包含 \(x\)，进一步由交换性得 \(B\) 的所有基都与 \(x\) 独立，因而左侧也为 \(1\)。
同时容易该命题与原先给出的命题等价，留作读者练习。
之所以说它直观，是因为这给出了一种类似「凸性」的性质，也就是集合越大的时候添加一个新元素的影响越小。
强基交换引理 Strong Basis Exchange Lemma
定义 \(\span(A) = \{x \in X \mid r(A \cup \{x\}) = r(A)\}\)。
性质 1
\[ A \subseteq B \implies \span(A) \subseteq \span(B) \]
证明：考虑 \(x \in \span(A)\)，有 \(0 = r(A \cup \{x\})-r(A)\ge r(B\cup \{x\}) - r(B)\)，因而 \(r(B \cup \{x\}) = r(B)\)。
性质 2
\[ x \in \span(A) \implies \span(A \cup \{x\}) = \span(A) \]
证明：只需考虑证明 \(\span(A \cup \{x\}) \subseteq \span(A)\)。考虑 \(y \in \span(A \cup \{x\})\)，我们有 \(0 = r(A\cup\{x\}) - r(A) \ge r(A\cup\{x,y\})-r(A\cup\{y\})\)，因而 \(r(A\cup\{y\}) = r(A\cup\{x,y\}) = r(A\cup \{x\}) = r(A)\)。
性质 3
\(\span(\span(A)) = \span(A)\)。
引理
对于 \(B, B' \in \mathcal B\) 且 \(B \ne B'\)，\(\forall\, x \in B \setminus B'\)，\(\exists\, y \in B' \setminus B\) 使得 \(B \setminus \{x\} \cup \{y\} \in \mathcal B\) 且 \(B' \setminus \{y\} \cup \{x\} \in \mathcal B\)。
证明：考虑 \(x \in B \setminus B'\)，易知 \(B' \cup \{x\}\) 包含一个环 \(C \ni x\)。
因而我们有 \(x \in \span(C \setminus \{x\})\)，于是 \(x \in \span((B\cup C) \setminus \{x\})\)，从而 \(\span((B\cup C) \setminus \{x\}) = \span(B \cup C) = X\)。
因而 \(\exists\, B'' \subseteq (B \cup C) \setminus \{x\}, B'' \in \mathcal B\)，且 \(|B''| > |B\setminus \{x\}|\)。由交换性得 \(\exists\, y \in B'' \setminus (B \setminus \{x\}), (B \setminus \{x\}) \cup \{y\} \in \mathcal B\)。
而 \(B'' \setminus (B \setminus \{x\}) \subseteq (B \cup C) \setminus \{x\} \setminus (B \setminus \{x\}) \subseteq C \setminus \{x\}\)，结合上一行即 \(\exists\, y \in C \setminus \{x\}, (B \setminus \{x\}) \cup \{y\} \in \mathcal B\)。
同时由于 \(C\) 是一个环，也有 \((B' \setminus \{y\}) \cup \{x\} \in \mathcal B\)。
独立性谕示 Independence Oracle
拟阵相关的很多算法需要在一些特殊条件下高效判定独立性。
常见拟阵
省略一些证明。当然，其中有一些由于独立性谕示较为困难，在应用中并不常见。
均匀拟阵 Uniform Matroid
\(\mathcal I = \{I \subseteq 2^X \mid |I| \le k\}\)。
\(k=0\) 称为 Trivial Matroid。\(k=|X|\) 称为 Complete Matroid。
划分拟阵 Partition Matroid
给定 \(X\) 的一组划分 \(X_1, X_2, \dots, X_m\) 以及参数 \(d_1, d_2, \dots, d_m\)，\(I \in \mathcal I\) 当且仅当 \(|I \cap X_i| \le d_i\)。
\(d_i=1\) 称为有色拟阵 Colorful Matroid。
图拟阵 Graphic Matroid
对于 \(G = (V, E)\)，取 \(X = E\)，\(I \in \mathcal I\) 当且仅当 \(I\) 的导出子图无环。
基环拟阵 Bicircular Matroid
对于 \(G = (V, E)\)，取 \(X = E\)，\(I \in \mathcal 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 \in B \setminus A\) 使得 \(A \cup \{x\} \in \mathcal I\)，则由最小有 \(w(A) \le w(B \setminus \{x\})\) 和 \(w(B) \le w(A \cup \{x\})\)。
在第一个式子中左右两边同时加入 \(x\) 有 \(w(A \cup \{x\}) \le w(B)\)。因此 \(w(A \cup \{x\}) = w(B)\)。
这说明带权的情况我们依然可以应用交换性，每次加入最小权的可加入的元素即可。
拟阵交
例子就省略了。值得注意的是，Hamilton 回路问题是三个拟阵的交。
交换图
对 Strong Basis Exchange Lemma 加以推广（即在截断拟阵上应用），可知相同大小的独立集之间也是可以交换的。
对于 \(S \in \mathcal I\)，定义二分图 \(\mathcal D(S)\)，其中 \((x, y)\) 有边当且仅当 \(x \in S, y \in X \setminus S, S \setminus \{x\} \cup \{y\} \in \mathcal I\)。
引理
对于两个独立集 \(|S|=|T|\)，\(\mathcal D(S)\) 存在 \(S \setminus T\) 和 \(T \setminus S\) 的完美匹配。
证明：将拟阵的独立集截断到 \(|S|\)，考虑 \(x \in T \setminus S\)，由 Strong Basis Exchange Lemma，\(\exists\, y \in T \setminus S\) 使 \(S \setminus \{x\} \cup \{y\}, T \setminus \{x\} \cup \{y\}\) 都是独立集。
因而 \((y, x)\) 一定是 \(\mathcal D(S)\) 的一条边。
从而我们令 \(T \gets T \setminus \{x\} \cup \{y\}\) 即可一直归纳。
引理
对于独立集 \(S\) 和集合 \(T\) 满足 \(|S|=|T|\)，若 \(\mathcal D(S)\) 中存在 \(S \setminus T\) 到 \(T \setminus S\) 的唯一匹配，则 \(T\) 是独立集。
不想证了，放两个图：
未完待续。