最大拟阵交

求两个拟阵的最大公共独立集;在交换图上找增广路,二部匹配是两个划分拟阵的交。

标签 数学 / 拟阵 / 拟阵交 / 匹配 / 增广路

模型

设 𝑀1=(𝐸,ℐ︀1)、𝑀2=(𝐸,ℐ︀2) 是同一底集上的两个拟阵。最大拟阵交问题是求

max{|𝐼|:𝐼∈ℐ︀1∩ℐ︀2}.

公共独立集族一般不是拟阵。

Edmonds–Lawler 算法

Edmonds–Lawler 算法适用于任意两个拟阵,求最大公共独立集。从 𝐼=∅ 开始,重复:

  1. 建交换图 𝐷𝐼。顶点集为 𝐸,每轮 𝐼 改变后重建。记

    𝑆1(𝐼)={𝑦∈𝐸∖𝐼:𝐼∪{𝑦}∈ℐ︀1},𝑆2(𝐼)={𝑦∈𝐸∖𝐼:𝐼∪{𝑦}∈ℐ︀2}.

    称 𝑆1(𝐼) 为源集,𝑆2(𝐼) 为汇集。对 𝑦∈𝐸∖𝐼,若 𝑦∉𝑆1(𝐼),令 𝐶1(𝑦) 为 𝑦 关于 𝐼 的基本回路,并对每个 𝑥∈𝐶1(𝑦)∖{𝑦} 连 𝑦→𝑥;若 𝑦∉𝑆2(𝐼),令 𝐶2(𝑦) 为 𝑦 关于 𝐼 在 𝑀2 中的基本回路,并对每个 𝑥∈𝐶2(𝑦)∖{𝑦} 连 𝑥→𝑦。从 𝑆1(𝐼) 到 𝑆2(𝐼) 的有向路称为增广路;按弧数最短的一条称为最短增广路。

  2. 若不存在增广路,停止,𝐼 是最大公共独立集。
  3. 取最短增广路,将 𝐼 与路径顶点取对称差,|𝐼| 增加 1。

其中 𝑦→𝑥 表示在 𝑀1 中加入 𝑦 必须先删去回路中的 𝑥,𝑥→𝑦 表示在 𝑀2 中删去 𝑥 后才能加入 𝑦。

这里是无权最大基数版本;带权版本使用带权增广或权重拆分。

二部匹配

设 𝐺=(𝐿,𝑅,𝐸) 是 二分图匹配 中的二分图。对每个 𝑢∈𝐿,令 𝐸𝑢 为与 𝑢 关联的边集;对每个 𝑣∈𝑅,令 𝐸𝑣 为与 𝑣 关联的边集。定义

ℐ︀𝐿={𝐼⊆𝐸:|𝐼∩𝐸𝑢|≤1(𝑢∈𝐿)},ℐ︀𝑅={𝐼⊆𝐸:|𝐼∩𝐸𝑣|≤1(𝑣∈𝑅)}.

这两族都是容量为 1 的划分拟阵。公共独立集在每个左右端点上都至多取一条边,恰为 𝐺 的匹配。因此最大匹配就是两个划分拟阵的最大公共独立集。

此时交换图的源是左端点未匹配的边,汇是右端点未匹配的边,增广路就是匹配的交替增广路。

源码位置