最后更新: 2025-01-22 10:13 查看: 43 次反馈刷题

Hall定理

Edmonds 于 1965 年提出了一种利用增广路求二分图最大匹配的有效算法——匈牙利算法。该算法提出的问题背景是任务安排：设有 $m$ 个人，$n$ 项任务，能不能适当地安排，使得每个人都有工作做？显然，可以将 $n$ 和 $m$ 作为两个互补的顶点集。当 $n<m$ 时，答案是否定的，即使 $n \geqslant m$ 也不一定。但经验告诉我们，当 $m$ 个人适应工作的能力愈强（即与 $m$ 个点邻接的点集 $p[m]$ 愈大）时，愈容易做到这一点。Hall 定理则定量地回答了这个问题。

定理 11.9 （Hall定理）对于二分图 $G\left(V_1, V_2\right)$ ，存在一匹配 $M$ ，使得 $V_1$ 的所有顶点关于
$M$ 饱和的充要条件是：对 $V_1$ 的任一子集 $A$ ，和 $A$ 邻接的点集为 $p[A]$ ，恒有：

$$
|p[A]| \geqslant|A|
$$

证明：必要性：存在一个匹配 $M$ ，使得 $V_1$ 关于 $M$ 饱和。 $|P[A]| \geqslant|A|$ 的直观意义是显然的。例如安排工作，要使得每个人至少有一项彼此不同的工作可做，不论多少人，他们能做的工作数目必须不少于人数。

充分性：若对于任何 $A \subseteq V_1$ 恒有 $|P[A]| \geqslant|A|$ ，则可以按下列方法作出匹配 $M$ ，使得 $V_1$ 关于 $M$ 饱和。

先作任意一初始匹配，若已使 $V_1$ 关于 $M$ 饱和，则定理已证。如若不然，则 $V_1$ 中至少有一点 $x_0$ 为未盖点，则从 $x_0$ 出发，检查从 $x_0$ 出发，终点在 $V_2$ 的交错路。可能有下列两种情况发生。
（1）没有任何一条交错路可以到达 $V_2$ 的未盖点。这时由于从 $x_0$ 点开始的一切交错路终点还是在 $V_1$ ，故存在 $V_1$ 的子集 $A$ 有：$|P[A]|<|A|$ 。这与假设相矛盾，所以这种情形是不可能的。
（2）存在一条从 $x_0$ 出发的交错轨，终点为 $V_2$ 集合中的未盖点，则这条道路便是可增广路。因而可以改变一下匹配使 $x_0$ 点为盖点。

重复以上的过程，就可以找出匹配 $M$ ，使得 $V_1$ 关于 $M$ 饱和。定理的充分性得到证明。
匈牙利算法就是根据充分性证明中的思想提出来的。具体实现方法是构造一棵树。
取 $G$ 的一个未盖点作为树根，它位于树的第 0 层。设已经构造好了树的第 $i-1$ 层，现在要构造第 $i$ 层。当 $i$ 为奇数时，将那些关联于第 $i-1$ 层中一个顶点且不属于 $M$ 的边，连同该边关联的另一个顶点一起添加到树上。当 $i$ 为偶数时，则添加那些关联于第 $i-1$ 层的一个顶点且属于 $M$ 的边，连同该边关联的另一个顶点。如果在上述构造树的过程中，发现一个未盖点被作为树的奇数层顶点，则这棵树上从树根到顶点 $v$ 的路径就是一条关于 $M$ 的增广路；如果在构造树的过程中，既没有找到增广路，又无法按要求往树上添加新的边和顶点，则可以在余下的顶点中再取一个未匹配顶点作树根，构造一棵新的树。这个过程一直进行下去，如果最终仍未得到任何增广路，就说明 $M$ 已经是一个最大匹配了。

例如，图 11.7 （a）中取未盖点 $t_5$ 作为树根，顶点 $c_1$ 是树上第一层中唯一的顶点，未匹配边 $\left(t_5, c_1\right)$ 是树上的一条边。顶点 $t_2$ 处于树的第二层，边 $\left(c_1, t_2\right)$ 属于 $M$ 且关联于 $c_1$ 边，也是树上的又一条边。顶点 $c_5$ 是未盖点可以添加到第三层。至此我们找到了一条增广路 $p=t_5 c_1 t_2 c_5$ 。由此增广路得到图 $G$ 的一个更大的匹配 $M \oplus p$ ，如图（b）所示。此时，$M \oplus p$ 是一个完全匹配，从而也是 $G$ 的一个最大匹配。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：二分图的匹配

下一篇：独立集、覆盖

本文对您是否有用？有用 (0) 无用 (0)