拟阵交算法

形式陈述 ​

Oracle 模型与目标 ​

给定同一有限底集 $E$ 上的两个拟阵

以及独立性 oracle：输入 $X\subseteq E$，返回 $X\in {\mathcal{I}}_j$ 与否。无权拟阵交要找最大公共独立集；其最优性证书最终以两个拟阵的秩与闭包理路拟阵的秩与闭包Matroid rank · Matroid closure · Matroid flat证明有限拟阵秩的子模性及秩公理的逆向重建，由此推出闭包交换，并用同一个四列矩阵计算秩、平坦与依赖证书。刻画。目标写为

算法从 $I=\varnothing$ 开始，每轮构造交换图并增广一次；至多增广 $r\le |E|$ 次，其中 $r$ 是最优公共独立集大小。记 $N=|E|$。若当前 $|I|=k$，朴素实现枚举 $I\times (E\setminus I)$ 中的交换对，并询问每个外部元素能否直接加入两侧拟阵。因此一轮需要 $O((k+1)N)$ 次 oracle 调用；其中的 $N$ 项也覆盖初始空集的源、汇判定。计入最终找不到增广路的证书搜索，对 $k=0,1,\dots ,r$ 求和，得到

次独立性查询和同阶的附加图搜索工作。这里可用成员位数组表示查询集合，临时改动至多两个位置、查询后恢复；若接口要求每次显式复制整个集合，还须另计复制成本。若一次 oracle 成本至多为 $T_{\mathrm{ind}}$，总时间为 $O((r+1{)}^{2}N(T_{\mathrm{ind}}+1))$。$N=0$ 时直接返回空集。基本回路、rank oracle 与 Cunningham 型算法能改善查询界，本页固定可直接核验的朴素实现。若元素标识和图索引各占一个机器字，以邻接表显式保存当前交换图需要 $O((r+1)N)$ 个存储字，BFS、成员数组及源汇标记另需 $O(N)$ 个字；每轮可复用这些空间，oracle 自身的工作空间另计。

交换有向图的方向 ​

固定当前公共独立集 $I$。交换图 $D_I$ 的顶点是底集 $E$，并在 $I$ 与 $E\setminus I$ 之间加两类方向相反的弧。对 $a\in I,b\notin I$：

源集合与汇集合为

因此一条 $S_I$ 到 $T_I$ 的路从外部元素开始，先沿 $M_2$ 弧进入 $I$，再沿 $M_1$ 弧离开，如此交替。交换图弧方向只是约定，但 sources、sinks 和后续证明必须与约定一致；交换其中一类方向却不交换端点集合会破坏增广语义。

最短增广路与对称差 ​

若 $b\in S_I\cap T_I$，长度零的路径直接把 $b$ 加入 $I$。否则从全部 $S_I$ 顶点同时启动广度优先搜索理路广度优先搜索Breadth-first search · BFS按无权距离分层访问可达顶点的图遍历算法。，在 $D_I$ 中找一条最短的 $S_I$–$T_I$ 路

其中 $b_j\notin I,a_j\in I$。令

外部顶点比内部顶点多一个，所以 $|I^{\prime }|=|I|+1$。真正需要证明的是 $I^{\prime }$ 同时属于 ${\mathcal{I}}_1,{\mathcal{I}}_2$。

最短性使这些单元素交换能够按次序合并。先用一个基本回路理路拟阵回路Matroid circuit · Circuit of a matroid拟阵中按包含关系极小的依赖集，是独立性首次失效的局部证书。事实：若 $I$ 独立而 $I+b$ 依赖，其中有唯一回路 $C(b,I)$；否则消去两条回路共有的 $b$，会在 $I$ 内产生回路。且 $I-a+b$ 独立恰当且仅当 $a\in C(b,I)\setminus \{b\}$。

在 $M_1$ 中，$I+b_0$ 独立。对 $j\ge 1$，$b_j$ 不是源，否则从它开始的路径更短；故 $I+b_j$ 有基本回路 $C_j$。弧 $a_j\to b_j$ 保证 $a_j\in C_j$。若 $C_j$ 含某个 $a_i$，$i<j$，就有弧 $a_i\to b_j$ 跳过路径的一段，与最短性矛盾。因此 $C_j$ 避开此前的 $a_1,\dots ,a_{j-1}$。

从独立集 $I+b_0$ 出发，依次对 $j=1,\dots ,k$ 加入 $b_j$、删去 $a_j$。归纳假设当前集合独立；原来的 $C_j$ 仍包含在当前集合加 $b_j$ 中，因此正是这次加入产生的唯一回路。删去其中的 $a_j$ 即恢复独立。最后得到 $I^{\prime }$。在 $M_2$ 中反向进行：先加入可直接加入的 $b_k$，再按 $j=k,\dots ,1$ 加入 $b_{j-1}$、删去 $a_j$；最短性排除弧 $b_{j-1}\to a_i$（$i>j$），同一论证成立。故 $I^{\prime }$ 在两个拟阵中都独立。

无增广路时的最优性证书 ​

若从 $S_I$ 无法到达 $T_I$，令 $R$ 为交换图中从 $S_I$ 可达的全部元素。交换闭包性质推出

具体地，对 $b\in (E\setminus I)\setminus R$，它不是 $M_1$ 的源，所以有基本回路 $C_1(b,I)$。该回路不含 $I\cap R$ 中的元素，否则相应弧 $a\to b$ 会使 $b$ 可达。因此 $b$ 属于 $I\setminus R$ 在 $M_1$ 中的闭包，给出第一式。

对 $b\in R\setminus I$，它不是 $M_2$ 的汇，所以有基本回路 $C_2(b,I)$。回路中的每个旧元素 $a$ 都有弧 $b\to a$，因而属于 $I\cap R$。于是整个 $R$ 包含于 $I\cap R$ 在 $M_2$ 中的闭包，给出第二式。两式的反向秩不等式则来自相应的独立子集。

取 $U=E\setminus R$，得到

另一方面，任意公共独立集 $J$ 都满足

所以当前 $I$ 已最优，$U$ 同时给出 拟阵交 min–max 定理理路拟阵交定理Matroid intersection theorem · Edmonds matroid intersection theorem两个有限拟阵的最大共同独立集大小，等于一次底集切分上的两侧秩之和的最小值。的等值证书。算法不是在“找不到路”时凭经验停止，而是产出可验证上界。