2、贝尔热定理 定理1（贝尔热，1957）G的匹配M是最大匹配，当且 仅当G不包含M可扩路。 证明：“必要性” 若G包含一条M可扩路P,则可令该可扩路为： P=yoYV2··V2kV2k+1 显然，P中M中的边比非M中的边少一条。于是作新 的匹配M,它当中的边由P中非M中边组成。M,中边比 M中多一条，这与M是G的最大匹配矛盾。 “充分性” 若不然，设M是G的一个最大匹配，则MPM
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 2、贝尔热定理 定理1 (贝尔热，1957) G的匹配M是最大匹配，当且 仅当G不包含M可扩路。 证明：“必要性” 若G包含一条M可扩路P,则可令该可扩路为： P v v v v v = 0 1 2 2 2 1 k k+ 显然，P中M中的边比非M中的边少一条。于是作新 的匹配M1 ,它当中的边由P中非M中边组成。M1中边比 M中多一条，这与M是G的最大匹配矛盾。 “充分性” 若不然，设M1是G的一个最大匹配，则|M1 |>|M|
令H=M△M。 容易知道：G的每个分支或者是由M,与M中边交 替组成的偶圈，或者是由M1与M中边交替组成的路。 在每个偶圈中，M,与M中边数相等；但因M>M, 所以，至少有一条路P,其起点和终点都是M非饱和点， 于是，它是G的一条M可扩路。这与条件矛盾。 注：贝尔热定理给我们提供了扩充G的匹配的思路。 贝尔热(1926-2002)法国著名数学家。他的《无限图 理论及其应用》(1958)是继哥尼之后的图论历史上的第 二本图论专著。他不仅在图论领域做出了许多贡献，而 且四处奔波传播图论，推动了图论的普及和发展。 1993年，他获得组合与图论领域颁发的欧拉奖章
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 令H = M1ΔM。 容易知道：G[H]的每个分支或者是由M1与M中边交 替组成的偶圈，或者是由M1与M中边交替组成的路。 在每个偶圈中，M1与M中边数相等；但因|M1 |>|M|， 所以，至少有一条路P，其起点和终点都是M非饱和点， 于是，它是G的一条M可扩路。这与条件矛盾。 注：贝尔热定理给我们提供了扩充G的匹配的思路。 贝尔热(1926-2002) 法国著名数学家。他的《无限图 理论及其应用》(1958) 是继哥尼之后的图论历史上的第 二本图论专著。他不仅在图论领域做出了许多贡献，而 且四处奔波传播图论，推动了图论的普及和发展。 1993年，他获得组合与图论领域颁发的欧拉奖章
贝尔热在博奔论、拓扑学领域里也有杰出贡献。在 博弈领域，他引入了Nash均衡之外的另一种均衡系统。 Nash的生活被改编成电影《美丽的心灵》，获02年奥 斯卡金像奖。 贝尔热对中国的手工艺很感兴趣。他也是一位象棋 高手，还创作过小说《准杀害了Densmore公爵》 。 (二)、偶图的匹配与覆盖 1、问题的提出 在日常生活，工程技术中，常常遇到求偶图的匹配 问题。下面看一个例子：
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 贝尔热在博弈论、拓扑学领域里也有杰出贡献。在 博弈领域，他引入了Nash均衡之外的另一种均衡系统。 Nash的生活被改编成电影《美丽的心灵》，获02年奥 斯卡金像奖。 贝尔热对中国的手工艺很感兴趣。他也是一位象棋 高手，还创作过小说《谁杀害了Densmore公爵》。 (二)、偶图的匹配与覆盖 在日常生活，工程技术中，常常遇到求偶图的匹配 问题。下面看一个例子： 1、问题的提出
有7名研究生A,B,C,D,E,F,G毕业寻找工作。就业 处提供的公开职位是：会计师(a),咨询师(b),编辑(c),程 序员(d),记者(e),秘书()和教师(g)。每名学生申请的职 位如下： A:b,c;B:a,b,d,f,g;C:b,e;D:b,c,e; E:a,c,d,f;F:c,e;G:d,e,f,g; 问：学生能找到理想工作吗？ 解：如果令X={A,B,C,D,E,F,G},Y={a,b,c,d,e,f, g},X中顶点与Y中顶点连线当且仅当学生申请了该工作。于 是，得到反映学生和职位之间的状态图：
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 有7名研究生A, B, C, D, E, F, G毕业寻找工作。就业 处提供的公开职位是：会计师(a) ,咨询师(b),编辑(c ),程 序员(d), 记者(e), 秘书(f)和教师(g)。每名学生申请的职 位如下： A : b, c ; B : a, b, d, f, g ; C : b, e ; D : b, c, e ; E : a, c, d, f ; F : c, e ; G : d, e, f, g ; 问：学生能找到理想工作吗？ 解：如果令X=｛A, B, C, D, E, F, G｝,Y=｛a, b, c, d, e, f , g｝,X中顶点与Y中顶点连线当且仅当学生申请了该工作。于 是，得到反映学生和职位之间的状态图：
A:b,c;B:a,b,d,f,g;C:b,e;D:b,c,e; E:a,c,d,f;F:c,e;G:d,e,f,g; 问题转化为求饱和X每个顶点的一个匹配！ 需要解决的问题是：(1)匹配是否存在？(2)如何求出匹配？ 2、偶图匹配存在性判定-Hal定理 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 问题转化为求饱和X每个顶点的一个匹配！ A : b, c ; B : a, b, d, f, g ; C : b, e ; D : b, c, e ; E : a, c, d, f ; F : c, e ; G : d, e, f, g ; A B C D E F G a b c d e f g 需要解决的问题是: (1) 匹配是否存在？(2) 如何求出匹配？ 2、偶图匹配存在性判定-Hall定理