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

第七章特殊图类习题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-1图7-16．证明由定理1，在任意的树中，边数；所以，由握手定理得①⑴若T没有树叶，则由于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-4abcd12342图7-4。其中T2，T5是图中的最小生成树。aabcdabcdabcdabcdabcdabcdabcdabcd⑴⑵⑶⑷⑸⑹⑺⑻图7-59．解最小生成树T如图7-7所示，W（T）=18。112367895104111236789510411图7-6图7-7习题7.2图7-81．解不一定是。如图7-8就不是根树.图7-82．解五个结点可形成3棵非同构的无向树，如图7-9⑴，⑵，⑶所示。由⑴可生成2棵非同构的根树，如图7-9⑷，⑸所示。⑷为3元树，⑸为4元树。由⑵可生成4棵非同构的根树，如图7-9⑹，⑺，⑻，⑼所示。⑹为2元树，⑺为2元树，⑻为3元树，⑼为2元树。由⑶可生成3棵非同构的根树，如图7-9⑽，⑾，⑿所⑵⑵⑴⑶⑷⑸⑸⑹⑺⑻⑽⑽⑼⑾⑿图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。即二元树有奇数个结点。5．解先根遍历：abdfgechi中根遍历：fdgbeahci后根遍历：fgdebhica6．解：33758112235758111032575811151032558117151032558117213615103255811721(a)(b)(c)(d)(e)(f)图7-11习题7.31．解图⑴是偶图，互补结点子集为：；图⑵是偶图，互补结点子集为：；图⑶不是偶图。2．证明设G=<V,E>是一棵树，任选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不是路，因此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-12图7-12aaabbbcccdddeeefffggg(1)(2)(3)3．解将n位男士和n位女士分别用结点表示，若某位男士认识某位女士，则在代表他们的结点之间连一条线，得到一个偶图G，它的互补结点子集V1和V2分别表示n位男士和n位女士，由题可知，V1中的每个结点度数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件（t=2），因此存在从V1到V2的匹配，故可将男士4．解不能。用结点表示五位教师（V1）和五门课（V2），在教师和他熟悉的课程之间连一条线，得到一个偶图G，其中，V1中的孙、李、周三个结点只与数学、物理两个结点相邻接，故不满足相异性条件，因此不存在从V1到V2的匹配，故不能按题设要求的安排。习题7.41．证明将图7-13所示的两个图改画为图7-14所示的两个图,可以看出图(1),(2)任何两边除在结点处相交外，无其它交叉点即可。因此,图7-13所示的两个图都是平面图.aabcde(1)eabcdf(2)图7-152．解图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条边围成。即。而由本届定理1知，。因此每个面只能由3条边围成。图7-17图7-17abcdefg⑴abcdefg⑵图7-164．解去掉图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条边,则有由于G是简单图,所以每个Gi也是简单图,由本节定理2的推论可知mi≤3ni-6,i=1,2,…,k。从而有所以m≤3n-6。再用反证法证明，简单平面图G中至少有一个度数小于等于5的结点。如果G中每个结点的度数均大于等于6,由握手定理可知,因此,代入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，与题设m<30矛盾。所以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个连通分支为，设结点。在G中添加边，设所得新图为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。aab(b)ecd7564a(a)becd16613785964图7-187．解题目就是求图7-19⑴的最小生成树问题。因此，图7-19⑴的最小生成树为图7-19⑵所示，即是所求的通讯线路图。其权即是最小总造价，其权为：。图7-19图7-19abcdefg1204153816172823369⑴abcdefg1438239⑵8．解高为2的所有不同构的二元树有7棵，如图7-20所示。其中有2棵完全二元树，图7-20中的⑸和⑺所示，有1棵满二元树，图7-20中⑺所示。⑵⑵⑴⑷⑶⑸⑹⑺图7-209．证明方法1：设T结点数为n，分支点数为i。根据完全二元树的定义，可知下面等式均成立：⑴⑵⑶由式⑴，⑵，⑶易知。方法2：在完全二元树中，除树叶外，每个结点的出度为2。除树根外，每个结点的入度为1。由握手定理知解得：。10．证明设完全二元树T有i个分支点，t片树叶，由T为完全二元树，则由7.2节定理3有。又结点数，所以为T的树叶数。11．解对于图7-21所示的二元树，三种遍历方法的结果如下：图7-21图7-21先根遍历：中根遍历：后根遍历：12．解设图7-22⑴所示的树为，是完全二元树。在每个分支结点引出的两条边上分别标上0（左）和1（右），则得如图7-23⑴的树，将树根到每片树叶的通路上所标的数字构成的符号串组成集合，则为前缀码。设图7-22⑵中所示的树为，是二元树，但不是完全二元树。对于有一个儿子的分支结点引出的边可随便标上0或1；有两个儿子的分支点标法同，则得如图7-23⑵的树，所得前缀码为。⑴⑴⑵图7-22⑴⑴010000001111111⑵000001111图7-2313．解：其实，等于T的各分支点的权之和，即。⑵由T形成的二元前缀码为。2235⑴510235⑵510235⑶8157510235⑷8157图7-242514．解应该用较短的符号串传输出现频率高的数字，因而可用100乘各数字出现的频率作为权，求最优二元树，然后用这样的二元树产生前缀码传输上面给定的数字。具体做法如下：用100乘各频率得权。将这些权由小到大排列得到4，5，6，10，10，15，20，30。⑴所求最优二元树如图7-25所示。⑵用所求的最优二元树产生二元前缀码如图7-25所示。带权为的树叶对应的符号串就为传输i的符号串。数字0,1,2,3,4,5,6,7对应的符号串分别为01，11，001，100，101，0001，00000，00001．⑶用这样的符号串传输按上述比例出现的数字最少。10101015156945202030301006040⑴4312507610001⑵110100001图7-25所以传输10000个上述比例出现的数字至少要用27400个二进制数字。15．证明设二部图G的互补结点子集为V1、V2，则m=V1V2且V1+V2=n，我们知道两个数的和一定，只有当它们相等时积最大，即当V1=V2=n/2时，积V1V2最大为n2/4，亦即mn2/4。16．解令V1={P1，P2，…，P7}，V2={a1，a2，…，a10}，以V1和V2的元素作结点，若Pi是aj的合格工作岗位，则在Pi和aj之间连一边，因此，可得二部图如图7-26。去掉图7-26边(P1,a4),(P1,a8),(P3,a7),(P1,a1),(P2,a2),(P5,a1),(P6,a2),(P6,a5)，则图7-26的子图如图7-27。而图7-27满足t(t=1)条件，所以，存在V1到V2的匹配M={(P1,a9),(P2,a7),(P3,a6),(P4,a3),(P5,a10),(P6,a1),(P7,a2)}，因此，图7-26中也存在V1到V2的匹配M={(P1,a9),(P2,a7),(P3,a6),(P4,a3),(P5,a10),(P6,a1),(P7,a2)}。这样安排使得所有的人都有工作。PP4P1P3P2P5P6P7a1a2a10a9a5a4a7a8a6a3图7-26PP4P1P3P2P5P6P