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

《图论课件第五章匹配与因子分解精.ppt》由会员分享，可在线阅读，更多相关《图论课件第五章匹配与因子分解精.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论课件第五章匹配与因子分解第1页，本讲稿共31页2第五章第五章 匹配与因子分解匹配与因子分解主要内容主要内容一、偶图的匹配问题一、偶图的匹配问题二、图的因子分解二、图的因子分解三、匈牙利算法与最优匹配算法三、匈牙利算法与最优匹配算法教学时数教学时数安排安排6学时讲授本章内容学时讲授本章内容第2页，本讲稿共31页3本次课主要内容本次课主要内容(一一)、图的匹配与贝尔热定理、图的匹配与贝尔热定理(二二)、偶图的匹配与覆盖、偶图的匹配与覆盖(三三)、托特定理、托特定理偶图的匹配问题偶图的匹配问题第3页，本讲稿共31页4 1、图的匹配相关概念、图的匹配相关概念 (1)、匹配、匹配 M-如果如果M是图

2、是图G的边子集的边子集(不含环），且不含环），且M中的中的任意两条边没有共同顶点，则称任意两条边没有共同顶点，则称M是是G的一个匹配或对集或边的一个匹配或对集或边独立集。独立集。(一一)、图的匹配与贝尔热定理、图的匹配与贝尔热定理 如果如果G中顶点中顶点v是是G的匹配的匹配 M中某条边的端点，称它为中某条边的端点，称它为M饱饱和点，否则为和点，否则为M非饱和点。非饱和点。v1 v7v6 Gv8v2v3v5v4 M1=v6v7 M2=v6v7,v1v8 M3=v6v7,v1v8,v3v4 M1,M2,M3等都是等都是G的匹配。的匹配。第4页，本讲稿共31页5 (2)、最大匹配、最大匹配 M-如果

3、如果M是图是图G的包含边数最多的匹配，的包含边数最多的匹配，称称M是是G的一个最大匹配。特别是，若最大匹配饱和了的一个最大匹配。特别是，若最大匹配饱和了G的所有顶点，称它为的所有顶点，称它为G的一个完美匹配。的一个完美匹配。G的一个 最大匹配G的一个完美匹配 注：一个图注：一个图G不一定存在完美匹配。不一定存在完美匹配。第5页，本讲稿共31页6 (3)、M交错路交错路-如果如果M是图是图G的匹配，的匹配，G中一条由中一条由M中的边中的边和非和非M中的边交错形成的路，称为中的边交错形成的路，称为G中的一条中的一条M交错路。特别交错路。特别地，若地，若M交错路的起点与终点是交错路的起点与终点是M非

4、饱和点，称这种非饱和点，称这种M交错交错路为路为M可扩路可扩路。在下图中：在下图中：v1 v7v6 Gv8v2v3v5v4 设设M=v7v8,v3v4，则：，则：路路v6v7v8v3v4与与v1v7v8v2都是都是M交错路。其中后者是交错路。其中后者是M可扩可扩路。路。第6页，本讲稿共31页7 2、贝尔热定理、贝尔热定理 定理定理1(贝尔热，贝尔热，1957)G的匹配的匹配M是最大匹配，当且仅当是最大匹配，当且仅当G不包含不包含M可扩路。可扩路。证明：证明：“必要性必要性”若若G包含一条包含一条M可扩路可扩路P,则可令该可扩路为：则可令该可扩路为：显然，显然，P中中M中的边比非中的边比非M中的

5、边少一条。于是作新的匹中的边少一条。于是作新的匹配配M1,它当中的边由它当中的边由P中非中非M中边组成。中边组成。M1中边比中边比M中多一条，中多一条，这与这与M是是G的最大匹配矛盾。的最大匹配矛盾。“充分性充分性”若不然，设若不然，设M1是是G的一个最大匹配，则的一个最大匹配，则|M1|M|。第7页，本讲稿共31页8 令令H=M1M。容易知道：容易知道：GH的每个分支或者是由的每个分支或者是由M1与与M中边交替组成中边交替组成的偶圈，或者是由的偶圈，或者是由M1与与M中边交替组成的路。中边交替组成的路。在每个偶圈中，在每个偶圈中，M1与与M中边数相等；但因中边数相等；但因|M1|M|，所以，

6、所以，至少有一条路至少有一条路P，其起点和终点都是，其起点和终点都是M非饱和点，于是，它是非饱和点，于是，它是G的一条的一条M可扩路。这与条件矛盾。可扩路。这与条件矛盾。注：贝尔热定理给我们提供了扩充注：贝尔热定理给我们提供了扩充G的匹配的思路。的匹配的思路。贝尔热贝尔热(1926-2002)法国著名数学家。他的法国著名数学家。他的无限图理论无限图理论及其应用及其应用(1958)是继哥尼之后的图论历史上的第二本图论专著。是继哥尼之后的图论历史上的第二本图论专著。他不仅在图论领域做出了许多贡献，而且四处奔波传播图论，推他不仅在图论领域做出了许多贡献，而且四处奔波传播图论，推动了图论的普及和发展。

7、动了图论的普及和发展。1993年，他获得组合与图论领域颁发的欧拉奖章。年，他获得组合与图论领域颁发的欧拉奖章。第8页，本讲稿共31页9 贝尔热在博弈论、拓扑学领域里也有杰出贡献。在博贝尔热在博弈论、拓扑学领域里也有杰出贡献。在博弈领域，他引入了弈领域，他引入了Nash均衡之外的另一种均衡系统。均衡之外的另一种均衡系统。Nash的生活被改编成电影的生活被改编成电影美丽的心灵美丽的心灵，获，获02年奥斯卡金像奖。年奥斯卡金像奖。贝尔热对中国的手工艺很感兴趣。他也是一位象棋高贝尔热对中国的手工艺很感兴趣。他也是一位象棋高手，还创作过小说手，还创作过小说谁杀害了谁杀害了Densmore公爵公爵。(二二

8、)、偶图的匹配与覆盖、偶图的匹配与覆盖 在日常生活，工程技术中，常常遇到求偶图的匹配问题。下在日常生活，工程技术中，常常遇到求偶图的匹配问题。下面看一个例子：面看一个例子：1、问题的提出、问题的提出第9页，本讲稿共31页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,

9、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页，本讲稿共31页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 需

10、要解决的问题是需要解决的问题是:(1)匹配是否存在？匹配是否存在？(2)如何求出匹配？如何求出匹配？2、偶图匹配存在性判定、偶图匹配存在性判定-Hall定理定理第11页，本讲稿共31页12FEDCBAGabcdefg 定理定理2(Hall定理）设定理）设G=(X,Y)是偶图，则是偶图，则G存在饱和存在饱和X每个顶点的匹配每个顶点的匹配的充要条件是：的充要条件是：例例1，在下面偶图中，是否存在饱和，在下面偶图中，是否存在饱和X=A,B,C,D,E,F,G的每个顶点的匹配？的每个顶点的匹配？第12页，本讲稿共31页13FEDCBAGabcdefg 解解:(1)当当S取取X中单元点时，容易验证：中单

11、元点时，容易验证：|N(S)|S|(2)当当S取取X中二元点集时，容易中二元点集时，容易验证：验证：|N(S)|S|(3)当当S取取X中三元点集时，容易中三元点集时，容易验证：验证：|N(S)|S|(4)当当S取取X中四元点集时，若取中四元点集时，若取S=A,C,D,F,则有则有3=|N(S)|S|=4 所以，不存在饱和所以，不存在饱和X每个顶点的匹配。每个顶点的匹配。下面我们证明下面我们证明Hall定理。定理。第13页，本讲稿共31页14 证明：证明：“必要性必要性”如果如果G存在饱和存在饱和X每个顶点的匹配，由匹配的定义，每个顶点的匹配，由匹配的定义，X的每的每个顶点在个顶点在Y中至少有一

12、个邻接点，所以中至少有一个邻接点，所以:“充分性充分性”如果如果G是满足条件是满足条件(*)的偶图的偶图,但是不存在饱和但是不存在饱和X每个顶点的每个顶点的匹配。匹配。令令M*是是G的一个最大匹配，但是不饱和的一个最大匹配，但是不饱和X的顶点的顶点u.u示意图示意图G第14页，本讲稿共31页15 又又令令Z是通过是通过M*与点与点u相连形成的所有相连形成的所有M*交错路上的点集。交错路上的点集。因因M*是最大匹配，所以是最大匹配，所以u是是所有交错路上唯一的一个未饱和点。所有交错路上唯一的一个未饱和点。令令S=XZ,T=ZY 显然，显然，S-u中点与中点与T中点在中点在M*下配对，即：下配对，

13、即：|T|=|S|-1|S|即：即：|N(S)|=|T|=|S|-1|S|，与条件矛盾。，与条件矛盾。uTS 注注:(1)G=(X,Y)存在存在饱和饱和X每个顶点的匹配每个顶点的匹配也常说成存在也常说成存在由由X到到Y的匹配的匹配。第15页，本讲稿共31页16 (2)Hall定理也可表述为：设定理也可表述为：设G=(X,Y)是偶图，如果存在是偶图，如果存在X的一个的一个子集子集S,使得使得|N(S)|0)正则偶图，则正则偶图，则G存在完美匹配。存在完美匹配。证明：一方面，由于证明：一方面，由于G是是k(k0)正则偶图正则偶图,所以所以k|X|=k|Y|,于是于是得得|X|=|Y|；另一方面，对

14、于另一方面，对于X的任一非空子集的任一非空子集S,设设E1与与E2分别是与分别是与S和和N(S)关联的边集，显然有：关联的边集，显然有：即：即：由由Hall定理，存在由定理，存在由X到到Y的匹配的匹配.又又|X|=|Y|，所以，所以G存在完美匹存在完美匹配。配。第17页，本讲稿共31页18 例例2(1)证明：每个证明：每个k方体都有完美匹配方体都有完美匹配(k大于等于大于等于2)(2)求求K2n和和Kn,n中不同的完美匹配的个数。中不同的完美匹配的个数。(1)证明一：证明每个证明一：证明每个k方体都是方体都是k正则偶图。正则偶图。事实上，由事实上，由k方体的构造：方体的构造：k方体有方体有2k

15、个顶点，每个顶点可以用长个顶点，每个顶点可以用长度为度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。制码只有一位坐标不同。如果我们划分如果我们划分k方体的方体的2k个顶点，把坐标之和为偶数的顶点归入个顶点，把坐标之和为偶数的顶点归入X，否则归入，否则归入Y。显然，。显然，X中顶点互不邻接，中顶点互不邻接，Y中顶点也如此。所以中顶点也如此。所以k方体是偶图。方体是偶图。又不难知道又不难知道k方体的每个顶点度数为方体的每个顶点度数为k,所以所以k方体是方体是k正则偶图。正则偶图。由推论：由推论：k方体存在完

16、美匹配。方体存在完美匹配。第18页，本讲稿共31页19 证明二：直接在证明二：直接在k方体中找出完美匹配。方体中找出完美匹配。设设k方体顶点二进制码为方体顶点二进制码为(x1,x2,xn),我们取我们取(x1,x2,xn-1,0),和和(x1,x2,xn-1,1)之间的全体边所成之集为之间的全体边所成之集为M.显然，显然，M中的边均不相邻接，所以作成中的边均不相邻接，所以作成k方体的匹配，又容易知方体的匹配，又容易知道：道：|M|=2k-1.所以所以M是完美匹配。是完美匹配。(2)我们用归纳法求我们用归纳法求K2n和和Kn,n中不同的完美匹配的个数。中不同的完美匹配的个数。K2n的任意一个顶点

17、有的任意一个顶点有2n-1中不同的方法被匹配。所以中不同的方法被匹配。所以K2n的不同完的不同完美匹配个数等于美匹配个数等于(2n-1)K2n-2,如此推下去，可以归纳出如此推下去，可以归纳出K2n的不同完美匹的不同完美匹配个数为：配个数为：(2n-1)!同样的推导方法可归纳出同样的推导方法可归纳出K n,n的不同完美匹配个数为：的不同完美匹配个数为：(n)!第19页，本讲稿共31页20 例例3 证明树至多存在一个完美匹配。证明树至多存在一个完美匹配。证明：若不然，设证明：若不然，设M1与与M2是树是树T的两个不同的完美匹配，那么的两个不同的完美匹配，那么M1M2,且且TTM1M2每个顶点度数

18、为每个顶点度数为2，即它存在圈，于是推出，即它存在圈，于是推出T中中有圈，矛盾。有圈，矛盾。3、点覆盖与哥尼定理、点覆盖与哥尼定理 (1)、图的点覆盖概念与性质、图的点覆盖概念与性质 定义定义1：图的点覆盖：图的点覆盖-G的一个顶点子集的一个顶点子集K称为称为G的一个点覆盖，如果的一个点覆盖，如果G的每条边都至少有一个端点在的每条边都至少有一个端点在K中。中。G的一个包含点数最少的点覆的一个包含点数最少的点覆盖称为盖称为G的最小点覆盖，其包含的点数称为的最小点覆盖，其包含的点数称为G的覆盖数，记为的覆盖数，记为(G).(G).(a)一个覆盖(b)一个最小覆盖第20页，本讲稿共31页21 定理定

19、理2 设设M是是G的匹配，的匹配，K是是G的覆盖，若的覆盖，若|M|=|K|,则则M是最是最大匹配，而大匹配，而G是最小覆盖。是最小覆盖。证明：设证明：设M*与与K*分别是分别是G的最大匹配和最小覆盖。的最大匹配和最小覆盖。由匹配和覆盖定义有：由匹配和覆盖定义有：|M*|K*|。所以，有：。所以，有：|M|M*|K*|K|所以，当所以，当|M|=|K|时，有时，有|M|=|M*|，|K*|=|K|即即M是最大匹配，而是最大匹配，而G是最小覆盖。是最小覆盖。(2)、偶图的点覆盖与偶图匹配间的关系、偶图的点覆盖与偶图匹配间的关系-哥尼定理哥尼定理第21页，本讲稿共31页22 定理定理2(哥尼，哥尼

20、，1931)在偶图中，最大匹配的边数等于最小在偶图中，最大匹配的边数等于最小覆盖的顶点数。覆盖的顶点数。证明：设证明：设G=(X,Y),M*是偶图是偶图G的最大匹配。的最大匹配。U表示表示G中中M*非饱和点集。非饱和点集。Z表示由表示由M*交错路连到交错路连到U的顶点的所有路上的点的顶点的所有路上的点作成的集合。且令作成的集合。且令S=ZX,T=ZY。SUT=N(S)X S第22页，本讲稿共31页23 由由M*的最大性，的最大性，T中点是中点是M*饱和的，且饱和的，且N(S)=T。SUT=N(S)X S 现在，令现在，令K*=(X-S)TT。可以证明：可以证明：K*=(X-S)TT是是G G的

21、一个覆盖。的一个覆盖。事实上，若事实上，若K*=(X-S)TT不是不是G G的一个覆盖。则存在的一个覆盖。则存在G G的的一条边一条边,其一个端点在其一个端点在S S中，而另一个端点在中，而另一个端点在Y-TY-T中，这与中，这与N(S)=T矛盾！矛盾！显然显然|K*|=|M*|。由定理。由定理2，K*是最小覆盖。是最小覆盖。第23页，本讲稿共31页24 哥尼哥尼(Knig)第一本图论教材的撰写者第一本图论教材的撰写者 到了到了1936年，第一本图论教材才与读者见面。作者是哥尼年，第一本图论教材才与读者见面。作者是哥尼(1884-1944).哥尼早期学习拓扑学，但对图论兴趣特别大。他一直哥尼早

22、期学习拓扑学，但对图论兴趣特别大。他一直工作在布达佩斯工业大学。讲课很有激情，吸引了很多优秀工作在布达佩斯工业大学。讲课很有激情，吸引了很多优秀学生转向图论研究。特别是，他把一起获得匈牙利国家高中学生转向图论研究。特别是，他把一起获得匈牙利国家高中数学竞赛一等奖的数学竞赛一等奖的3个学生都吸引来研究图论，这个学生都吸引来研究图论，这3个学生是：个学生是：Erds,Gallai,Turan.都是伟大的数学家。都是伟大的数学家。哥尼的著作名称是哥尼的著作名称是有限图与无限图理论有限图与无限图理论。这本书对青年。这本书对青年学者产生了很大影响，推动了图论的进一步发展。在学者产生了很大影响，推动了图论

23、的进一步发展。在20多年多年时间里，它都是世界上唯一一本图论著作。直到时间里，它都是世界上唯一一本图论著作。直到1958年，法国数年，法国数学家贝尔热学家贝尔热(Berge）才出版专著）才出版专著无限图理论及其应用无限图理论及其应用。哥尼哥尼1944年为免遭纳碎迫害，只有自杀。年为免遭纳碎迫害，只有自杀。第24页，本讲稿共31页25 例例4 矩阵的一行或一列称为矩阵的一条线。证明：布尔矩矩阵的一行或一列称为矩阵的一条线。证明：布尔矩阵中，包含了所有阵中，包含了所有“1”的线的最少数目，等于具有性质的线的最少数目，等于具有性质“任任意两个意两个1都不在同一条线上的都不在同一条线上的1的最大数目的

24、最大数目”。例如：在如下布尔矩阵中：例如：在如下布尔矩阵中：证明：设布尔阵是证明：设布尔阵是n行行m列矩阵，把它模型为一个偶图如下：列矩阵，把它模型为一个偶图如下：每行每列分别用一个点表示，每行每列分别用一个点表示，X表示行点集合，表示行点集合，Y表示列点集合，表示列点集合，两点连线。当且仅当该行该列元为两点连线。当且仅当该行该列元为1.第25页，本讲稿共31页26 于是，包含了所有于是，包含了所有“1”的线的最少数目对应偶图中的最的线的最少数目对应偶图中的最小点覆盖数。而具有性质小点覆盖数。而具有性质“任意两个任意两个1都不在同一条线上的都不在同一条线上的1的最大数目的最大数目”对应偶图的最

25、大匹配包含的边数。对应偶图的最大匹配包含的边数。由哥尼定理，命题得到证明。由哥尼定理，命题得到证明。(三三)、托特定理、托特定理 定理定理4(托特定理，托特定理，1947)图图G有完美匹配当且仅当对有完美匹配当且仅当对V的任意非的任意非空真子集空真子集S,有：有：注：注：o(G-S)表示奇分支数目。表示奇分支数目。第26页，本讲稿共31页27 推论推论(彼得森定理彼得森定理)没有割边的没有割边的3正则图存在完美匹配。正则图存在完美匹配。证明：设证明：设S是是V的任意一个非空真子集，的任意一个非空真子集，G1,G2,Gk是是G-S的所的所有奇分支。有奇分支。mi (1ik)ik)表示端点分属于表

26、示端点分属于S S和和G Gi i的边数。的边数。SG1G2Gkm1m2mk第27页，本讲稿共31页28 下面分析下面分析miSG1G2Gkm1m2mk 在在Gi中，其总度数为中，其总度数为2|E(Gi)|。在在Gi中，其点在中，其点在G中的中的总度数为总度数为3|V(Gi)|。所以：所以：所以所以mi必然为奇数，但必然为奇数，但G无割边，所以无割边，所以mi3.这样这样：由托特定理，由托特定理，G有完美匹配。有完美匹配。第28页，本讲稿共31页29 注：推论中的条件是注：推论中的条件是G存在完美匹配的充分条件而不是存在完美匹配的充分条件而不是必要条件。例如：必要条件。例如：（a）没有完美匹配）没有完美匹配（b）有完美匹配）有完美匹配第29页，本讲稿共31页30 作业作业 P117-118 习题习题4：1,2,16，17第30页，本讲稿共31页31Thank You!第31页，本讲稿共31页