第五章-匹配与因子分解-图论及其应用课件.ppt

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

1、1Email:图论及其应用图论及其应用任课教师：杨春任课教师：杨春2第五章第五章 匹配与因子分解匹配与因子分解主要内容主要内容一、偶图的匹配问题一、偶图的匹配问题二、图的因子分解二、图的因子分解三、匈牙利算法与最优匹配算法三、匈牙利算法与最优匹配算法教学时数教学时数安排安排6学时讲授本章内容学时讲授本章内容3本次课主要内容本次课主要内容(一一)、图的匹配与贝尔热定理、图的匹配与贝尔热定理(二二)、偶图的匹配与覆盖、偶图的匹配与覆盖(三三)、托特定理、托特定理偶图的匹配问题偶图的匹配问题4 1、图的匹配相关概念、图的匹配相关概念 (1)、匹配、匹配 M-如果如果M是图是图G的边子集的边子集(不含

2、环），且不含环），且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的匹配。的匹配。6 (3)、M交错路交错路-如果如果M是图是图G的匹配，的匹配，G中一条由中一条由M中的边

3、和非中的边和非M中的边交错形成的路，称为中的边交错形成的路，称为G中的一条中的一条M交错路。特别地，若交错路。特别地，若M交错路的起点与终点是交错路的起点与终点是M非饱和非饱和点，称这种点，称这种M交错路为交错路为M可扩路可扩路。在下图中：在下图中：v1 v7v6 Gv8v2v3v5v4 设设M=v7v8,v3v4，则：，则：路路v6v7v8v3v4与与v1v7v8v2都是都是M交错路。其中后者是交错路。其中后者是M可扩路。可扩路。7 2、贝尔热定理、贝尔热定理 定理定理1(贝尔热，贝尔热，1957)G的匹配的匹配M是最大匹配，当且是最大匹配，当且仅当仅当G不包含不包含M可扩路。可扩路。证明：

4、证明：“必要性必要性”若若G包含一条包含一条M可扩路可扩路P,则可令该可扩路为：则可令该可扩路为：显然，显然，P中中M中的边比非中的边比非M中的边少一条。于是作新中的边少一条。于是作新的匹配的匹配M1,它当中的边由它当中的边由P中非中非M中边组成。中边组成。M1中边比中边比M中多一条，这与中多一条，这与M是是G的最大匹配矛盾。的最大匹配矛盾。“充分性充分性”若不然，设若不然，设M1是是G的一个最大匹配，则的一个最大匹配，则|M1|M|。8 令令H=M1M。容易知道：容易知道：GH的每个分支或者是由的每个分支或者是由M1与与M中边交中边交替组成的偶圈，或者是由替组成的偶圈，或者是由M1与与M中边

5、交替组成的路。中边交替组成的路。在每个偶圈中，在每个偶圈中，M1与与M中边数相等；但因中边数相等；但因|M1|M|，所，所以，至少有一条路以，至少有一条路P，其起点和终点都是，其起点和终点都是M非饱和点，于非饱和点，于是，它是是，它是G的一条的一条M可扩路。这与条件矛盾。可扩路。这与条件矛盾。注：贝尔热定理给我们提供了扩充注：贝尔热定理给我们提供了扩充G的匹配的思路。的匹配的思路。贝尔热贝尔热(1926-2002)法国著名数学家。他的法国著名数学家。他的无限图无限图理论及其应用理论及其应用(1958)是继哥尼之后的图论历史上的第是继哥尼之后的图论历史上的第二本图论专著。他不仅在图论领域做出了许

6、多贡献，而二本图论专著。他不仅在图论领域做出了许多贡献，而且四处奔波传播图论，推动了图论的普及和发展。且四处奔波传播图论，推动了图论的普及和发展。1993年，他获得组合与图论领域颁发的欧拉奖章。年，他获得组合与图论领域颁发的欧拉奖章。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

7、,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中顶点连线当且仅当学生申请了该工作。于中顶点连线当且仅当学生申请了该工作。于是，得到反映学生和职位之间的状态图：是，得到反映学生和职位之间的状态图：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 需要解决的问

8、题是需要解决的问题是:(1)匹配是否存在？匹配是否存在？(2)如何求出匹配？如何求出匹配？2、偶图匹配存在性判定、偶图匹配存在性判定-Hall定理定理13FEDCBAGabcdefg 解解:(1)当当S取取X中单元点时，容易验证：中单元点时，容易验证：|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每个顶点的匹配。每个顶点的

9、匹配。下面我们证明下面我们证明Hall定理。定理。15 又又令令Z是通过是通过M*与点与点u相连形成的所有相连形成的所有M*交错路上交错路上的点集。的点集。因因M*是最大匹配，所以是最大匹配，所以u是所有交错路上唯一的一个是所有交错路上唯一的一个未饱和点。未饱和点。令令S=XZ,T=ZY 显然，显然，S-u中点与中点与T中点在中点在M*下配对，即：下配对，即：|T|=|S|-1|S|即：即：|N(S)|=|T|=|S|-1|S|，与条件矛盾。，与条件矛盾。uTS 注注:(1)G=(X,Y)存在存在饱和饱和X每个顶点的匹配每个顶点的匹配也常说成存也常说成存在在由由X到到Y的匹配的匹配。16 (2

10、)Hall定理也可表述为：设定理也可表述为：设G=(X,Y)是偶图，如果存在是偶图，如果存在X的一个子集的一个子集S,使得使得|N(S)|S|，那么，那么G中不存在由中不存在由X到到Y的的匹配。匹配。(3)Hall定理也称为定理也称为“婚姻定理婚姻定理”，表述如下：，表述如下：“婚姻定理婚姻定理”：在一个由：在一个由r个女人和个女人和s个男人构成的人群中，个男人构成的人群中，1rsrs。在熟识的男女之间可能出现。在熟识的男女之间可能出现r r对婚姻的充分必要条件对婚姻的充分必要条件是，对每个整数是，对每个整数k(1kr),k(1kr),任意任意k k个女人共认识至少个女人共认识至少k k个男人

11、。个男人。(4)Hall定理是在偶图中求最大匹配算法的理论基础，即定理是在偶图中求最大匹配算法的理论基础，即匈牙利算法基础。匈牙利算法基础。(5)Hall(1904-1982)英国人，英国人，20世纪最伟大的数学家之世纪最伟大的数学家之一。主要功绩是在代数学领域。在剑桥大学工作期间，主要一。主要功绩是在代数学领域。在剑桥大学工作期间，主要研究群论，研究群论，1932年发表的关于素数幂阶群论文是他最有名年发表的关于素数幂阶群论文是他最有名18 例例2(1)证明：每个证明：每个k方体都有完美匹配方体都有完美匹配(k大于等于大于等于2)(2)求求K2n和和Kn,n中不同的完美匹配的个数。中不同的完美

12、匹配的个数。(1)证明一：证明每个证明一：证明每个k方体都是方体都是k正则偶图。正则偶图。事实上，由事实上，由k方体的构造：方体的构造：k方体有方体有2k个顶点，每个顶点可个顶点，每个顶点可以用长度为以用长度为k的二进制码来表示，两个顶点连线当且仅当代的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。表两个顶点的二进制码只有一位坐标不同。如果我们划分如果我们划分k方体的方体的2k个顶点，把坐标之和为偶数的顶个顶点，把坐标之和为偶数的顶点归入点归入X，否则归入，否则归入Y。显然，。显然，X中顶点互不邻接，中顶点互不邻接，Y中顶点中顶点也如此。所以也如此。所以k方体是偶

13、图。方体是偶图。又不难知道又不难知道k方体的每个顶点度数为方体的每个顶点度数为k,所以所以k方体是方体是k正则正则偶图。偶图。由推论：由推论：k方体存在完美匹配。方体存在完美匹配。19 证明二：直接在证明二：直接在k方体中找出完美匹配。方体中找出完美匹配。设设k方体顶点二进制码为方体顶点二进制码为(x1,x2,xn),我们取我们取(x1,x2,xn-1,0),和和(x1,x2,xn-1,1)之间的全体边所成之集为之间的全体边所成之集为M.显然，显然，M中的边均不相邻接，所以作成中的边均不相邻接，所以作成k方体的匹配，又方体的匹配，又容易知道：容易知道：|M|=2k-1.所以所以M是完美匹配。是

14、完美匹配。(2)我们用归纳法求我们用归纳法求K2n和和Kn,n中不同的完美匹配的个数。中不同的完美匹配的个数。K2n的任意一个顶点有的任意一个顶点有2n-1中不同的方法被匹配。所以中不同的方法被匹配。所以K2n的的不同完美匹配个数等于不同完美匹配个数等于(2n-1)K2n-2,如此推下去，可以归纳出如此推下去，可以归纳出K2n的不同完美匹配个数为：的不同完美匹配个数为：(2n-1)!同样的推导方法可归纳出同样的推导方法可归纳出K n,n的不同完美匹配个数为：的不同完美匹配个数为：(n)!20 例例3 证明树至多存在一个完美匹配。证明树至多存在一个完美匹配。证明：若不然，设证明：若不然，设M1与

15、与M2是树是树T的两个不同的完美匹配，的两个不同的完美匹配，那么那么M1M2,且且TTM1M2每个顶点度数为每个顶点度数为2，即它存在圈，即它存在圈，于是推出于是推出T中有圈，矛盾。中有圈，矛盾。3、点覆盖与哥尼定理、点覆盖与哥尼定理 (1)、图的点覆盖概念与性质、图的点覆盖概念与性质 定义定义1：图的点覆盖：图的点覆盖-G的一个顶点子集的一个顶点子集K称为称为G的一个点覆的一个点覆盖，如果盖，如果G的每条边都至少有一个端点在的每条边都至少有一个端点在K中。中。G的一个包含点的一个包含点数最少的点覆盖称为数最少的点覆盖称为G的最小点覆盖，其包含的点数称为的最小点覆盖，其包含的点数称为G的的覆盖

16、数，记为覆盖数，记为(G).(G).(a)一个覆盖(b)一个最小覆盖21 定理定理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)、偶图的点覆盖与偶图匹配间的关系、偶图的点覆盖与偶图匹

17、配间的关系-哥尼定理哥尼定理22 定理定理2(哥尼，哥尼，1931)在偶图中，最大匹配的边数等于在偶图中，最大匹配的边数等于最小覆盖的顶点数。最小覆盖的顶点数。证明：设证明：设G=(X,Y),M*是偶图是偶图G的最大匹配。的最大匹配。U表示表示G中中M*非饱和点集。非饱和点集。Z表示由表示由M*交错路连到交错路连到U的顶点的所的顶点的所有路上的点作成的集合。且令有路上的点作成的集合。且令S=ZX,T=ZY。SUT=N(S)X S24 哥尼哥尼(Knig)第一本图论教材的撰写者第一本图论教材的撰写者 到了到了1936年，第一本图论教材才与读者见面。作者是年，第一本图论教材才与读者见面。作者是哥尼

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

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

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

21、最大数目的最大数目”对应偶图的最大匹配包含的边对应偶图的最大匹配包含的边数。数。由哥尼定理，命题得到证明。由哥尼定理，命题得到证明。(三三)、托特定理、托特定理 定理定理4(托特定理，托特定理，1947)图图G有完美匹配当且仅当对有完美匹配当且仅当对V的任意非空真子集的任意非空真子集S,有：有：注：注：o(G-S)表示奇分支数目。表示奇分支数目。28 下面分析下面分析miSG1G2Gkm1m2mk 在在Gi中，其总度数中，其总度数为为2|E(Gi)|。在在Gi中，其点在中，其点在G中的总度数为中的总度数为3|V(Gi)|。所以：所以：所以所以mi必然为奇数，但必然为奇数，但G无割边，所以无割边，所以mi3.这样这样：由托特定理，由托特定理，G有完美匹配。有完美匹配。29 注：推论中的条件是注：推论中的条件是G存在完美匹配的充分条件存在完美匹配的充分条件而不是必要条件。例如：而不是必要条件。例如：（a）没有完美匹配）没有完美匹配（b）有完美匹配）有完美匹配31Thank You!