电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

离散数学第11章答案(刘玉珍 刘永梅) VIP免费

离散数学第11章答案(刘玉珍 刘永梅) _第1页
1/14
离散数学第11章答案(刘玉珍 刘永梅) _第2页
2/14
习题11.11.若n个顶点的简单无向图G中至少有2个孤立点,则结论自然成立;若G中只有一个孤立点,而2n,则G中至少有3个顶点,其中至少有2个非孤立点,可不考虑孤立点;若G中无孤立点,则G中n个顶点度数均不小于1.现设G中n个顶点的度数均不小于1,又G为简单图,故所有顶点的度数均不大于n-1,即n个顶点的度数的取值只能是1,2,„,n-1,由鸽舍原理知,结论成立。2.设G有x个顶点,则92)6(36)deg(122xxvVv3.mnknknnknvmkkkVv2)1()1()()deg(24.VvVvvnvmVvvn})max{deg()deg(2})deg(min{故所证不等式成立。5.(1)非同构的4个顶点的自补图只有一个;非同构的5个顶点的自补图有2个(2)G为自补图G与G的边数相同,设均为m,又G与G的边数之和为nK的边数2)1(nn,即2)1(nn=2m,亦即)1(nn=4m,故n为4的倍数,即n=4k,或n-1为4的倍数,即n=4k+1,Ik6.(1)<0,1,1,2,3,3>,<3,3,3,3>均为可图解的,其对应图为<1,3,3,3>非可图解,否则,设3)deg()deg()deg(,1)deg(4321vvvv,由于要构成无向简单图,故,1v,2v,3v,4v之间必定有边关联,这与1)deg(1v矛盾,<2,3,4,4,5>,<2,2,4>非可图解,以为简单图中所有顶点的度数多为n-1。<1,2,2,3,4,5>z中有奇数个,故非可图解。(2)充分性:<1d2,1d3,„,1d1d,1d1d1,2d1d,„,nd>可图解添加度数为1d的顶度,与度数为1d2,1d3,„,1d1d,1d1d1的顶点相邻<1d,2d,„,nd>可图解。必要性:<1d,2d,„,nd>可图解,设度数为1d的顶点与度数分别为2d,„,1d1d的顶点相邻,删去度数为1d的顶点<1d2,1d3,„,1d1d,1d1d1,2d1d,„,nd>可图解。7.设6K的顶点为1V,2V,„,6V,随意用红色和蓝色涂6K的边,则由1V引出的5条边中至少有3条同色边,不妨设存在3条红色边,且该3条边的另一端点分别为2V,3V,4V。若2V,3V,4V构成的3K中的边再有一条,比如(2V,3V)为红色边,则1V,2V,4V构成的3K为红色;若2V,3V,4V的边全为蓝色,则结论已成立。习题11.21.强分图为:单向分图为:弱分图为:2.(1)G弱连通G对应的无向图连通至少需要n-1条边连接n个顶点n-1m.G为简单图m)(EnK=n(n-1),故)1(1nnmn(2)G强联通,由定理11.2.3知,G至少有n条边,故)1(nnmn3.若G非基本回路,又G连通,则G中必有顶点的度数不等于2,矛盾。4.设e含于两个不同的基本回路221eevv„1vek,与,221eevv„1,vei中,则e不含于回路kev1„,22eev„1,vei中,由推论11.2.2知,存在从1v到1v的基本回路,且e不含于该基本回路中。5.设G不连通,且有2k个连通分支,1G,2G,„,kG,其中iG有in个顶点,i=1,2,„,k。则2)1(2)1(2211nnnnm„2)1(kknn2)1)(1(2)1)(1(21nnnn„2)1)(1(knn2))(1(knn2)2)(1(nn。即m2)2)(1(nn,矛盾,故G连通。步骤依次对应为1,3,2,5,4,9,6,7,8,11,12,10,130V2V=10V4V=210VV,0V2V1V=210VV6V,0V2V1V6V=40V32VV=310VV76VV11V,0V2V1V76VV11V,0V4V8V11V=810VV76VV,0V2V1V76VV=50V4V8V=510VV5V,0V2V1V5V,10VV6V5V,0V2V1V65VV=610VV6V10V,0V2V1V6V10V=90V4V8V12V,10VV76VV1211VV,0V4V8V1211VV=910VV5V9V,0V2V1V5V9V,10VV6V5V9V,0V2V1V6V5V9V=910VV6V10V13V,0V2V1V6V10V13V,0V4V8V12V13V,10VV76VV1211VV13V,0V4V8V1211VV13V=10长度分别为4,5,4,6,5习题11.31.(1)0100100001010111A10000100111112122A01001000131224233A10000100342347354A令432AAAAB220022005947714711(2)由4A知,1V到4V的长度为4的通路有4条。(3)由3A知,1V到自身的长度为3的回路有3条。(4)由B知,长度不超过4的通路条数为B中元素之和为72,其中回路的条数为B中对角线元素之和19。2.(1)0100011000000100010100010A1100012000001010002000101...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

离散数学第11章答案(刘玉珍 刘永梅)

您可能关注的文档

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部