离散数学课后习题答案第七章 VIP专享VIP免费

第七章特殊图类习题7.11．解因m=n-1,这里m=6,所以n=6+1=7.2．解不正确。与平凡图构成的非连通图中有4个结点3条边，但是它不是树。3K3．证明必要性。因为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，在任意的树中，边数),(mn1−=nm；所以，由握手定理得)1(22)(1−==∑=nmvdnii①⑴若T没有树叶，则由于T是连通图，所以T中任一结点均有，从而2)(≥ivdnvdnii2)(1≥∑=②则①与②矛盾。⑵若树T仅有1片树叶，则其余1−n个结点的度数不小于2，于是121)1(2)(1−=+−≥∑=nnvdnii③从而①、③相矛盾。综合⑴，⑵得知T中至少有两片树叶。7．解图7-2⑴中共有两棵非同构的生成树（如图7-3⑴，⑵）。图7-2⑵中共有3棵非同构的生成树（如图7-3⑶，⑷，⑸）。⑵⑴⑶⑷⑸图7-38．解在图7-4中共有8棵生成树，如图7-5⑴～⑻所示，第i生成树用表示。，，，)8,,2,1(=iTi7)(8=TW8)()(61==TWTW6)()(52==TWTW)()(73==TWTW9)(4=TW。其中T2，T5是图中的最小生成树。9．解最小生成树T如图7-7所示，W（T）=18。abcdabcdabcdabcdabcdabcdabcdabcd⑴⑵⑶⑷⑸⑹⑺⑻图7-5abcd12342图7-412367895104111236789510411图7-6图7-7习题7.21．解不一定是。如图7-8就不是根树.2．解五个结点可形成3棵非同构的无向树，如图7-9⑴，⑵，⑶所示。由⑴可生成2棵非同构的根树，如图7-9⑷，⑸所示。⑷为3元树，⑸为4元树。由⑵可生成4棵非同构的根树，如图7-9⑹，⑺，⑻，⑼所示。⑹为2元树，⑺为2元树，⑻为3元树，⑼为2元树。由⑶可生成3棵非同构的根树，如图7-9⑽，⑾，⑿所⑷⑴⑵⑶⑸⑺⑻⑹示。⑽为1元树，⑾，⑿为2元树。由此可知，五个结点共形成9棵非同构的根树。3．解不是。根树中最长路径的端点一个是树根，另一个是树叶，因为根树的高等于最长路径的长度，应从树根开始。4．证明设完全二元树T有n0个叶结点，n2分支结点，则T的结点数为n=n0+n2，边数m=2n2，有握手定理可得：2n2=n0+n2-1，所以，n2=n0-1，因此，n=n0+n2=2n0-1。⑽⑼⑾⑿图7-9图7-8即二元树有奇数个结点。5．解先根遍历：abdfgechi中根遍历：fdgbeahci后根遍历：fgdebhica6．解：习题7.31．解图⑴是偶图，互补结点子集为：；图⑵是偶图，互补结点子集为：；图⑶不是偶图。},,{},,,,{21gcbVfedaV==},,,{},,,{21gedbVfcaV==2．证明设G=是一棵树，任选v0∈V，定义V的两个子集如下：}),({01为偶数vvdvV=,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不是路，因此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)3758112235758111032575811151032558117151032558112136151032755811217(a)(b)(c)(d)(e)(f)图7-113．解将n位男士和n位女士分别用结点表示，若某位男士认识某位女士，则在代表他们的结点之间连一条线，得到一个偶图G，它的互补结点子集V1和V2分别表示n位男士和n位女士，由题可知，V1中的每个结点度数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件（t=2），因此存在从V1到V2的匹配，故可将男士和女士分配为n对，使得每对中的男士和女士彼此都认识。4．解不能。用结点表示五位教师（V1）和五门课（V2），在教师和他熟悉的课程之间连一条线，得到一个偶图G，其中，V1中的孙、李、周三个结点只与数学、物理两个结点相邻接，故不满足相异性条件，因此不存在从V1到V2的匹配，故不能按题设要求的安排。习题7.41．证明将图7-13所示的两个...