最后更新: 2025-01-22 10:13 查看: 212 次纠错评论(0) 课件开VIP

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$ 的一个最大匹配。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：二分图的匹配

下一篇：独立集、覆盖

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