§8.3 Hall定理
设有m个人，n项工作，每个人会做其中的若
干项工作，能不能适当安排，使得每个人都有工
作做？
w1
w2 w3
w4
w5
m1 m2
m3
m4
当m>n时，肯定是不可能的，即使是 m≤n也不一定。但如果每个人能做的工作 越多，越容易实现。
w1
w2 w3
w4
w5
m1 m2
m3
m4
w1
w2 w3
48
§3 匈牙利算法
1965年，匈牙利著名数学家 Edmonds设计了一种求最大匹配的算法， 称为匈牙利(Hungarian)算法。
求最大匹配常用匈牙利算法，在图中求最大 匹配的关键是寻找M-可扩充路。它的基本思想是： 通常是先构造一个匹配M，再看图中有没有不饱 和点。 如果没有，那么肯定是最大匹配了，如果 有，从图中的任一选定的非饱和点出发，用标号 法寻找增广链。如果找到增广链，则就可以得到 增广；否则从图中另一个非饱和点出发，继续寻 找增广链。重复这个过程直到G中不存在增广链 结束，此时的匹配就是G的最大匹配。这个算法 通常称为匈牙利算法.
H=G[MM’] (边导出子图)。 任取vH，d(v)为1或2。∴H的每个连通分支是一条 M’边和M边交错出现的通路或偶数长度的回路。∵|M’| ＞|M|，∴H包含M’的边多于M的边，从而必有一个连 通分支P中的M’边多于M边。∴P是开始边和终止边都是 M’边通路，即M–可增广路。矛盾。故M为最大匹配。
(1)边在M1和M2中交错出现的偶圈. (2)边在M1和M2中交错出现的路.
一个匹配
f1
f2
f3
f4
f5
m1 m2
m3
m4
m5
另一个匹配
f1
f2
f3
f4
f5
m1 m2
m3
m4
m5
f1 f2 f3 f4 f5 • 环合是交错道路
f1 f2 f3 f4 f5 m1 m2 m3 m4 m5 f1 f2 f3 f4 f5
推论：若G是k (k>0)正则偶图，则G存在完美匹配。
证明：一方面，由于G是k (k>0)正则偶图,所以k|X|=k|Y|, 于是得|X| = |Y|；
另一方面，对于X的任一非空子集S, 设E1与E2分别是与S 和N(S)关联的边集，显然 有：E1 E2 即：
E 1 kSE 2 kN (S )
由Hall定理，存在由X到Y的匹配.又|X| = |Y|，所以G存在 完美匹配。
46
(5) Hall (1904---1982) 英国人， 20世纪最伟大的数学家之一。 主要功绩是在代数学领域。在 剑桥大学工作期间，主要研究 群论，1932年发表的关于素数 幂阶群论文是他最有名的工作。 匹配定理是他1935年在剑桥大 学做讲师时发表的结果。Hall 是一名雅致的学者，对学生特 别友好，当他觉得有必要批评 学生时，他都会以一种十分温 和的方式建议他们改正。
具体问题描述：
有n个女士和n个男士参加舞会，每位女士与其中若干 位男士相识，每位男士与其中若干位女士相识，问如何安 排，使得尽量多配对的男女舞伴相识。
f1
f2
f3
f4
f5
m1
m2
m3
m4
m5
下图就是一种分配方法：
f1
f2
f3
f4
f5
m1
m2
m3
m4
m5
下图是一种分配方法吗？
f1
定理(1935)： 二部图G=（X，Y）存在一匹配M，使
得X的所有顶点关于M饱和的充要条件是：对 于X任一子集S，及与S邻接的点集为N(S)， 恒有：
|N(S)|≥|S|。
(2) Hall定理也可表述为：设G=(X,Y)是偶图，如果存在 X的一个子集S,使得|N(S)| < |S| ，那么G中不存在由X到Y的 匹配。
v8
这是最大匹配而不是完 美匹配。此图尽管是偶 数个顶点却无完美匹配
推论1.设G是k(>0)正则二部图,则G有完美匹配. 推论2.设G是二部划分(V1,V2)的简单二部图,且 V1=V2=n,若(G)n/2,则G有完美匹配. 定理1.G有完美匹配O(G-S) S,SV(G),其 • 中O(G-S)是G-S的奇数阶连通分枝数目.
解 令G = <V1, V2, E >, 其中V1={s, g, x}, V2={a, b, c, d, e}, E={(u, v) | uV1, vV2, v想去u},
其中s, g, x分别表示上海、广州和香港.
G如图所示.
G 满足相异性条件，因而可给
出派遣方案，共有9种派遣方案
(请给出这9种方案).
1993年，他获得组合与图论领域颁发的欧拉奖章。
贝尔热在博弈论、拓扑学领域里也有杰出贡献。在 博弈领域，他引入了Nash均衡之外的另一种均衡系统。 Nash的生活被改编成电影《美丽的心灵》，获02年奥 斯卡金像奖。
贝尔热对中国的手工艺很感兴趣。他也是一位象棋 高手，还创作过小说《谁杀害了Densmore公爵》。
实际问题 二次大站期间，许多盟军飞行员到英
国参加对法西斯的空袭，当时每架飞机需领航员 和飞行员各一名。其中有些只能领航，有些只能 驾驶，也有人二者均会。加之二人语言要求相通， 如果以结点表示人，边表示二人语言相通并且一 人可领航，另一人可驾驶便可得一图，这是一简 单图，那么最多的编队方案就是求该G的一个最 大匹配。
f1
f2
f3
f4
f5
m1 m2
m3 m4
m5
最大匹配一般不唯一
f1
f2
f3
f4
f5
m1 m2
m3 m4
m5
怎样会是最大匹配？
• 图G中的匹配M怎样会是最大匹配呢？让我们 来考虑最简单的情况：
• 最简单的情况是G是一条单通路。显然 • ①G的边应交错地属于M(M不能有邻接的边)。 • ② G的第一条边和最后一条边中至少应有一条
边属于M (否则M不是最大匹配)。如下图所示：
• 定义4：若M是图G的一个匹配，若从G中
一个顶点到另一个顶点存在一条道路，此
路径由属于M和不属于M的边交替出现组成
的，则称此路径为交错道路.。
f1
f2
f3
f4
f5
m1 m2
m3
m4
m5
• 定义5：若交互道路的两个端点为关于M的不 饱和顶点时，称此交互道为M-可增广道路。
匈牙利(Hungarian)算法：
(1)任给一个初始匹配；
(2)若X已经饱和，结束；否则转（3）；
(3)在X中找一个非饱和点x0，V1={x0}，V2={}； (4)若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2； (5)若y已饱和， M中必有(y,z) ；作【 V1 =V1 ∪{z} ，
匈牙利算法
基本思想:设G是具有二部划分(V1,V2)的二部图,从图G的 任意匹配M开始.若M饱和V1,则M是G的匹配.若M不能饱和 V1,则在V1中选择一个非M饱和点x,若G中存在以x为起点 的M可增广路P,则M’=MP就是比M更大的匹配,利用M’ 代替M,并重复这个过程.若G中不存在以x为起点的M可增 广路,则令H是根在x的M交错子图的顶点集,并令 S=HV1,T=HV2, 由定理1,T=NG(S),且G中不存在以x为 起点的M可增广路,此时称x为检验过的非M饱和点.对V1中 其它未检验过的非M饱和点重复该过程,直到V1中的所有 非M饱和点全部检验过为止.当整个过程结束时,由于G中 不存在M可增广路,从而M为G的最大匹配.
最大匹配与完美匹配
• 完美匹配必定是最大匹配，但反 之不然。
• 任何图G一定有最大匹配，但却 不一定有完美匹配。
• 含奇数顶点的图不可能有完美匹 配，因为无论如何配对，注定有 人打单身。
• 有完美匹配的图一定是偶数个顶 点，但偶数个顶点的图中也未必 能使天下人终成眷属。
v1
v2
v6 v3
v4
v5
v7
(3) Hall定理也称为“婚姻定理”，表述如下： “婚姻定理” ：在一个由r个女人和s个男人构成的人群中， 1≦r≦s。在熟识的男女之间可能出现r对婚姻的充分必要条 件是，对每个整数k(1≦k≦r),任意k个女人共认识至少k个男 人。 (4) Hall定理是在偶图中求最大匹配算法的理论基础，即 匈牙利算法基础。
27
证明： 设M是G的最大匹配。若G中存在M–
可增广路，的长度必为奇数，且不属于M的 边比属于M的边恰好多一条。令M’ = M。 显然M’也是G的一个匹配，且|M’| = |M| + 1＞ |M|。此与M的假设矛盾。故G中无M–可增广路。
（反证法） 反之，设G中不存在M–可增广路，若M不 是最大匹配，则可令M’是最大匹配，|M’|＞|M|。令
f1
f2
f3
f4
f5
m1 m2 m3
m4
m5
2、贝尔热定理 定理2 (Berge 1957)：M为最大匹配的充要条
件是：图G中不存在M-可增广道路。
f1
f2
f3
f4
f5
m1
m2
m3
m4
m5
注：贝尔热定理给我们提供了扩充G的匹配的思路。
贝尔热(1926---2002) 法国著名数学家。他的《无限图 理论及其应用》(1958) 是继哥尼之后的图论历史上的第 二本图论专著。他不仅在图论领域做出了许多贡献，而 且四处奔波传播图论，推动了图论的普及和发展。
f1
f2
f3
f4
f5
m1 m2
m3
m4
m5
匹配——边 独立 集（边与边 不 相邻）
例9.2 求下列图的匹配：
3