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

习题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...