图论29电子科大杨春

0.810.60.40.20xt00.511.5210.500.51n1Email:[e-mail]图论及其应用任课教师：杨春数学科学学院0.810.60.40.20xt00.511.5210.500.51n2本次课主要内容(二)、边独立集与边覆盖拉姆齐问题简介(一)、独立集与覆盖(四)、拉姆齐数r(m,n)(三)、点临界图与边临界图0.810.60.40.20xt00.511.5210.500.51n31、概念定义1设G=(V,E)是一个图。V的一个顶点子集V1称为G的一个点独立集,如果V1中的顶点互不邻接；(一)、独立集与覆盖G的一个包含顶点数最多的独立集称为G的最大独立集。最大独立集包含的顶点数，称为G的点独立数，记为α(G)。v2v1v6v5v4v3v8v7G的一个独立集v2v1v6v5v4v3v8v7G的一个最大独立集0.810.60.40.20xt00.511.5210.500.51n4定义2设G=(V,E)是一个图。V的一个顶点子集K称为G的一个点覆盖,如果E中的每条边至少有一个端点在K中。G的一个包含顶点数最少的点覆盖称为G的最小点覆盖。最小点覆盖包含的顶点数，称为G的点覆盖数，记为β(G)。v2v1v6v5v4v3v8v7G的一个点覆盖v2v1v6v5v4v3v8v7G的一个最小点覆盖0.810.60.40.20xt00.511.5210.500.51n5定理1(加莱)对任意不含孤立点的n阶图G，有：2、加莱恒等式α(G)+β(G)=n证明：一方面，设V1是G的最大点独立集。因为G中每条边的端点最多一个在V1中，所以G中每条边的端点至少有一个在V-V1中。即V-V1构成G的一个点覆盖，于是有：β(G)≦｜V-V1｜=n-α(G)另一方面，设K是G的最小点覆盖。因为G中每条边的端点至少有一个在K中，所以G中每条边的端点至多有一个在V-K中。即V-K构成G的一个点独立集，于是有：0.810.60.40.20xt00.511.5210.500.51n6α(G)≥｜V-K｜=n-β(G)由上面两个不等式，得到：α(G)+β(G)=n(二)、边独立集与边覆盖1、概念定义3设G=(V,E)是一个图。E的一个边子集E1称为G的一个边独立集,如果E1中的边互不邻接；G的一个包含边数最多的边独立集称为G的最大边独立集。最大边独立集包含的边数，称为G的边独立数，记为α‵(G)。0.810.60.40.20xt00.511.5210.500.51n7注：一个边独立集实际上就是图的一个匹配，一个最大边独立集就是图的一个最大匹配。G的一个边独立集G的一个最大边独立集定义4设G=(V,E)是一个图。E的一个边子集L称为G的一个边覆盖,如果G中的每个顶点均是L中某条边的端点。G的一个包含边数最少的边覆盖称为G的最小边覆盖。最小边覆盖包含的边数，称为G的边覆盖数，记为β‵(G)。0.810.60.40.20xt00.511.5210.500.51n8G的一个边覆盖G的一个最小边覆盖2、加莱恒等式定理2(加莱)对任意不含孤立点的n阶图G，有：α‵(G)+β‵(G)=n证明：一方面,设α‵(G)=k,则G的最大匹配由k条边组成，且覆盖了2k个顶点。所以，余下的n-2k个顶点至多需要n-2k条边就可以被覆盖，于是：β‵(G)≦k+(n-2k)=n-k。0.810.60.40.20xt00.511.5210.500.51n9所以，α‵(G)+β‵(G)≦k+(n-k)=n另一方面,设X是G的一个最小边覆盖，则｜X｜=β‵(G)。考虑导出子图F=G[X]。可以证明F中不会包含长度为3的迹。若不然，设F中包含长度为3的迹。取该迹的中间边e，显然，X-e仍然构成G的边覆盖，与X的最小性矛盾。所以，F中不包含长度为3和大于3的迹。也不包含圈。所以，F中的每个连通分支必然为星图。F是森林。因为，阶数为n，边数为n-k的森林包含k个连通分支。而F的边数为n-(n-β‵(G))，所以F有n-β‵(G)个分支。0.810.60.40.20xt00.511.5210.500.51n10从F的每个分支中选取一条边，可作成G的一个匹配，所以α‵(G)≥n-β‵(G)。由上面两个不等式，得到：α‵(G)+β‵(G)=n。例1确定下图G的α(G)，β(G)，α‵(G)，β‵(G)。1432567G解：顶点2的左右两部分均是K4,所以可以推知α(G)=2，再由加莱恒等式得：β(G)=5。0.810.60.40.20xt00.511.5210.500.51n11定理3设G是无孤立点的偶图，则G中最大点独立集包含的顶点数等于最小边覆盖所包含的边数。1432567G又因为G的阶数为7,所以，G的最大匹配包含的边数不会超过3，即α‵(G)≦3;而在G中找出了匹配：｛16，23，45｝，所以α‵(G)≥3，所以α‵(G)=3。再由加莱恒等式：β‵(G)=4.证明：首先由两个加莱恒等式得：α(G)+β(G)=α‵(G)+β‵(G)0.810.60.40.20xt00.511.5210.500.51n12其次，由第5章中的哥尼定理得：α‵(G)=β(G)所以得：α(G)=β‵(G).定理得到证明。(三)、点临界图与边临界图定义5设G=(V,E)是一个图。v是G的一个顶点，e是G的一条边。若β(G-v)β(G),称v是G的β临界点；若β(G-e)β(G),称e是G的β临界边。例如：vv是G1的2临界点e2是G2的2临界边容易知道：若v是G的一个β临界点，则：()()1GvG0.810.60.40.20xt00.511.5210.500.51n13定理4点v是图G的β临界点当且仅当v含于G的某个最小点覆盖中。证明：若点v是图G的β临界点，则：()()1GvG取G-v的一个最小点覆盖K。显然KU{v}是G的一个点覆盖。而：()11()KvGG表明KU{v}是G的一个最小点覆盖；反之，若点v含于G的某个最小点覆盖K之中。显然K-v构成G-v的点覆盖，于是有：0.810.60.40.20xt00.511.5210.500.51n14注：(1)有β临界边的图必有β临界点。(2)有β临界点的图不一定有β临界边。例如：GG的每个点均是2临界点，但它的每条边均不是2临界边。()()GvG即点v是G的一个β临界点。0.810.60.40.20xt00.511.5210.500.51n15定义6设G=(V,E)是一个图。若G的每个顶点是G的β临界点，称该图是β点临界图；若G的每条边均是G的β临界边，称该图是β边临界图。注：β边临界图一定是β点临界图，反之不一定！几个边临界图(四)、拉姆齐数r(m,n)0.810.60.40.20xt00.511.5210.500.51n16在图论问题中，极值问题是最有意义但又是最令人感到困难的问题。拉姆齐问题是极值图论中著名问题之一。Erdos教授是极值图论研究的中心人物。Bollbas教授的《极值图论》著作是经典著作。值得一提的是，97年(Fulkerson奖)，98年(Fields奖)，99年(Wolf奖)的世界三项数学大奖均与拉姆齐问题有关。定义7设m和n是两个正整数，如果存在最小的r(m,n)阶的图G,使得G中或者有Km或者有n个顶点的独立集，则称正整数r(m,n)为(m,n)拉姆齐数。0.810.60.40.20xt00.511.5210.500.51n17拉姆齐(1903---1930)英国数学家。1920年毕业于英国曼切斯特学院，随后获得奖学金入剑桥三一学院研究数学，1924年当选为该学院fellow。1925年，拉姆齐发表第一篇重要学术论文“数学的基础”。拉姆齐问题是他的第二篇文章中提出的。除数学外，拉姆齐在经济学和哲学方面兴趣很高，但主要是在哲学方面。拉姆齐工作效率很高，每天只工作4小时，其余时间全用在娱乐上。26岁时，拉姆齐意外去世。0.810.60.40.20xt00.511.5210.500.51n18求(m,n)拉姆齐数是一个非常困难的问题，以至于到目前为止，求出来的拉姆齐数还屈指可数。Erdos教授曾经开玩笑：外星人对地球人说：我们要毁灭你们，除非你们算出了r(5,5)。地球人讨论后决定，还是和外星人决以死战算了。如果用定义直接求r(m,n),一般是先恰当找出一个k阶图G1,说明它既不含Km，也不含n点独立集，得到r(m,n)k;然后再找到一个k+1阶图G2,说明它或者包含Km或者含有n点独立集，得到r(m,n)≦k+1.通过上面的方法，得到：r(m,n)=k+1。0.810.60.40.20xt00.511.5210.500.51n19例2求(1)r(1,n);(2)r(3,3)解：(1)r(1,n)=1(2)求r(3,3)一方面：注意到C5中既不含有K3，也不含有3点独立集，所以：r(3,3)≥6；另一方面：可以证明，任一6阶单图，或者含有K3，或者含有3点独立集。事实上，设V(G)=｛v1,v2,…,v6｝。考虑v1。情形1若G中至少有3个点与v1邻接。不失一般性，设v1与v2,v3,v4邻接。0.810.60.40.20xt00.511.5210.500.51n20如果v2,v3,v4互不邻接，则它们构成G的3点独立集；否则，显然在G中存在K3。情形2若G中至多有2个点与v1邻接。那么在G的补图中至少有3个顶点与v1邻接。于是由情形1，G的补图中或者存在K3或者存在3点独立集，当然在G中也就或者存在3点独立集或者存在K3.v1v4v3v2所以，r(3,3)=6。0.810.60.40.20xt00.511.5210.500.51n21拉姆齐数的计算很难，所以研究拉姆齐数的上下界是该问题的主题。下面综述一些结果。(1)Erdos教授在1935年提出如下结论：定理1对于任意两个正整数m和n,且m,n≥2,有：(,)(,1)(1,)rmnrmnrmn并且，如果r(m,n-1)和r(m-1,n)都是偶数，则上面严格不等式成立。0.810.60.40.20xt00.511.5210.500.51n22例4已知，r(2,5)=5,r(3,4)=9求(1)r(3,5);(2)r(4,4)解：(1)一方面由上面定理1：r(3,5)≦r(2,5)+r(3,4)=14另一方面可以构造出一个13阶图G，它既不含K3，又不含5点独立集。G所以，r(3,5)=14。0.810.60.40.20xt00.511.5210.500.51n23(2)一方面由上面定理1：r(4,4)≦r(3,4)+r(4,3)=18另一方面可以构造出一个17阶图G，它既不含K4，又不含4点独立集。所以，r(4,4)=18。G0.810.60.40.20xt00.511.5210.500.51n24定理2当m,n≥2时，有：2(,)1mnrmnm定义8称r(m,m)为对角线拉姆齐数。(2)Erdos教授利用概率方法证明了如下结论：定理3221(,)1(1)2nrnnone注：f(n)≥(1-o(1))g(n)表示：对任意ε0,存在自然数N，当n≥N时，有f(n)≥(1-ε)g(n)。0.810.60.40.20xt00.511.5210.500.51n25(3)1959年，Erdos教授利用随机图论方法，巧妙证明了如下结论：定理42(3,)lnnrncn1995年，贝尔实验室的年轻数学家Kim(现在微软公司，他是Erdos的学生)得到定理4的改进界：定理521(3,)lnnrncnKim由此获得1997年度的Fulkerson奖。这是图论领域的重大事件。0.810.60.40.20xt00.511.5210.500.51n26(4)对于r(m,n)的下界，1977年，Spencer利用罗瓦斯的局部引理得到：定理612(,)lnmnrmncn