离散数学答案第七章特殊图类

第七章特殊图类习题7.11．解因m=n-1,这里m=6,所以n=6+1=7.2．解不正确。3K与平凡图构成的非连通图中有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所示。6．证明由定理1，在任意的),(mn树中，边数1nm；所以，由握手定理得)1(22)(1nmvdnii①⑴若T没有树叶，则由于T是连通图，所以T中任一结点均有2)(ivd，从而nvdnii2)(1②则①与②矛盾。⑵若树T仅有1片树叶，则其余1n个结点的度数不小于2，于是121)1(2)(1nnvdnii③从而①、③相矛盾。综合⑴，⑵得知T中至少有两片树叶。7．解图7-2⑴中共有两棵非同构的生成树（如图7-3⑴，⑵）。图7-2⑵中共有3棵非同构的生成树（如图7-3⑶，⑷，⑸）。图7-18．解在图7-4中共有8棵生成树，如图7-5⑴～⑻所示，第i生成树用)8,,2,1(iTi表示。8)()(61TWTW，6)()(52TWTW，7)()()(873TWTWTW，9)(4TW。其中T2，T5是图中的最小生成树。9．解最小生成树T如图7-7所示，W（T）=18。abcdabcdabcdabcdabcdabcdabcdabcd⑴⑵⑶⑷⑸⑹⑺⑻图7-5⑵⑴⑶⑷⑸图7-3abcd12342图7-4习题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-912367895104111236789510411图7-6图7-7图7-8即二元树有奇数个结点。5．解先根遍历：abdfgechi中根遍历：fdgbeahci后根遍历：fgdebhica6．解：习题7.31．解图⑴是偶图，互补结点子集为：},,{},,,,{21gcbVfedaV；图⑵是偶图，互补结点子集为：},,,{},,,{21gedbVfcaV；图⑶不是偶图。2．证明设G=V,E是一棵树，任选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)3758112235758111032575811151032558117151032558117213615103255811721(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所示的两个图改画为图7-14所示的两个图,可以看出图(1),(2)任何两边除在结点处相交外，无其它交叉点即可。因此,图7-13所示的两个图都是平面图.2．解图7-15⑴中有五个面，分别为F1:abea,F2:acea,F3:acda,F4:cdec,F5:abeda。它们的秩分别为r(F1)=r(F2)=r(F3)=r(F4)=3,r(F5)=4。图7-15⑵有两个面，其中有限面为F1:acfedea,无限面F2:acbcfea。它们的秩r(F1)=r(F2)=6。3．证明设该连通简单图的面数为r，由Euler公式可得，6-12+r=2，所以r=8，其8个面分别设为ri(i=1,2,┅,8)。因是简单图，故每个面至少由3条边围成。即2483)(81iirD。而由本届定理1知，241222)(81mrDii。因此每个面只能由3条边围成。4．解去掉图7-16中的两条边，并给结点表上名称的图7-17⑴，在将图7-17⑴改画图7-17⑵，而显然图7-17⑵与K5是同胚的，由库拉图斯基定理知，图7-16所示的图为非面图。5．证明若G中无圈,则G为森林,结论显然成立,若G中有圈,假设G中有n个结点,m条边,并假设G的所有连通分支为G1,G2,…,Gk,每个Gi有ni个结点,mi条边,则有，nnkii1mmkii1abcde(1)eabcdf(2)图7-15图7-17abcdefg⑴abcdefg⑵图7-16由于G是简单图,所以每个Gi也是简单图,由本节定理2的推论可知mi≤3ni-6,i=1,2,…,k。从而有63636363111nknknnmmkiikiikii）（所以m≤3n-6。再用反证法证明，简单平面图G中至少有一个度数小于等于5的结点。如果G中每个结点的度数均大于等于6,由握手定理可知niinvm16deg2）（,因此mn31,代入m≤3n-6得m≤m-6,这显然的矛盾的。故G中至少有一个度数小于等于5的结点。6．证明设G是连通平面图。假设G中每一结点v都有deg(v)≥5。因为2m≥5n,所以n≤2m/5。于是，m≤3n-6≤6m/5-6，即5m≤6m-30。因此，m≥30，与题设m30矛盾。所以G中必有一个结点的度小于或等于4。复习题71．解假设T有m条边，x个1度结点，则有：m=5+3+4+2+x-12m=5×2+3×3+4×4+2×5+x解得：x=19,m=32，即T有19个1度结点。2．证明因为，图G是连通图，所以，由本节定理2知图G存在生成树T，而生成树T的边数n-1是不超过图G的边数m的，即m≥n-1。3．证明设G的p个连通分支分别为n1，m1，n2，m2，┅，np，mp，由于森林的每个连通分支都是树，因此，有：m1=n1-1，m2=n2-1，┅，mp=np-1⑴又m1+m2+┅+mp=m;n1+n2+…+np=n⑵由（1），（2）得：m=n-p。4．证明因为，a是在T1中但不在T2中的一条边，所以，T2{a}有惟一的圈C，而T1是树，则圈C上一定有一边b不在T1中。因此，(T2-{b}){a}=T2{a}-{b}是G的生成树。下面证明，(T1-{a}){b}=T1{b}-{a}也是G的生成树，事实上，因为T1是树，所以T1中的边a是T1的割边，因此T1去掉边a后可得两个连同分支，设为T11和T12。又b不在T1中，所以T1{b}有惟一的圈C1，5．解设G中的k个连通分支为kTTT,,,21，设结点kiTvii,,2,1,。在G中添加边1,,2,1),,(1kivvii，设所得新图为T，则T连通且无回路，因此T是树。所加边的条数k-1是使得G为树的最小数目。6．解取图7-18(a)中最小权的边为e1=(d,e);再在E-{e1}取中权最小的边e2=(d,a);在E-{e1,e2}中权最小的边有两条(a,e)和(b,c)但若选(a,e)就会有圈,因此取e3=(b,c)；最后取e4=(b,c)，则得最小树如图7-18(b)，最小生成树的权为W=4+5+6+7=22。7．解题目就是求图7-19⑴的最小生成树问题。因此，图7-19⑴的最小生成树为图7-19⑵所示，即是所求的通讯线路图。其权即是最小总造价，其权为：482398431)(Tw。8．解高为2的所有不同构的二元树有7棵，如图7-20所示。其中有2棵完全二元树，图7-20中的⑸和⑺所示，有1棵满二元树，图7-20中⑺所示。9．证明方法1：设T结点数为n，分支点数为i。根据完全二元树的定义，可知下面等式均成立：tin⑴im2⑵1nm⑶由式⑴，⑵，⑶易知22tm。方法2：在完全二元树中，除树叶外，每个结点的出度为2。除树根外，每个结点的入度为1。由握手定理知ab(b)ecd7564a(a)becd16613785964图7-18图7-19abcdefg1204153816172823369⑴abcdefg1438239⑵⑵⑴⑷⑶⑸⑹⑺图7-2012)1(31231)(2)()(211tmtnntnvdvdmniniii解得：22tm。10．证明设完全二元树T有i个分支点，t片树叶，由T为完全二元树，则由7.2节定理3有1ti。又结点数tin，所以2/)1(nt为T的树叶数。11．解对于图7-21所示的二元树，三种遍历方法的结果如下：先根遍历：9875264310vvvvvvvvvv中根遍历：2978504613vvvvvvvvvv后根遍历：0257981463vvvvvvvvvv12．解设图7-22⑴所示的树为1T，1T是完全二元树。在每个分支结点引出的两条边上分别标上0（左）和1（右），则得如图7-23⑴的树，将树根到每片树叶的通路上所标的数字构成的符号串组成集合}1,011,01011,01010,0100,001,0001,0000{1B，则,1B为前缀码。设图7-22⑵中所示的树为2T，2T是二元树，但不是完全二元树。对于有一个儿子的分支结点引出的边可随便标上0或1；有两个儿子的分支点标法同1T，则得如图7-23⑵的树，所得前缀码为2B。}11,011,01010,0100,00{2B13．解：其实，)(TW等于T的各分支点的权之和，即552515105)(TW。⑵由T形成的二元前缀码为}11,10,01,001,000{B。⑴010000001111111⑵000001111图7-23⑴⑵图7-220v2v1v8v3v9v7v6v5v4v图7-2114．解应该用较短的符号串传输出现频率高的数字，因而可用100乘各数字出现的频率作为权，求最优二元树，然后用这样的二元树产生前缀码传输上面给定的数字。具体做法如下：用100乘各频率得权,10,15,20,303210。将这些权由小到大排列得到4，5，6，10，