离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r)0∨(0∧1)0（2）（p?r）∧(﹁q∨s)（0?1）∧(1∨1)0∧10.（3）（p∧q∧r）?(p∧q∧﹁r)（1∧1∧1）?(0∧0∧0)0(4)（r∧s）→(p∧q)（0∧1）→(1∧0)0→0117．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”答：p:是无理数1q:3是无理数02是无理数1s:6能被2整除1t:6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型：4）(p→q)→(q→p)（5）(p∧r)(p∧q)6）((p→q)∧(q→r))→(p→r)答：（4）pqp→qqpq→p(p→q)→(q→p)0011111011011110010011110011所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案1用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)(∨(p∨q))∨(∨∨∨∨ppr)ppqr1所以公式类型为永真式(3)Pqrp∨qp∧r（p∨q）→(p∧r)000001001001010100011100100100101111110100111111所以公式类型为可满足式用等值演算法证明下面等值式：(2)(p→q)∧(p→r)(p→(q∧r))(4)(p∧q)∨(p∧q)(p∨q)∧(p∧q)证明（2）(p→q)∧(p→r)(p∨q)∧(p∨r)p∨(q∧r))p→(q∧r)（4）(p∧q)∨(p∧q)(p∨(p∧q))∧(q∨(p∧q)(p∨p)∧(p∨q)∧(q∨p)∧(q∨q)1∧(p∨q)∧(p∧q)∧1(p∨q)∧(p∧q)求下列公式的主析取范式与主合取范式，并求成真赋值(1)(p→q)→(q∨p)(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)2解：（1）主析取范式(p→q)→(qp)(pq)(qp)(pq)(qp)(pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq)m0m2m3(0,2,3)主合取范式：(p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(pq)M1(1)主合取范式为：(p→q)qr(pq)qr(pq)qr0所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为0主合取范式为：(p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))13所以该式为永真式.永真式的主合取范式为1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案在自然推理系统P中构造下面推理的证明：(2)前提：pq,(qr),r结论：p(4)前提：qp,qs,st,tr结论：pq证明：（2）①(qr)前提引入②qr①置换③qr②蕴含等值式④r前提引入⑤q③④拒取式⑥pq前提引入⑦￢p（3）⑤⑥拒取式证明（4）：①tr前提引入②t①化简律③qs前提引入④st前提引入⑤qt③④等价三段论⑥（qt）(tq)⑤置换⑦（qt）⑥化简⑧q②⑥假言推理⑨qp前提引入4⑩p⑧⑨假言推理(11)pq⑧⑩合取15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p(qr),sp,q结论：sr证明①s附加前提引入②sp前提引入③p①②假言推理④p(qr)前提引入⑤qr③④假言推理⑥q前提引入⑦r⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：pq,rq,rs结论：p证明：①p结论的否定引入②p﹁q前提引入③﹁q①②假言推理④￢rq前提引入⑤￢r④化简律⑥r￢s前提引入⑦r⑥化简律⑧r﹁r⑤⑦合取由于最后一步r﹁r是矛盾式,所以推理正确.第四章部分课后习题参考答案3.在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命5题的真值:(1)对于任意x,均有2=(x+)(x).(2)存在x,使得x+5=9.其中(a)个体域为自然数集合.个体域为实数集合.解：F(x):2=(x+)(x).G(x):x+5=9.(1)在两个个体域中都解释为xF(x)，在（a）中为假命题，在(b)中为真命题。(2)在两个个体域中都解释为xG(x)，在（a）(b)中均为真命题。在一阶逻辑中将下列命题符号化:没有不能表示成分数的有理数.在北京卖菜的人不全是外地人.解:(1)F(x):x能表示成分数H(x):x是有理数命题符号化为:x(F(x)H(x))(2)F(x):x是北京卖菜的人H(x):x是外地人命题符号化为:x(F(x)H(x))在一阶逻辑将下列命题符号化:火车都比轮船快.不存在比所有火车都快的汽车.解:(1)F(x):x是火车;G(x):x是轮船;H(x,y):x比y快命题符号化为:xy((F(x)G(y))H(x,y))(2)(1)F(x):x是火车;G(x):x是汽车;H(x,y):x比y快命题符号化为:y(G(y)x(F(x)H(x,y)))9.给定解释I如下:6个体域D为实数集合R.D中特定元素=0.特定函数(x,y)=xy,x,yD.(d)特定谓词(x,y):x=y,(x,y):x
,<3,3>,<4,4>}EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}DA={<2,4>}13.设A={<1,2>,<2,4>,<3,3>}B={<1,3>,<2,4>,<4,2>}求AB,AB,domA,domB,dom(AB),ranA,ranB,ran(AB),fld(A-B).解：AB={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}AB={<2,4>}domA={1,2,3}domB={1,2,4}dom(A∨B)={1,2,3,4}ranA={2,3,4}ranB={2,3,4}ran(AB)={4}A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3}14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求RR,R-1,R{0,1,},R[{1,2}]解：RR={<0,2>,<0,3>,<1,3>}12R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}R[{1,2}]=ran(R|{1,2})={2,3}16．设A={a,b,c,d}，R1，R2为A上的关系，其中R1=a,a,a,b,b,dR2a,d,b,c,b,d,c,b求R1R2,R2R1,R12,R23。解:R1R2={,,}R2R1={}R12=R1R1={,,}R22=R2R2={,,}R23=R2R22={,,}36．设A={1，2，3，4}，在AA上定义二元关系R，,AA，〈u,v>Ru+y=x+v.证明R是AA上的等价关系.确定由R引起的对AA的划分.（1）证明：∵Ru+y=x-y∴Ru-v=x-yAA∵u-v=u-vR∴R是自反的任意的,∈A×A如果R，那么u-v=x-yx-y=u-v∴R∴R是对称的任意的,,∈A×A13若R,R则u-v=x-y,x-y=a-b∴u-v=a-b∴R∴R是传递的∴R是A×A上的等价关系∏={{<1,1>,<2,2>,<3,3>,<4,4>},{<2,1>,<3,2>,<4,3>},{<3,1>,<4,2>},{<4,1>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>}}41.设A={1，2，3，4}，R为AA上的二元关系,〈a，b〉，〈c，d〉AA,〈a，b〉R〈c，d〉a+b=c+d(1)证明R为等价关系.(2)求R导出的划分.(1)证明：R∴R是自反的任意的,∈A×A设R，则a+b=c+d∴c+d=a+b∴R∴R是对称的任意的,,∈A×A若R,R则a+b=c+d,c+d=x+ya+b=x+y∴R∴R是传递的∴R是A×A上的等价关系∏={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<4,1>,<2,3>,<3,2>},{<2,4>,<4,2>,<3,3>},{<3,4>,<4,3>},{<4,4>}}43.对于下列集合与整除关系画出哈斯图:14{1,2,3,4,6,8,12,24}{1,2,3,4,5,6,7,8,9,10,11,12}解:2481281210469467235231111(1)(2)下图是两个偏序集的哈斯图.分别写出集合A和偏序关系R的集合表达式.defgfcbdbcegaa(a)(b)解:(a)A={a,b,c,d,e,f,g}R={,,,,,,,,,}IA(b)A={a,b,c,d,e,f,g}R={,,,,,,}IA分别画出下列各偏序集的哈斯图,并找出A的极大元`极小元`最大元和最小元.(1)A={a,b,c,d,e}R={,,,,,,}IA.(2)A={a,b,c,d,e},R={}IA.解:15edbcdeaabc(1)(2)项目(1)(2)极大元:ea,b,d,e极小元:aa,b,c,e最大元:e无最小元:a无第八章部分课后习题参考答案1．设f:NN,且，若为奇数1xf(x)=x若为偶数，x2求f(0),f({0}),f(1),f({1}),f({0,2,4,6,})，f({4,6,8}),f-1({3,5,7}).解：f(0)=0,f({0})={0},f(1)=1,f({1})={1},f({0,2,4,6,})=N，f({4,6,8})={2,3,4},f-1({3,5,7})={6,10,14}.判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的?(1)f:NN,f(x)=x2+2不是满射，不是单射(2)f:NN,f(x)=(x)mod3,x除以3的余数不是满射，不是单射，若为奇数(3)f:N1x不是满射，不是单射N,f(x)=，若为偶数0x0，若x为奇数(4)f:N{0,1},f(x)=是满射，不是单射1，若x为偶数(5)f:N-{0}R,f(x)=lgx不是满射，是单射(6)f:RR,f(x)=x2-2x-15不是满射，不是单射165.设X={a,b,c,d},Y={1,2,3},f={,,,}判断以下命题的真假:(1)f是从X到Y的二元关系,但不是从X到Y的函数;对(2)f是从X到Y的函数,但不是满射,也不是单射的;错(3)f是从X到Y的满射,但不是单射;错(4)f是从X到Y的双射.错第十章部分课后习题参考答案4．判断下列集合对所给的二元运算是否封闭：（1）整数集合Z和普通的减法运算。封闭,不满足交换律和结合律，无零元和单位元（2）非零整数集合普通的除法运算。不封闭（3）全体nn实矩阵集合（R）和矩阵加法及乘法运算，其中n2。封闭均满足交换律，结合律，乘法对加法满足分配律；加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，零元是零矩阵；（4）全体nn实可逆矩阵集合关于矩阵加法及乘法运算，其中n2。不封闭（5）正实数集合和运算，其中运算定义为：不封闭因为1111111R（6）n关于普通的加法和乘法运算。封闭，均满足交换律，结合律，乘法对加法满足分配律加法单位元是0，无零元；乘法无单位元（n1），零元是0；n1单位元是1（7）A={a1,a2,,an}n运算定义如下：封闭不满足交换律，满足结合律，（8）S=关于普通的加法和乘法运算。封闭均满足交换律，结合律，乘法对加法满足分配律（9）S={0,1},S是关于普通的加法和乘法运算。17加法不封闭，乘法封闭；乘法满足交换律，结合律（10）S=,S关于普通的加法和乘法运算。加法不封闭，乘法封闭，乘法满足交换律，结合律5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。见上题7．设*为Z上的二元运算x,yZ，X*Y=min(x，y),即x和y之中较小的数.(1)求4*6，7*3。4,3(2)*在Z上是否适合交换律，结合律，和幂等律？满足交换律，结合律，和幂等律求*运算的单位元，零元及Z中所有可逆元素的逆元。单位元无，零元1,所有元素无逆元8．SQQQ为有理数集，*为S上的二元运算，,S有*=（1）*运算在S上是否可交换，可结合？是否为幂等的？不可交换：*=*可结合：(*)*=*=*(*)=*=(*)*=*(*)不是幂等的（2）*运算是否有单位元，零元？如果有请指出，并求S中所有可逆元素的逆元。设是单位元，S，*=*=则==，解的=<1,0>，即为单位。设是零元，S，*=*=则==，无解。即无零元。S，设是它的逆元*=*=<1,0>==<1,0>a=1/x,b=-y/x18所以当x0时，x,y11,yxx10．令S={a，b}，S上有四个运算：*，分别有表10.8确定。(a)(b)(c)(d)这4个运算中哪些运算满足交换律，结合律，幂等律？交换律，结合律，幂等律都满足，零元为a,没有单位元；满足交换律和结合律，不满足幂等律，单位元为a,没有零元a1a,b1b(c)满足交换律,不满足幂等律,不满足结合律a(bb)aab,(ab)babaa(bb)(ab)b没有单位元,没有零元不满足交换律，满足结合律和幂等律没有单位元,没有零元求每个运算的单位元，零元以及每一个可逆元素的逆元。见上16．设V=〈N，+，〉，其中+，分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？（1）S1=是（2）S=不是加法不封闭2（3）S3={-1，0，1}不是，加法不封闭第十一章部分课后习题参考答案8.设S={0，1，2，3}，为模4乘法，即"x,y∈S,xy=(xy)mod419问〈S，〉是否构成群？为什么？解：(1)x,y∈S,xy=(xy)mod4S,是S上的代数运算。(2)x,y,z∈S,设xy=4k+r0r3(xy)z=((xy)mod4)z=rz=(rz)mod4=(4kz+rz)mod4=((4k+r)z)mod4=(xyz)mod4同理x(yz)=(xyz)mod4所以，(xy)z=x(yz)，结合律成立。(3)x∈S,(x1)=(1x)=x,，所以1是单位元。(4)111,313,0和2没有逆元所以，〈S，〉不构成群设Z为整数集合，在Z上定义二元运算。如下："x,y∈Z,xoy=x+y-2问Z关于o运算能否构成群？为什么？解：(1)x,y∈Z,xoy=x+y-2Z,o是Z上的代数运算。x,y,z∈Z,(xoy)oz=(x+y-2)oz=(x+y-2)+z-2=x+y+z-4同理(xoy)oz=xo(yoz)，结合律成立。设e是单位元，x∈Z,xoe=eox=x,即x+e-2=e+x-2=x,e=2x∈Z,设x的逆元是y,xoy=yox=e,即x+y-2=y+x-2=2,所以，x1y4x所以〈Z，o〉构成群1010101011.设G=1,,0,0，证明G关于矩阵乘法构成一个群．00111解：(1)x,y∈G,易知xy∈G,乘法是Z上的代数运算。矩阵乘法满足结合律设10是单位元，0120每个矩阵的逆元都是自己。所以G关于矩阵乘法构成一个群．设G为群，且存在a∈G,使得G={ak∣k∈Z}证明：G是交换群。证明:x,y∈G，设xak,yal，则xyakalaklalkalakyx所以，G是交换群设G为群，证明e为G中唯一的幂等元。证明:设e0G也是幂等元，则e02e0，即e02e0e，由消去律知e0e设G为群，a,b,c∈G,证明abc∣=∣bca∣=∣cab∣证明：先证设(abc)ke(bca)ke设(abc)ke,则(abc)(abc)(abc)(abc)e，即a(bca)(bca)(bca)(bca)a1e左边同乘a1，右边同乘a得(bca)(bca)(bca)(bca)(bac)ka1eae反过来，设(bac)ke,则(abc)ke.由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣19.证明：偶数阶群G必含2阶元。证明：设群G不含2阶元，aG，当ae时，a是一阶元，当ae时，a至少是3阶元,因为群G时有限阶的，所以a是有限阶的，设a是k阶的,则a1也是k阶的，所以高于3阶的元成对出现的，G不含2阶元，G含唯一的1阶元e,这与群G是偶数阶的矛盾。所以，偶数阶群G必含2阶元2120.设G为非Abel群，证明G中存在非单位元a和b,a≠b,且ab=ba.证明：先证明G含至少含3阶元。若G只含1阶元,则G={e},G为Abel群矛盾；若G除了1阶元e外,其余元a均为2阶元，则a2e，a1aa,bG,a1a,b1b,(ab)1ab,所以aba1b1(ba)1ba，与G为Abel群矛盾；所以，G含至少含一个3阶元，设为a，则aa2，且a2aaa2。令ba2的证。设G是Mn(R)上的加法群，n≥2，判断下述子集是否构成子群。（1）全体对称矩阵是子群（2）全体对角矩阵是子群3）全体行列式大于等于0的矩阵.不是子群4）全体上（下）三角矩阵。是子群设G为群，a是G中给定元素，a的正规化子N（a）表示G中与a可交换的元素构成的集合，即N（a）={x∣x∈G∧xa=ax}证明N（a）构成G的子群。证明：ea=ae,eN(a)x,yN(a),则axxa,ayyaa(xy)(ax)y(xa)yx(ay)x(ya)(xy)a,所以xyN(a)由axxa，得x1axx1x1xax1,x1aeeax1，即x1aax1，所以x1N(a)所以N（a）构成G的子群31.设1是群G1到G2的同态，2是G2到G3的同态，证明12是G1到G3的同态。证明：有已知1是G到G的函数，2是G到G的函数，则1·2是G到G的函数。122313a,bG1,(12)(ab)2(1(ab))2(1(a)1(b))(2(1(a)))(2(1(b)))(12)(a)(12)(b)所以:1·2是G1到G3的同态。证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。证明：设G是循环群,令G=,x,yG,令xak,yal,那么22xyakalaklalkalakyx,G是阿贝尔群克莱因四元群,G{e,a,b,c}eabceeabcaaecbbbceaccbae是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。设,是5元置换，且123451234521453，45123(1)计算,,1,1,1；将,1,1表成不交的轮换之积。将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。解：(1)12345123451123454532143125451231123451123452153454132(2)(1425)1(14253)1(143)(25)(3)(14)(12)(15)奇置换，1(14)(12)(15)(13)偶置换(14)(13)(25)奇置换第十四章部分课后习题参考答案5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有多少个顶点？在最少顶点的情况下，写出度数列、(G)、(G)。解：由握手定理图G的度数之和为：210203度与4度顶点各2个，这4个顶点的度数之和为14度。其余顶点的度数共有6度。其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2,所以，G至少有7个顶点,出度数列为3,3,4,4,2,2,2,(G)4,(G)2.237、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求(D),(D)，(D),(D),(D),(D).解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2.(D)3,(D)2,(D)2,(D)1,(D)2,(D)18、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？解：由握手定理图G的度数之和为：2612设2度点x个，则31512x12，x2，该图有4个顶点.14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。(1)2,2,3,3,4,4,5(2)2,2,2,2,3,3,4,4解：(1)2+2+3+3+4+4+5=23是奇数，不可图化；(2)2＋2+2+2+3+3+4+4=16,是偶数，可图化；18、设有3个4阶4条边的无向简单图G1、G2、G3，证明它们至少有两个是同构的。证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个：所以，G1、G2、G3至少有两个是同构的。20、已知n阶无向简单图G有m条边，试求G的补图G的边数m。n(n1)m解：m221、无向图G如下图24(1)求G的全部点割集与边割集，指出其中的割点和桥；(2)求G的点连通度k(G)与边连通度(G)。e1e2dbe5e4e3ce解：点割集:{a,b},(d)边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}k(G)=(G)=123、求G的点连通度k(G)、边连通度(G)与最小度数(G)。解：k(G)2、(G)3、(G)428、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？3n2m得n=6,m=9.解：3m2n31、设图G和它的部图G的边数分别为m和m，试确定G的阶数。n(n1)118(mm)解：mm得n2245、有向图D如图(1)求v2到v5长度为1，2，3，4的通路数；(2)求v5到v5长度为1，2，3，4的回路数；(3)求D中长度为4的通路数；(4)求D中长度小于或等于4的回路数；25(5)写出D的可达矩阵。v1v4v5v2v3解：有向图D的邻接矩阵为：000010101020200101000000202020A00001，A201010A32020010100000020202001010202000000400004012154040052522A400004AA2A3A42121540400425220404025254v2到v5长度为1，2，3，4的通路数为0,2,0,0；v5到v5长度为1，2，3，4的回路数为0,0,4,0；(3)D中长度为4的通路数为32；(4)D中长度小于或等于4的回路数10；1111111111(4)出D的可达矩阵P111111111111111第十六章部分课后习题参考答案1、画出所有5阶和7阶非同构的无向树.262、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点?解：设3度分支点x个，则51323x2(53x1)，解得x3T有11个顶点3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。解：设4度分支点x个，则81234x2(82x1)，解得x2度数列4、棵无向树T有ni(i=2，3，，k)个i度分支点，其余顶点都是树叶，问T应该有几片树叶?解：设树叶x片，则niix12(nix1)，解得x(i2)ni2评论：2，3，4题都是用了两个结论,一是握手定理，二是mn15、n(n≥3)阶无向树T的最大度至少为几？最多为几？解：2，n-16、若n(n≥3)阶无向树T的最大度=2，问T中最长的路径长度为几？解：n-17、证明：n(n≥2)阶无向树不是欧拉图.27证明：无向树没有回路，因而不是欧拉图。8、证明：n(n≥2)阶无向树不是哈密顿图.证明：无向树没有回路，因而不是哈密顿图。9、证明：任何无向树T都是二部图.证明：无向树没有回路，因而不存在技术长度的圈，是二部图。10、什么样的无向树T既是欧拉图，又是哈密顿图?解：一阶无向树14、设e为无向连通图G中的一条边，e在G的任何生成树中，问e应有什么性质?解：e是桥15、设e为无向连通图G中的一条边，e不在G的任何生成树中，问e应有什么性质?解：e是环23、已知n阶m条的无向图G是k(k≥2)棵树组成的森林，证明：m=n-k.；证明：数学归纳法。k=1时,m=n-1，结论成立；设k=t-1(t-11)时，结论成立，当k=t时,无向图G是t棵树组成的森林,任取两棵树，每棵树任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m=n-（k-1）.所以原图中m=n-k得证。24、在图16.6所示2图中，实边所示的生成子图T是该图的生成树.(1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统.(2)指出T的所有树枝，及每条树枝对应的基本割集和对应T的基本割集系统.(a)(b)图16.16解：(a)T的弦：c,d,g,hT的基本回路系统:S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}}T的所有树枝:e,a,b,fT的基本割集系统:S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}}有关问题仿照给出2825、求图16.17所示带权图中的最小生成树.(a)(b)图16.17解：注：答案不唯一。37、画一棵权为3，4，5，6，7，8，9的最优2叉树，并计算出它的权.38.下面给出的各符号串集合哪些是前缀码?A1={0，10，110，1111}是前缀码A2={1，01，001，000}是前缀码A3={1，11，101，001，0011}不是前缀码A4={b，c，aa，ac，aba，abb，abc}是前缀码A5={b，c，a，aa，ac，abc，abb，aba}不是前缀码41.设7个字母在通信中出现的频率如下:a:35%b:20%c:15%d:10%e:10%f:5%g:5%29用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.并指出传输10n(n≥2)个按上述频率出现的字母，需要多少个二进制数字.解：a:01b:10c:000d:110e:001f:1111g:1110W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255传输10n(n≥2)个按上述频率出现的字母，需要255*10n-2个二进制数字.30
浙公网安备 33021202002483