二分匹配 vs 稳定匹配

二分匹配追求匹配边数最大化，稳定匹配追求匹配的稳定性（无阻隔对），两者目标不同、算法不同，但都建立在二部图的结构之上。

共同点

二分匹配和稳定匹配在概念上互补，但关注点截然不同：

二分匹配是纯组合优化问题——只关心”能匹配多少对”，不关心匹配的质量或参与者的偏好。其核心工具是增广路径（Berge定理），算法通过反复寻找增广路径来扩大匹配。

稳定匹配引入了偏好这一博弈论要素——不仅要求匹配是完美的，还要求匹配是”自执行的”（没有人有动力偏离）。Gale-Shapley算法通过”延迟接受”机制实现稳定性，其深刻性质（求婚方最优、被求婚方最劣）揭示了匹配市场中的权力不对称。

值得注意的是，稳定匹配不一定是最大匹配（虽然稳定匹配一定是完美匹配，在 $n$ 对参与者中边数为 $n$ ），而最大匹配不一定稳定（即使存在完美匹配，也可能存在阻隔对）。两者的目标正交：一个追求”数量”，一个追求”质量”。

在实际应用中，两种匹配问题常常需要综合考虑。例如，在住院医师匹配（NRMP）中，既要保证稳定性（Gale-Shapley），又要考虑医院配额（多对一匹配的推广），还需要处理不完全偏好列表等实际问题。