资源描述：
《离散数学第11章答案刘玉珍 刘永梅.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、习题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个顶点，则3．4．故所证不等式成立。5.（1）非同构的4个顶点的自补图只有一个；非同构的5个顶点的自补图有2个（2）为自补图与的边数相同，设均为m，又与的边数之和为的边数，即=2m，亦即=4m，故n为4的倍数，即n
2、=4k，或n-1为4的倍数，即n=4k+1，6.（1）<0,1,1,2,3,3>,<3,3,3,3>均为可图解的，其对应图为<1,3,3,3>非可图解，否则，设，由于要构成无向简单图，故，，，，之间必定有边关联，这与矛盾，<2，3，4，4，5>,<2,2,4>非可图解，以为简单图中所有顶点的度数多为n-1。<1,2,2,3,4,5>z中有奇数个，故非可图解。（2）充分性：<,,…,,,,…,>可图解添加度数为的顶度，与度数为,,…,,的顶点相邻<,,…,>可图解。必要性：<,,…,>可图解，设度数为的顶点与度数分别为，…，的顶点相邻，删去度数为的顶点<,,…,,,,…,>可图解。7
3、.设的顶点为，，…，，随意用红色和蓝色涂的边，则由引出的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.
4、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.（
5、1）如（2）如（3）如（4）如2.(a)通路为(b)回路为3.(a)是图，有一个回路为(b)非图，取则。4.设G中存在与不相邻，且，令，则为n-2个顶点的简单图，且其边数，与为简单图矛盾，故G中任意两个不相邻的顶点的度数之和均不小于n，因此，G为图。左图中有4个顶点，条边，但非图。5若G中有不相邻的两个顶点，则它们的度数之和不小于nG为图。，左图中有3个顶点，且，，但非图。6，（1）acbeda18(2)aedbca,acbdea,16习题11.51.设，则1.构造偶图G=<,,>，其中…，…适合，则G如右图所示按照中度数小的顶点，优先于中度数小的顶点匹配的原则，得一匹配也是最大匹
6、配和完备匹配。习题11.61．若G不连通，则可适当添加边但不增加面，得连通图，设的顶点数、边数、面数分别为,,，G的边数为m，则=n,>m,=k。由Euler公式知-+=2m<=n+k-2，由定理11.6.3知≤3n-6，故n+k-2≤3n-6，即k≤2n-4。若G连通，则n-m+k=2，又m≤3n-6，故k≤2n-4。2．如G：，则：G,均为平面图。3．设G与均为平面图，且均连通，G与的边数分别为m与，则m≤3n-6,≤3n-6(若G与不连通，则可适当添加边使之为连通平面图，不等式仍成立)。而，矛盾，故G或非平面图。4．不妨设G连通，否则，G的每个连通分支的边数均应小于30，则可
7、对G的每个分支进行讨论。若G中无回路，则G必为树，结论显然成立。若G中有回路，则简单图G中每个面至少由3条边围成，故G至少有3个顶点，从而。若G中所有顶点的度数均不小于5，则，与矛盾，故结论成立。1．（1）设G不连通，且有个连通分支,，设的顶点数为，边数为，i=1,2,,k。若，则k=2，因为此时G为一个平面图，并上一个才能使其边数为15，但含子图，故为非平面图，与G为平面图矛盾；若，则简单图中至多只有一条边，另外5个顶点构成时边数最多，但也只有10条边，与G有15条
