形式陈述

有限拟阵是二元组 $M=(E,\mathcal I)$$M=(E,\mathcal{I})$，其中 $E$$E$ 为有限底集，$\mathcal I\subseteq2^E$$\mathcal{I}\subseteq 2^E$ 为独立集族，满足：

1. $\varnothing\in\mathcal I$$\varnothing \in \mathcal{I}$；
2. 若 $I\in\mathcal I$$I\in \mathcal{I}$ 且 $J\subseteq I$$J\subseteq I$，则 $J\in\mathcal I$$J\in \mathcal{I}$；
3. 若 $I,J\in\mathcal I$$I,J\in \mathcal{I}$ 且 $|I|<|J|$$|I|<|J|$，则存在 $e\in J\setminus I$$e\in J\setminus I$ 使 $I\cup\{e\}\in\mathcal I$$I\cup \{e\}\in \mathcal{I}$。 极大独立集称为基，交换公理保证所有基等势；其大小为秩。秩函数

$$ r(X)=\max\{|I|:I\subseteq X,\ I\in\mathcal I\} $$$$r(X)=max\{|I|:I\subseteq X,I\in \mathcal{I}\}$$

满足单调性、$0\le r(X)\le|X|$$0\le r(X)\le |X|$ 和次模性。图拟阵的独立集是无圈边集，向量拟阵的独立集是线性无关列集。

直觉

拟阵抽取线性无关与森林共享的交换结构。交换公理保证局部扩张不会把基大小带向不同终点，从而贪心选择具有全局意义。

例子与边界

图 $G$$G$ 的拟阵基是各连通分量生成树的并；矩阵列向量给出可表示拟阵。均匀拟阵 $U_{r,n}$$U_{r,n}$ 把所有大小至多 $r$$r$ 的子集视为独立。任意遗传集合系统未必是拟阵，失败点通常是交换公理。拟阵贪心定理称：对任意权重，按权重降序加入仍保持独立的元素可得到最大权基；反过来，所有权重下贪心正确刻画拟阵。这里采用有限拟阵；无限拟阵需要增强的极大性/交换公理，不能只原样使用有限基数比较。拟阵独立不等于概率独立。

推论与应用

拟阵统一最小生成树、线性基选择、横截结构和组合优化中的贪心可解性。

参考资料

• James Oxley, Matroid Theory, 2nd ed., Oxford University Press, 2011，Chs. 1–2, matroid axioms, bases, rank, and examples。
• J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001，Ch. 13, matroids and greedy algorithms。