《图论课件第五章匹配与因子分解》.ppt

该【《图论课件第五章匹配与因子分解》 】是由【相惜】上传分享，文档一共【31】页，该文档可以免费在线阅读，需要了解更多关于【《图论课件第五章匹配与因子分解》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。图论及其应用应用数学学院精选课件1第五章匹配与因子分解主要内容一、偶图的匹配问题二、图的因子分解三、匈牙利算法与最优匹配算法教学时数安排6学时讲授本章内容精选课件2本次课主要内容(一)、图的匹配与贝尔热定理(二)、偶图的匹配与覆盖(三)、托特定理偶图的匹配问题精选课件31、图的匹配相关概念(1)、匹配M---如果M是图G的边子集(不含环〕,且M中的任意两条边没有共同顶点,那么称M是G的一个匹配或对集或边独立集。(一)、图的匹配与贝尔热定理如果G中顶点v是G的匹配M中某条边的端点,称它为M饱和点,否那么为M非饱和点。v1v7v6Gv8v2v3v5v4M1={v6v7}M2={v6v7,v1v8}M3={v6v7,v1v8,v3v4}M1,M2,M3等都是G的匹配。精选课件4(2)、最大匹配M---如果M是图G的包含边数最多的匹配,称M是G的一个最大匹配。特别是,假设最大匹配饱和了G的所有顶点,称它为G的一个完美匹配。G的一个最大匹配G的一个完美匹配注:一个图G不一定存在完美匹配。精选课件5(3)、M交错路---如果M是图G的匹配,G中一条由M中的边和非M中的边交错形成的路,称为G中的一条M交错路。特别地,假设M交错路的起点与终点是M非饱和点,称这种M交错路为M可扩路。在以下图中:v1v7v6Gv8v2v3v5v4设M={v7v8,v3v4},那么:路v6v7v8v3v4与v1v7v8v2都是M交错路。其中后者是M可扩路。精选课件62、贝尔热定理定理1(贝尔热,1957)G的匹配M是最大匹配,当且仅当G不包含M可扩路。证明:“必要性〞假设G包含一条M可扩路P,那么可令该可扩路为:显然,P中M中的边比非M中的边少一条。于是作新的匹配M1,它当中的边由P中非M中边组成。M1中边比M中多一条,这与M是G的最大匹配矛盾。“充分性〞假设不然,设M1是G的一个最大匹配,那么|M1|>|M|。精选课件7令H=M1ΔM。容易知道:G[H]的每个分支或者是由M1与M中边交替组成的偶圈,或者是由M1与M中边交替组成的路。在每个偶圈中,M1与M中边数相等;但因|M1|>|M|,所以,至少有一条路P,其起点和终点都是M非饱和点,于是,它是G的一条M可扩路。这与条件矛盾。注:贝尔热定理给我们提供了扩充G的匹配的思路。贝尔热(1926---2002)法国著名数学家。他的?无限图理论及其应用?(1958)是继哥尼之后的图论历史上的第二本图论专著。他不仅在图论领域做出了许多奉献,而且四处奔波传播图论,推动了图论的普及和开展。1993年,他获得组合与图论领域颁发的欧拉奖章。精选课件8贝尔热在博弈论、拓扑学领域里也有杰出奉献。在博弈领域,他引入了Nash均衡之外的另一种均衡系统。Nash的生活被改编成电影?美丽的心灵?,获02年奥斯卡金像奖。贝尔热对中国的手工艺很感兴趣。他也是一位象棋高手,还创作过小说?谁杀害了Densmore公爵?。(二)、偶图的匹配与覆盖在日常生活,工程技术中,常常遇到求偶图的匹配问题。下面看一个例子:1、问题的提出精选课件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中顶点连线当且仅当学生申请了该工作。于是,得到反映学生和职位之间的状态图:精选课件10