资源描述：
《离散数学答案 第七章 特殊图类》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章特殊图类习题7.11．解因m=n-1,这里m=6,所以n=6+1=7.2．解不正确。与平凡图构成的非连通图中有4个结点3条边，但是它不是树。3．证明必要性。因为G中有n个结点，边数m=n-1，又因为G是连通的，由本节定理1可知，G为树，因而G中无回路。再证充分性。因为G中无回路，又因为边数m=n-1，由本节定理1，可知G为树，所以G是连通的。4．解因m=n-r,这里n=15,r=3,所以m=15-3=12，即G有12条边。5．解6个结点的所有不同构的树如图7-1所示。图7-16．证明由定理1，在任意的树中，边数；所以，由握手定理得①⑴若T没有
2、树叶，则由于T是连通图，所以T中任一结点均有，从而②则①与②矛盾。⑵若树T仅有1片树叶，则其余个结点的度数不小于2，于是③从而①、③相矛盾。综合⑴，⑵得知T中至少有两片树叶。7．解图7-2⑴中共有两棵非同构的生成树（如图7-3⑴，⑵）。图7-2⑵中共有3棵非同构的生成树（如图7-3⑶，⑷，⑸）。⑵⑴⑶⑷⑸图7-38．解在图7-4中共有8棵生成树，如图7-5⑴～⑻所示，abcd12342图7-4第i生成树用表示。，，，。其中T2，T5是图中的最小生成树。abcdabcdabcdabcdabcdabcdabcdabcd⑴⑵⑶⑷⑸⑹⑺⑻图7-59．解最小
3、生成树T如图7-7所示，W（T）=18。12367895104111236789510411图7-6图7-7习题7.2图7-81．解不一定是。如图7-8就不是根树.2．解五个结点可形成3棵非同构的无向树，如图7-9⑴，⑵，⑶所示。由⑴可生成2棵非同构的根树，如图7-9⑷，⑸所示。⑷为3元树，⑸为4元树。由⑵可生成4棵非同构的根树，如图7-9⑹，⑺，⑻，⑼所示。⑹为2元树，⑺为2元树，⑻为3元树，⑼为2元树。由⑶可生成3棵非同构的根树，如图7-9⑽，⑾，⑿所⑵⑴⑶⑷⑸⑹⑺⑻⑽⑼⑾⑿图7-9示。⑽为1元树，⑾，⑿为2元树。由此可知，五个结点共形成9棵非
4、同构的根树。3．解不是。根树中最长路径的端点一个是树根，另一个是树叶，因为根树的高等于最长路径的长度，应从树根开始。4．证明设完全二元树T有n0个叶结点，n2分支结点，则T的结点数为n=n0+n2，边数m=2n2，有握手定理可得：2n2=n0+n2-1，所以，n2=n0-1，因此，n=n0+n2=2n0-1。即二元树有奇数个结点。5．解先根遍历：abdfgechi中根遍历：fdgbeahci后根遍历：fgdebhica6．解：37581122357581110325758111510325581171510325581172136151032558
5、11721(a)(b)(c)(d)(e)(f)图7-11习题7.31．解图⑴是偶图，互补结点子集为：；图⑵是偶图，互补结点子集为：；图⑶不是偶图。2．证明设G=是一棵树，任选v0∈V，定义V的两个子集如下：,V2=V–V1。现证明V1中任二结点之间无边存在。若存在一条边(u,v)∈E，u,v∈V1,由于树中任意两个结点之间仅存在惟一一条路，设v0到u的路为v0v1v2…vku，则v0v1v2…vku的长度为偶数，因(u,v)∈E，所以v0v1v2…vkuv是v0到v的一条通路，且该通路的长度k+2为奇数，从而v0v1v2…vkuv不是路，
6、因此v必与某个vi(i=0,1,2,…,k)相同，从而vvi+1vi+2…vkuv是G中的一个圈，这与G是树矛盾。同理可证，V2中任意两个结点之间无边存在。故G中的每条边(u,v)∈E，必有u∈V1，v∈V2或u∈V2，v∈V1，因此G是具有互补结点子集V1和V2的偶图。图7-12aaabbbcccdddeeefffggg(1)(2)(3)3．解将n位男士和n位女士分别用结点表示，若某位男士认识某位女士，则在代表他们的结点之间连一条线，得到一个偶图G，它的互补结点子集V1和V2分别表示n位男士和n位女士，由题可知，V1中的每个结点度数至少为2，而V
7、2中的每个结点度数至多为2，从而它满足t条件（t=2），因此存在从V1到V2的匹配，故可将男士和女士分配为n对，使得每对中的男士和女士彼此都认识。4．解不能。用结点表示五位教师（V1）和五门课（V2），在教师和他熟悉的课程之间连一条线，得到一个偶图G，其中，V1中的孙、李、周三个结点只与数学、物理两个结点相邻接，故不满足相异性条件，因此不存在从V1到V2的匹配，故不能按题设要求的安排。习题7.41．证明将图7-13所示的两个图改画为图7-14所示的两个图,可以看出图(1),(2)任何两边除在结点处相交外，无其它交叉点即可。因此,图7-13所示的两个
8、图都是平面图.abcde(1)eabcdf(2)图7-152．解图7-15⑴中有五个面，分别为F1:abea,F2:ace
