离散数学第8章习题解答

《离散数学第8章习题解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第8章习题解答8.1图&6屮，（1）所示的图为（3,（2）所示的图为心,3,（3）所示的图为它们分别各有不同的同构形式.8.2若G为零图，用一种颜色就够了，若G是非零图的二部图,用两种颜色就够了.分析根据二部图的定义可知,n阶零图（无边的图）是三部图（含平凡图），对n阶零图的每个顶点都用同一种颜色染色，因为无边，所以，不会出现相邻顶点染同色，因而一利「颜色就够用了.8.3完全二部图K“，中的边数m-rs・分析设完全二部图k乍的顶点集为v,则v=v1uv2,v1nv2=0，且IV,1=r,IV2l=5,K⑺是简单图

2、，且％中每个顶点与岭中所有顶点和邻,而且V[中任何两个不同顶点关联的边互不相同，所以，边数8.4完全二部图心$中匹配数“=min{r,5},即/?,等于乍中的小者.分析不妨设r<5,且二部图K乍中,IV.hr,IV,

3、=5,由Hall定理可知，图中存在％到的完备匹配，设M为一个完备匹配，则％中顶点全为M饱和点，所以，0]=r.&5能安排多种方案，使每个工人去完成一项他们各a能胜任的任务.分析设％={甲,乙丙}，则％为工人集合，V2={a,b,c}f则岭为任务集合.令V二％二{(x，y)lx能胜任刃，得无向图G=<

4、V,E>,则G为二部图，见图&7所示•本题是求图屮完美匹配问题.给图中一个完美匹配就y/对应一个分配方案•图8・7满足Hall定理中的相异性条件，所以，VV存在完备匹配，又因为IV,HV2I=3,所以，完备匹配也为完美匹配.。“S&7其实,从图上，可以找到多个完美匹配.取M^{(甲Q,(乙劝,(丙,c)}此匹配对应的方案为甲完成a,乙完成b,丙完成c,见图中粗边所示的匹配.M={(甲,b),(乙,d),(丙,C)}对应的分配方案为甲完成b,乙完成a,丙完成c.请读者再找出其余的分配方案.&6本题的答案太多，如果不

5、限定画出的图为简单图，非常容易地给出4族图分别满足要求.(1)n(n为偶数，且n>2)阶圈都是偶数个顶点，偶数条边的欧拉图.(2)n(n为奇数，且/ini)阶圈都是奇数个顶点，奇数条边的欧拉图.(3)在(1)屮的圈上任选一个顶点，在此顶点处加一个环，所务图为奇数个顶点，偶数条边的欧拉图.分析上面给出的4族图都是连通的，并且所有顶点的度数都是偶数,所以，都是欧拉图.并且仃)，(2)中的图都是简单图.而(3),(4)中的图都带环，因而都是非简单图.于是,如果要求所给岀的图必须是简单图，则(3),(4)中的图不满足要求

6、.其实，欧拉图是若干个边不重的图的并，由这种性质，同样可以得到满足(3),(4)屮要求的简单欧拉图•设GG，…G是长度大于等于3的k个奇圈(长度为奇数的圈称为奇圈)，其中k为偶数，将q中某个顶点与G?中的某顶点重合,但边不重合，G2中某顶点与G3中某顶点重合，但边不重合，继续地,最后将G-中某顶点与5屮某顶点重合，边不重合，设最后得连通图为G,则G屮有奇数个顶点,偶数条边，且所有顶点度数均为偶数，所以，这样的一族图满足(4)的要求，其屮一个特例为图&8中⑴所示.在以上各图中，若G，G2,…,G*屮有一个偶圈，其他

7、条件不变，构造方法同上，则所得图G为偶数个顶点，奇数条边的简单欧拉图，满足(3)的要求，图&8屮(2)所示为一个特殊的情况.因8.8&7木题的讨论类似于&6题，只是将所有无向圈全变成有向圈即可，请读者自己画出满足要求的一些特殊有向欧拉图.8.8木题的答案也是很多的，这里给出满足要求的最简单一些图案，而且全为简单图.(1)n(n>3)阶圈，它们都是欧拉图，又都是哈密尔顿图.(2)给定R(32)个长度人于等于3的初级1111路，即圈G,G“…,Gk，用8.6题方法构造的图G均为欧拉图,但都不是哈密尔顿图，图8.8给

8、出的两个图是这里的特例.(3)n(n>4)阶圈中，找两个不相邻的顶点,在它们Z间加一条边，所得图均为哈密尔顿图，但都不是欧拉图.(4)在(2)中的图中,设存在长度大于等于4的圈，比如说5,在$中找两个不相邻的相邻顶点，在它们之间加一条新边，然后用8.6题方法构造图G,则G既不是欧拉图,也不是哈密尔顿图，见图&9所示的图.分析(1)中图满足要求是显然的•(2)屮构造的图G是连通的，并月.各顶点度数均为偶数，所以，都是欧拉图，但因为G中存在割点，将割点从G中删除，所得图至少有两个连通分支，这破坏了哈密尔顿图的必要条件

9、，所以,G不是哈密尔顿图・(3)中构造的图中，所有顶点都排在一个圈上，所以，图屮存在哈密尔顿冋路，因而为哈密尔顿图，但因图屮有奇度顶点(度数为奇数的顶点)，所以，不是欧拉图.由以上讨论可知，(4)中图既不是欧拉图，也不是哈密尔顿图.其实,读者可以找许多族图，分别满足题中的耍求.&9请读者自己讨论.8.10其逆命题不真.分析若D是强连通的有向图，则D中任何两个顶点都是相互可