匈牙利算法简证

__ryp__ · 2024-05-25 16:41:23 · 个人记录

简单描述一下匈牙利算法：

首先设 m_u 表示每个点的匹配。

尝试对每个点 u 进行匹配，对每一个 (u, v) \in E：

• 如果 v 未匹配就直接匹配；

• 否则，尝试重新匹配 m_v；如果成功，那么 (u, v) 相配；否则失配，继续找下一个 v。

注意到这个过程就是找增广路的过程。第一种情况中的增广路是 u \to v；第二种情况中，若设 m_v 的新匹配是 m_v'，那么增广路是 u \to v \to m_v \to m_v'。

不难注意到，两种情况都使整体匹配数加一，故一个最大匹配中一定是没有增广路的。

再证充分性。

充分性太难了不好证 但是分讨可以证