拟阵

拟阵（matroid）是在有限集合上抽象“可以继续保持独立的选择”的数学结构。它保留了线性独立向量和无环边集共有的两条规律：独立对象删去一些成员仍独立；两个独立集大小不同时，较小者能从较大者借来一个元素继续扩充。第二条规律比“没有冲突”更强。

例如，要从三个互不重叠的组 $R=\{r_1,r_2\}$、$B=\{b_1,b_2\}$、$G=\{g\}$ 中选择代表，每组最多选一人。$\{r_1,b_2\}$ 合法，$\{r_1,r_2\}$ 不合法。若已有 $\{r_1\}$，另一个合法方案是 $\{r_2,b_1,g\}$，虽不能再加入 $r_2$，却可以加入 $b_1$ 或 $g$。拟阵要求这种可扩充性对每一对独立集成立。

独立集公理

设 $E$ 是有限底集，$ℐ\subseteq 2^E$ 是指定的独立集族。二元组 $M=(E,ℐ)$ 是拟阵，当且仅当满足：

• $\varnothing \in ℐ$；
• 若 $J\in ℐ$ 且 $I\subseteq J$，则 $I\in ℐ$，称为遗传性；
• 若 $I,J\in ℐ$ 且 $|I|<|J|$，则存在 $e\in J\setminus I$，使 $I\cup \{e\}\in ℐ$，称为增广公理。

开头的分组选择确实满足这些公理。遗传性来自“每组至多一个”。若 $|I|<|J|$，把两个大小写成各组人数之和，必有一组中 $J$ 选了一个而 $I$ 没选；加入这个代表不违反任何组的限制。这也说明分组必须互不重叠，才能直接使用上述论证。这种结构称为分划拟阵；每组容量也可推广为非负整数。

基是按包含关系极大的独立集，即不能再加入底集中任何新元素的独立集。“极大”描述不能向外扩充，“最大”描述大小达到全局上界，两者通常不同，但在拟阵中一致。

基等大定理。 拟阵的所有基都有相同的大小。证明：若两个基 $B,C$ 满足 $|B|<|C|$，增广公理提供一个 $e\in C\setminus B$ 使 $B+e$ 独立，与 $B$ 极大矛盾。互换两者也不能有反向严格不等式，故大小相同。有限性保证任何独立集都能不断加元素，直到某个基为止。对任意 $A\subseteq E$ 限制可选元素，同样的公理仍成立，因此 $A$ 内所有极大独立集也等大；这个数就是秩 $r(A)$。

线性独立中的同一种交换

取实平面向量 $a=(1,0)$、$b=(2,0)$、$c=(0,1)$。底集是三个带标签的向量，独立集按线性代数定义。两组基是 $\{a,c\}$ 和 $\{b,c\}$；$\{a,b\}$ 相关，因为 $b=2a$，三个向量一起也相关。这里元素 $a,b$ 不相同，即使它们指向相同方向，也不能把底集标签合并。

a 与 b 只能贡献一个方向；加入 c 才得到第二个独立方向。

线性独立为何满足增广公理？设 $I,J$ 对应独立向量组且 $|I|<|J|$。若 $J\setminus I$ 中每个向量都在 $\mathrm{span}(I)$ 内，那么 $J$ 全部在一个维数为 $|I|$ 的空间里，不可能含 $|J|$ 个独立向量。因此至少一个向量不在该张成空间内，将它加入 $I$ 仍独立。这给出了公理与原来线性代数对象之间的具体联系。

变式。 再加入 $d=(1,1)$，列出全部二元素基。答案是 $\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}$。除 $\{a,b\}$ 外，各对行列式分别非零；平面中三个向量必相关，所以这些二元素独立集已经极大。

遗传性不足以保证拟阵

四个顶点组成路径 $1-2-3-4$，把“不共享端点的边集”作为合法选择。它具有遗传性，但 $I=\{23\}$、$J=\{12,34\}$ 都合法，且 $|I|<|J|$；把 $12$ 或 $34$ 加到 $I$ 都与 $23$ 共享端点。这是增广失败的具体位置。于是不能把任意资源冲突问题直接当作一个拟阵，也不能把“选不进去了”直接当作“已选得最多”。此类双侧端点约束可用拟阵交表达。

图拟阵把无向图的森林作为独立边集；多拟阵则把一件元素是否入选推广为可分配的非负数量。前者改变独立性的具体来源，后者改变可行对象的类型，二者都以本篇的交换结构为参照。