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

习题11.11 若n个顶点的简单无向图G中至少有2个孤立点，则结论自然成立；若G中只有一个孤立点，而，则G中至少有3个顶点，其中至少有2个非孤立点，可不考虑孤立点；若G中无孤立点，则G中n个顶点度数均不小于1.现设G中n个顶点的度数均不小于1，又G为简单图，故所有顶点的度数均不大于n-1，即n个顶点的度数的取值只能是1，2，n-1,由鸽舍原理知，结论成立。2 设G有x个顶点，则34故所证不等式成立。5.（1）非同构的4个顶点的自补图只有一个；非同构的5个顶点的自补图有2个（2）为自补图与的边数相同，设均为m，又与的边数之和为的边数，即=2m，亦即=4m，故n为4的倍数，即n=4k，或n-1为4的倍数，即n=4k+1，6.（1）,均为可图解的，其对应图为非可图解，否则，设，由于要构成无向简单图，故，之间必定有边关联，这与矛盾，,非可图解，以为简单图中所有顶点的度数多为n-1。z中有奇数个，故非可图解。（2）充分性：可图解添加度数为的顶度，与度数为, ,的顶点相邻可图解。必要性：可图解，设度数为的顶点与度数分别为，的顶点相邻，删去度数为的顶点可图解。7.设的顶点为，随意用红色和蓝色涂的边，则由引出的5条边中至少有3条同色边，不妨设存在3条红色边，且该3条边的另一端点分别为，。若，构成的中的边再有一条，比如（，）为红色边，则，构成的为红色；若，的边全为蓝色，则结论已成立。习题11.21. 强分图为：单向分图为：弱分图为：2.（1）G弱连通G对应的无向图连通至少需要n-1条边连接n个顶点n-1m.G为简单图m=n(n-1),故（2）G强联通，由定理11.2.3知，G至少有n条边，故3.若G非基本回路，又G连通，则G中必有顶点的度数不等于2，矛盾。4设e含于两个不同的基本回路，与中，则不含于回路中，由推论11.2.2知，存在从到的基本回路，且不含于该基本回路中。5.设G不连通，且有个连通分支，其中有个顶点，=1，2，k。则。即，矛盾，故G连通。步骤依次对应为1，3，2，5，4，9，6，7，8，11，12，10，13=1=2，=2，=4=3，=8，=5=5，=6，=9，=9，=9，=10长度分别为4，5，4，6，5习题11.31.（1）令（2）由知，到的长度为4的通路有4条。（3）由知，到自身的长度为3的回路有3条。（4）由知，长度不超过4的通路条数为中元素之和为72，其中回路的条数为中对角线元素之和19。2.（1）令故可达矩阵3（1）习题11.41.（1）如（2）如（3）如（4）如2.(a) 通路为(b) 回路为3.(a) 是图，有一个回路为(b)非图，取则。4.设G中存在与不相邻，且，令，则为n-2个顶点的简单图，且其边数，与为简单图矛盾，故G中任意两个不相邻的顶点的度数之和均不小于n，因此，G为图。左图中有4个顶点，条边，但非图。5若G中有不相邻的两个顶点，则它们的度数之和不小于nG为图。，左图中有3个顶点，且，但非图。6，（1）acbeda 18(2)aedbca,acbdea,16习题11.51. 设，则2. 构造偶图G=，其中，适合，则G如右图所示按照中度数小的顶点，优先于中度数小的顶点匹配的原则，得一匹配也是最大匹配和完备匹配。习题11.61 若G不连通，则可适当添加边但不增加面，得连通图，设的顶点数、边数、面数分别为,，G的边数为m，则=n, m, =k。由Euler公式知-+=2m3m，即k10，而由Euler公式知，n-m+k=2即k=10，矛盾，故G的每个面均由3条边围成。6（a）非平面图， V6 V5 V2 V7 V3 V4因为含子图。 V1 V4 V6 V5（b）非平面图，因为含同胚于 V2 V7的子图（右图中删去即同构）。 V3 7 （a），虚线所示即为对偶图。 （b），虚线所示为对偶图。8（1）如第7题（a）所示。（2）G为平面图，且为平面图。连通G连通，设G的面数为k，则n=的顶点数=k。由Euler公式知，n-m+n=2,即m=2n-2。9（a）由第10题知，色数为2。（b）中含长度为奇数的基本回路，该回路上的顶点需3种色，而3种色够用，故色数为3。（c）中含长度为奇数的基本回路，该回路上的顶点需3种色，而该基本回路外另有一度数为5的顶点与该基本回路上每个顶点相邻，故至少需4种，而4种够用，故色数为4。10充分性：G中无奇数长度的基本回路G为偶图，记作G=，给中顶点着第一种色，中顶点着第二种色，则G为2可着色的。必要性：G为2可着色的，第一种色的顶点集记为，第二种色的顶点集记为，则中顶点互不相邻，中顶点也互不相邻，故G=为偶图。习题11.71 设有x个1度顶点，则2m=2(2+1+3+x-1)=x1+22+13+34x=9。2 当n=2时，,，且+=22-2，则=1，存在一棵顶点度数分别为1，1的树 ，结论成立。设n=k2时，结论成立，则n=k+1时，,中至少有一个大于1。不妨设1，否则=，则=k+12(k+1)-2，且,中至少有2个为1。不妨设=1，否则2k+1，故2(k+1)-2。由归纳假设知，存在一棵顶点度数分别为-1, ,1的无向树。在该树上添加一个度数为1的顶点，它只与度数为D的顶点相邻，则得一棵顶点度数分别为, ,1,1，即, ,的无向数。3 树中无回路树中无奇数长度的基本回路树为偶图。4 设G中有k棵树，其中第i棵树的顶点数为，边数为，则=-1，i=1，k，故m=-k=n-k。5 设G中无回路，则G的k1个连通分支也无回路，故连通分支均为树，由第4题知m=n-kn，与mn矛盾，故G中必有回路。6 （a） （b）7 不一定，如右图 5个顶点只有1顶点入度为0，其余顶点入度为1，但非有向树。8 设T中顶点数为n，其中有k个分支点，由二元正则树的定义知，n=k+t,m=2k,m=n-1m=2t-2。9 （1）、（3）非前缀码，（2）为前缀码。10题目有误，“0.6”应改为“0.06”。 为使通信中出现的二进制数字尽