资源描述：
《图论课件第五章 匹配与因子分解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1图论及其应用应用数学学院2第五章匹配与因子分解主要内容一、偶图的匹配问题二、图的因子分解三、匈牙利算法与最优匹配算法教学时数安排6学时讲授本章内容3本次课主要内容(一)、图的匹配与贝尔热定理(二)、偶图的匹配与覆盖(三)、托特定理偶图的匹配问题41、图的匹配相关概念(1)、匹配M---如果M是图G的边子集(不含环），且M中的任意两条边没有共同顶点，则称M是G的一个匹配或对集或边独立集。(一)、图的匹配与贝尔热定理如果G中顶点v是G的匹配M中某条边的端点，称它为M饱和点，否则为M非饱和点。v1v7v6Gv8v2v3v5v4M1=｛v6v7｝M2=｛
2、v6v7,v1v8｝M3=｛v6v7,v1v8,v3v4｝M1,M2,M3等都是G的匹配。5(2)、最大匹配M---如果M是图G的包含边数最多的匹配，称M是G的一个最大匹配。特别是，若最大匹配饱和了G的所有顶点，称它为G的一个完美匹配。G的一个最大匹配G的一个完美匹配注：一个图G不一定存在完美匹配。6(3)、M交错路---如果M是图G的匹配，G中一条由M中的边和非M中的边交错形成的路，称为G中的一条M交错路。特别地，若M交错路的起点与终点是M非饱和点，称这种M交错路为M可扩路。在下图中：v1v7v6Gv8v2v3v5v4设M=｛v7v8,v3v4｝
3、，则：路v6v7v8v3v4与v1v7v8v2都是M交错路。其中后者是M可扩路。72、贝尔热定理定理1(贝尔热，1957)G的匹配M是最大匹配，当且仅当G不包含M可扩路。证明：“必要性”若G包含一条M可扩路P,则可令该可扩路为：显然，P中M中的边比非M中的边少一条。于是作新的匹配M1,它当中的边由P中非M中边组成。M1中边比M中多一条，这与M是G的最大匹配矛盾。“充分性”若不然，设M1是G的一个最大匹配，则
4、M1
5、>
6、M
7、。8令H=M1ΔM。容易知道：G[H]的每个分支或者是由M1与M中边交替组成的偶圈，或者是由M1与M中边交替组成的路。在每个偶圈
8、中，M1与M中边数相等；但因
9、M1
10、>
11、M
12、，所以，至少有一条路P，其起点和终点都是M非饱和点，于是，它是G的一条M可扩路。这与条件矛盾。注：贝尔热定理给我们提供了扩充G的匹配的思路。贝尔热(1926---2002)法国著名数学家。他的《无限图理论及其应用》(1958)是继哥尼之后的图论历史上的第二本图论专著。他不仅在图论领域做出了许多贡献，而且四处奔波传播图论，推动了图论的普及和发展。1993年，他获得组合与图论领域颁发的欧拉奖章。9贝尔热在博弈论、拓扑学领域里也有杰出贡献。在博弈领域，他引入了Nash均衡之外的另一种均衡系统。Nash的生活被改
13、编成电影《美丽的心灵》，获02年奥斯卡金像奖。贝尔热对中国的手工艺很感兴趣。他也是一位象棋高手，还创作过小说《谁杀害了Densmore公爵》。(二)、偶图的匹配与覆盖在日常生活，工程技术中，常常遇到求偶图的匹配问题。下面看一个例子：1、问题的提出10有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
14、;问：学生能找到理想工作吗？解：如果令X=｛A,B,C,D,E,F,G｝,Y=｛a,b,c,d,e,f,g｝,X中顶点与Y中顶点连线当且仅当学生申请了该工作。于是，得到反映学生和职位之间的状态图：11问题转化为求饱和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;FEDCBAGabcdefg需要解决的问题是:(1)匹配是否存在？(2)如何求出匹配？2、偶图匹配存在性判定----Hall定理12FEDCBAGabcdefg定理2(Hall定理）设G=(X,Y)是
15、偶图，则G存在饱和X每个顶点的匹配的充要条件是：例1，在下面偶图中，是否存在饱和X=｛A,B,C,D,E,F,G｝的每个顶点的匹配？13FEDCBAGabcdefg解:(1)当S取X中单元点时，容易验证：
16、N(S)
17、>
18、S
19、(2)当S取X中二元点集时，容易验证：
20、N(S)
21、≧
22、S
23、(3)当S取X中三元点集时，容易验证：
24、N(S)
25、≧
26、S
27、(4)当S取X中四元点集时，若取S=｛A,C,D,F｝,则有3=
28、N(S)
29、<
30、S
31、=4所以，不存在饱和X每个顶点的匹配。下面我们证明Hall定理。14证明：“必要性”如果G存在饱和X每个顶点的匹配，由匹配的定义，
32、X的每个顶点在Y中至少有一个邻接点，所以:“充分性”如果G是满足条件(*)的偶图,但是不存在饱和X每个顶点的匹配。令M*是
