最大拟阵交
求两个拟阵的最大公共独立集;在交换图上找增广路,二部匹配是两个划分拟阵的交。标签 数学 / 拟阵 / 拟阵交 / 匹配 / 增广路
模型
设 、 是同一底集上的两个拟阵。最大拟阵交问题是求
公共独立集族一般不是拟阵。
Edmonds–Lawler 算法
Edmonds–Lawler 算法适用于任意两个拟阵,求最大公共独立集。从 开始,重复:
建交换图 。顶点集为 ,每轮 改变后重建。记
称 为源集, 为汇集。对 ,若 ,令 为 关于 的基本回路,并对每个 连 ;若 ,令 为 关于 在 中的基本回路,并对每个 连 。从 到 的有向路称为增广路;按弧数最短的一条称为最短增广路。
- 若不存在增广路,停止, 是最大公共独立集。
- 取最短增广路,将 与路径顶点取对称差, 增加 。
其中 表示在 中加入 必须先删去回路中的 , 表示在 中删去 后才能加入 。
这里是无权最大基数版本;带权版本使用带权增广或权重拆分。
二部匹配
设 是 二分图匹配 中的二分图。对每个 ,令 为与 关联的边集;对每个 ,令 为与 关联的边集。定义
这两族都是容量为 的划分拟阵。公共独立集在每个左右端点上都至多取一条边,恰为 的匹配。因此最大匹配就是两个划分拟阵的最大公共独立集。
此时交换图的源是左端点未匹配的边,汇是右端点未匹配的边,增广路就是匹配的交替增广路。