拟阵交定理

形式陈述 ​

设 $M_1=(E,{\mathcal{I}}_1)$ 与 $M_2=(E,{\mathcal{I}}_2)$ 是同一有限底集上的两个拟阵，秩函数分别为 $r_1,r_2$。Edmonds 拟阵交定理断言

$$\boxed{{\displaystyle max\{|I|:I\in {\mathcal{I}}_1\cap {\mathcal{I}}_2\}=\underset{U\subseteq E}{min}(r_1(U)+r_2(E\setminus U)).}}$$

上界对任意共同独立集 $I$ 与任意 $U\subseteq E$ 都成立，因为

$$|I|=|I\cap U|+|I\cap (E\setminus U)|\le r_1(U)+r_2(E\setminus U).$$

难点是证明某个切分能达到最大共同独立集的大小。

证明骨架使用交换图。给定共同独立集 $I$，在 $E$ 上建立有向图：若 $x\in I,y\notin I$ 且 $I-x+y\in {\mathcal{I}}_1$，加弧 $x\to y$；若同一交换在 $M_2$ 中保持独立，加弧 $y\to x$。源点是满足 $I+y\in {\mathcal{I}}_1$ 的 $y\notin I$，汇点是满足 $I+y\in {\mathcal{I}}_2$ 的 $y\notin I$。一条最短源–汇有向路通过交替交换把 $I$ 增广为大小 $|I|+1$ 的共同独立集，正确性由基本回路公理库拟阵回路Matroid circuit · Circuit of a matroid拟阵中按包含关系极小的依赖集，是独立性首次失效的局部证书。消去保证。

若不存在增广路，令 $R$ 为从所有源点可达的顶点集。交换性质推出

$$r_1(E\setminus R)=|I\setminus R|,r_2(R)=|I\cap R|.$$

取 $U=E\setminus R$，右侧秩和正好等于 $|I|$，从而给出与当前共同独立集同值的上界证书。反复增广直到无路，即证明极小极大公式。

直觉 ​

共同独立集必须同时支付两套独立性预算。任意切分 $U\bigsqcup (E\setminus U)$ 后，落在 $U$ 的元素至多占用 $M_1$ 的 $r_1(U)$ 个独立位置，另一侧至多占用 $M_2$ 的 $r_2(E\setminus U)$ 个位置，所以每个切分都给上界。定理的力量在于：总有一个切分把这个显然上界压到恰好可达。

交换图是增广路思想的拟阵版本。单次加入可能在两个拟阵中分别制造回路；沿路径交替删换元素，可以把一边修好的独立性传递到另一边，直到找到同时可加入的终点。无路时，可达与不可达区域反过来形成秩证书。

例子与边界 ​

在二分图 $G=(L\bigsqcup R,E)$ 的边集上，令 $M_1$ 是按左端点分组、每组至多取一条边的分割拟阵，$M_2$ 对右端点作同样限制。共同独立集恰是匹配，所以二分图最大匹配是拟阵交的特例。对边 $ax,bx$（$L=\{a,b\},R=\{x\}$），最大共同独立集大小为 $1$；取 $U=\varnothing$，有 $r_1(U)+r_2(E)=0+1$，min–max 两侧相等。

共同独立集族通常不是拟阵。四顶点路径的三条边记为 $e_1,e_2,e_3$；匹配 $\{e_2\}$ 与 $\{e_1,e_3\}$ 都共同独立，但无法从后者选一条加入前者而保持匹配，违反拟阵交换公理。因此不能把 ${\mathcal{I}}_1\cap {\mathcal{I}}_2$ 当成第三个拟阵并直接使用普通贪心。

公式中的第二项必须是 $r_2(E\setminus U)$。若误写成 $r_2(U)$，切分就不再覆盖共同独立集的两部分，连显然上界都无法推出。有限性也用于增广算法终止和基数 min–max；无限拟阵交需要额外公理与不同定理。

推论与应用 ​

交换图算法每次把共同独立集增大一，最终同时产出一个最大解和集合 $U$ 的最优性证书。二分图匹配中的交替路与顶点覆盖对偶由此成为同一增广–证书结构的具体表现；增广路公理库增广路Augmenting path相对于当前匹配，边在未匹配与已匹配之间交替且两个端点均未匹配的路径。不再局限于图上的顶点序列，而由两套拟阵交换关系生成。

拟阵交还描述同时满足图森林约束、分组容量约束或线性无关约束的选择问题。加权拟阵交允许元素带权并优化共同独立集的总权值，但需要势函数、最短路或线性规划等更强算法；它不是把本页无权增广证明中的“大小”机械替换成“权重”。

参考资料

• Jack Edmonds, “Matroid Intersection,” Annals of Discrete Mathematics 4 (1979), 39–49.
• Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003, chapters on matroid intersection.