离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案.doc

_离散数学答案 屈婉玲版第二版 高等教育出版社课后答案第一章部分课后习题参考答案16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p(qr) 0(01) 0 （2）（pr）(qs) （01）(11) 010. （3）（pqr）(pqr) （111） (000)0(4)（rs）(pq) （01）(10) 00117判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则也是无理数。另外6能被2整除，6才能被4整除。”答：p: 是无理数 1 q: 3是无理数 0 r: 是无理数 1 s:6能被2整除 1t: 6能被4整除 0 命题符号化为： p(qr)(ts)的真值为1，所以这一段的论述为真。19用真值表判断下列公式的类型：（4）(pq) (qp)（5）(pr) (pq)（6）(pq) (qr) (pr)答： （4） p q pq q p qp (pq)(qp) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) (pqq)(2)(p(pq)(pr)(3)(pq)(pr)答：(2)（p(pq)）(pr)(p(pq)(pr)ppqr1 所以公式类型为永真式(3) P q r pq pr （pq）(pr)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1 所以公式类型为可满足式4.用等值演算法证明下面等值式：(2)(pq)(pr)(p(qr)(4)(pq)(pq)(pq) (pq)证明（2）(pq)(pr) (pq)(pr)p(qr)p(qr)（4）(pq)(pq)(p(pq) (q(pq)(pp)(pq)(qp) (qq)1(pq)(pq)1(pq)(pq) 5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(pq)(qp)(2)(pq)qr(3)(p(qr)(pqr)解：（1）主析取范式(pq)(qp) (pq)(qp) (pq)(qp) (pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq) (0,2,3) 主合取范式： (pq)(qp) (pq)(qp) (pq)(qp) (p(qp)(q(qp) 1(pq) (pq) M1 (1) (2) 主合取范式为： (pq)qr(pq)qr (pq)qr0 所以该式为矛盾式. 主合取范式为(0,1,2,3,4,5,6,7) 矛盾式的主析取范式为 0 (3)主合取范式为：(p(qr)(pqr) (p(qr)(pqr)(p(qr)(pqr)(p(pqr)(qr)(pqr) 11 1 所以该式为永真式. 永真式的主合取范式为 1 主析取范式为(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统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 前提引入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 结论的否定引入pq 前提引入q 假言推理rq 前提引入r 化简律rs 前提引入r 化简律rr 合取由于最后一步rr 是矛盾式,所以推理正确.第四章部分课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1) 对于任意x,均有x2-2=(x+2)(x-2).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合. (b)个体域为实数集合.解：F(x): x2-2=(x+2)(x-2). G(x): x+5=9.(1)在两个个体域中都解释为，在（a）中为假命题，在(b)中为真命题。(2)在两个个体域中都解释为，在（a）(b)中均为真命题。4. 在一阶逻辑中将下列命题符号化:(1) 没有不能表示成分数的有理数.(2) 在北京卖菜的人不全是外地人.解:(1)F(x): x能表示成分数 H(x): x是有理数命题符号化为: (2)F(x): x是北京卖菜的人 H(x): x是外地人命题符号化为: 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解:(1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快命题符号化为: (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快命题符号化为: 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素a =0. (c) 特定函数f(x,y)=x-y,x,y. (d) 特定谓词F(x,y):x=y,G(x,y):x<y,x,y. 说明下列公式在I下的含义,并指出各公式的真值:(1)(2)答:(1) 对于任意两个实数x,y,如果x<y, 那么xy. 真值1.(2) 对于任意两个实数x,y,如果x-y=0, 那么x<y. 真值0.10. 给定解释I如下： （a） 个体域D=N(N为自然数集合). （b） D中特定元素a=2. （c） D上函数fx,y =x+y,g(x,y)=xy. （d） D上谓词F(x,y):x=y.说明下列各式在I下的含义，并讨论其真值.(1) xF(g(x,a),x)(2) xy(F(f(x,a),y)F(f(y,a),x)答:(1) 对于任意自然数x, 都有2x=x, 真值0.(2) 对于任意两个自然数x,y,使得如果x+2=y, 那么y+2=x. 真值0.11. 判断下列各式的类型:(1) Fx,yGx,yFx,y.(3) xyF(x,y)xyF(x,y).解:(1)因为 为永真式； 所以 Fx,yGx,yFx,y.为永真式；(3)取解释I个体域为全体实数F(x,y)：x+y=5所以,前件为任意实数x存在实数y使x+y=5，前件真；后件为存在实数x对任意实数y都有x+y=5，后件假，此时为假命题再取解释I个体域为自然数N，F(x,y)：:x+y=5所以,前件为任意自然数x存在自然数y使x+y=5，前件假。此时为假命题。此公式为非永真式的可满足式。13. 给定下列各公式一个成真的解释，一个成假的解释。(1) x(F(x)G(x)(2) x(F(x)G(x)H(x)解:(1)个体域:本班同学F(x)：x会吃饭, G(x)：x会睡觉.成真解释F(x)：x是泰安人,G(x)：x是济南人.（2）成假解释(2)个体域:泰山学院的学生F(x)：x出生在山东,G(x):x出生在北京,H(x):x出生在江苏,成假解释.F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸. 成真解释.第五章部分课后习题参考答案5.给定解释如下:(a)个体域D=3,4;(b)f为(c). 试求下列公式在下的真值.(1) (3)解:(1) (2) 12.求下列各式的前束范式。(1) (5) (本题课本上有错误)解:(1) (5) 15.在自然数推理系统F中,构造下面推理的证明:(1) 前提: ,结论: xR(x)(2) 前提: x(F(x)(G(a)R(x), xF(x)结论:x(F(x)R(x)证明(1) 前提引入 F(c) EI 前提引入 假言推理 (F(c)G(c)R(c) UI F(c)G(c) 附加 R(c) 假言推理 xR(x) EG(2)xF(x) 前提引入F(c) EIx(F(x)(G(a)R(x) 前提引入F(c)(G(a)R(c) UIG(a)R(c) 假言推理R(c) 化简F(c)R(c) 合取引入x(F(x)R(x) EG 第六章部分课后习题参考答案5.确定下列命题是否为真：（1） 真 （2） 假（3） 真（4） 真（5）a,ba,b,c,a,b,c 真（6）a,ba,b,c,a,b 真（7）a,ba,b,a,b 真（8）a,ba,b,a,b 假6设a,b,c各不相同，判断下述等式中哪个等式为真:（1）a,b，c,=a,b,c 假（2）a ,b,a=a,b 真（3）a，b=a,b 假（4），a,b=,a,b 假8求下列集合的幂集：（1）a,b,c P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c（2）1，2，3 P(A)= , 1, 2,3, 1，2，3 （3） P(A)= , （4）， P(A)= , 1, 2,3, 1，2，3 14化简下列集合表达式：（1）（AB）B ）-（AB）（2）（ABC）-（BC）A解:(1)（AB）B ）-（AB）=（AB）B ）（AB）=（AB）（AB）)B=B=（2）（ABC）-（BC）A=（ABC）（BC）A=（A（BC）（BC ）（BC）A=（A（BC）A=（A（BC）A=A18某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。解: 阿A=会打篮球的人，B=会打排球的人，C=会打网球的人 |A|=14, |B|=12, |AB|=6,|AC|=5,| ABC|=2, |C|=6,CAB如图所示。25-(5+4+2+3)-5-1=25-14-5-1=5不会打球的人共5人21.设集合A1，2，2，3，1，3,计算下列表达式：（1）A（2）A（3）A（4）A解: （1）A=1，22，31，3=1，2，3,（2）A=1，22，31，3=（3）A=123= （4）A=27、设A,B,C是任意集合，证明(1)(A-B)-C=A- BC(2)(A-B)-C=(A-C)-(B-C)证明(1) (A-B)-C=(AB) C= A( BC)= A(BC) =A- BC(2) (A-C)-(B-C)=(AC) (B C)= (AC) (BC)=(ACB) (ACC)= (ACB) = A(BC) =A- BC 由（1）得证。第七章部分课后习题参考答案7.列出集合A=2,3,4上的恒等关系I A,全域关系EA,小于或等于关系LA,整除关系DA.解：IA =<2，2>,<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(AB)=1,2,3,4ranA=2,3,4 ranB=2,3,4ran(AB)=4A-B=<1,2>,<3,3>，fld(A-B)=1,2,314.设R=<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>求RR, R-1, R0,1, R1,2解：RR=<0,2>,<0,3>,<1,3> R-1,=<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>R0,1=<0,1>,<0,2>,<0,3>,<1,2>,<1,3>R1,2=ran(R|1,2)=2,316设A=a,b,c,d，为A上的关系，其中=求。解: R1R2=<a,d>,<a,c>,<a,d> R2R1=<c,d>R12=R1R1=<a,a>,<a,b>,<a,d>R22=R2R2=<b,b>,<c,c>,<c,d>R23=R2R22=<b,c>,<c,b>,<b,d>36设A=1，2，3，4，在AA上定义二元关系R， <u,v>,<x,y>AA ，u,v> R <x,y>u + y = x + v.(1) 证明R 是AA上的等价关系.(2)确定由R 引起的对AA的划分.（1）证明：<u,v>R<x,y> u+y=x-y<u,v>R<x,y>u-v=x-y<u,v>AAu-v=u-v<u,v>R<u,v>R是自反的任意的<u,v>,<x,y>A×A如果<u,v>R<x,y> ，那么u-v=x-yx-y=u-v <x,y>R<u,v> R是对称的任意的<u,v>,<x,y>,<a,b>A×A若<u,v>R<x,y>,<x,y>R<a,b>则u-v=x-y,x-y=a-bu-v=a-b <u,v>R<a,b>R是传递的R是A×A上的等价关系(2) =<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，bRc，da + b = c + d(1) 证明R为等价关系.(2) 求R导出的划分.(1)证明：<a，b AA a+b=a+b<a,b>R<a,b> R是自反的任意的<a,b>,<c,d>A×A设<a,b>R<c,d>，则a+b=c+dc+d=a+b <c,d>R<a,b>R是对称的任意的<a,b>,<c,d>,<x,y>A×A若<a,b>R<c,d>,<c,d>R<x,y>则a+b=c+d,c+d=x+ya+b=x+y <a,b>R<x,y>R是传递的R是 A×A上的等价关系(2)=<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. 对于下列集合与整除关系画出哈斯图:(1) 1,2,3,4,6,8,12,24(2) 1,2,3,4,5,6,7,8,9,10,11,12解: (1) (2)45.下图是两个偏序集<A,R>的哈斯图.分别写出集合A和偏序关系R的集合表达式. (a) (b)解: (a)A=a,b,c,d,e,f,g R=<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g> (b) A=a,b,c,d,e,f,gR=<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>46.分别画出下列各偏序集<A,R>的哈斯图,并找出A的极大元极小元最大元和最小元.(1)A=a,b,c,d,eR=<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>IA.(2)A=a,b,c,d,e, R=<c,d>IA.解: (1) (2)项目 (1) (2)极大元: e a,b,d,e 极小元: a a,b,c,e最大元: e 无最小元: a 无第八章部分课后习题参考答案1 设f :NN,且 f (x)=求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.4. 判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的? (1) f:NN, f(x)=x2+2 不是满射，不是单射 (2) f:NN,f(x)=(x)mod 3,x除以3的余数 不是满射，不是单射 (3) f:NN,f(x)= 不是满射，不是单射 (4) f:N0,1,f(x)= 是满射，不是单射 (5) f:N-0R,f(x)=lgx 不是满射，是单射 (6) f:RR,f(x)=x2-2x-15 不是满射，不是单射5. 设X=a,b,c,d,Y=1,2,3,f=<a,1>,<b,2>,<c,3>,判断以下命题的真假: (1)f是从X到Y的二元关系,但不是从X到Y的函数; 对 (2)f是从X到Y的函数,但不是满射,也不是单射的; 错 (3)f是从X到Y的满射,但不是单射; 错 (4)f是从X到Y的双射. 错第十章部分课后习题参考答案4判断下列集合对所给的二元运算是否封闭：（1） 整数集合Z和普通的减法运算。封闭,不满足交换律和结合律，无零元和单位元（2） 非零整数集合Z*和普通的除法运算。不封闭（3） 全体实矩阵集合Mn（R）和矩阵加法及乘法运算，其中n2。封闭 均满足交换律，结合律，乘法对加法满足分配律；加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，零元是零矩阵；（4）全体实可逆矩阵集合关于矩阵加法及乘法运算，其中n2。不封闭（5）正实数集合R+和 ° 运算，其中 ° 运算定义为： a，b R+，a ° b = ab-a-b 不封闭 因为 （6） Z+, nZ=nz z Z .nZ关于普通的加法和乘法运算。封闭，均满足交换律，结合律，乘法对加法满足分配律加法单位元是0，无零元；乘法无单位元（），零元是0；单位元是1（7）A = n2. ° 运算定义如下： a，b A，a ° b = b 封闭 不满足交换律，满足结合律，（8）S = 2x-1xZ+关于普通的加法和乘法运算。封闭 均满足交换律，结合律，乘法对加法满足分配律（9）S = 0,1,S是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律（10）S = x x=2n,nZ+ ,S关于普通的加法和乘法运算。加法不封闭，乘法封闭，乘法满足交换律，结合律5对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题7设 * 为上的二元运算，X * Y = min ( x，y ),即x和y之中较小的数.(1) 求4 * 6，7 * 3。 4, 3(2)* 在上是否适合交换律，结合律，和幂等律？满足交换律，结合律，和幂等律(3)求*运算的单位元，零元及中所有可逆元素的逆元。单位元无，零元1, 所有元素无逆元8 为有理数集，*为S上的二元运算，<a,b>,<x,y > S有 < a，b >*<x，y> = <ax，ay + b>（1）*运算在S上是否可交换，可结合？是否为幂等的？不可交换：<x,y>*<a,b >= <xa，xb +y>< a，b >*<x，y>可结合：(<a,b >*<x,y>)*<c,d>=<ax，ay + b>*<c,d>=<axc，axd +(ay+b) ><a,b >*(<x,y>*<c,d>)=<a, b>*<xc,xd+y>=<axc，a(xd +y)+b >(<a,b >*<x,y>)*<c,d>=<a,b >*(<x,y>*<c,d>)不是幂等的（2）*运算是否有单位元，零元？ 如果有请指出，并求S中所有可逆元素的逆元。 设<a,b>是单位元，<x,y > S ，<a,b >*<x,y>= <x,y>*<a,b >=<x,y> 则<ax,ay+b>=<xa,xb+y>=<x,y>，解的<a,b>=<1,0>，即为单位。设<a,b>是零元，<x,y > S ，<a,b >*<x,y>= <x,y>*<a,b >=<a,b> 则<ax,ay+b>=<xa,xb+y>=<a,b>，无解。即无零元。<x,y > S，设<a,b>是它的逆元<a,b >*<x,y>= <x,y>*<a,b >=<1,0><ax,ay+b>=<xa,xb+y>=<1,0>a=1/x,b=-y/x所以当x0时，10令S=a，b，S上有四个运算：*，°，和分别有表10.8确定。 (a) (b) (c) (d)(1)这4个运算中哪些运算满足交换律，结合律，幂等律？(a) 交换律，结合律，幂等律都满足， 零元为a,没有单位元；(b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 (c)满足交换律,不满足幂等律,不满足结合律 没有单位元, 没有零元(d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元(2) 求每个运算的单位元，零元以及每一个可逆元素的逆元。见上16设V= N，+ ， ，其中+ ，分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？（1）S1=2n nZ 是（2）S2=2n+1 nZ 不是 加法不封闭（3）S3 = -1，0，1 不是，加法不封闭第十一章部分课后习题参考答案8.设S=0，1，2，3，为模4乘法，即 "x,yS, xy=(xy)mod 4 问S，是否构成群？为什么？解：(1) x,yS, xy=(xy)mod 4,是S上的代数运算。(2) x,y,zS,设xy=4k+r (xy)z =(xy)mod 4)z=rz=(rz)mod 4=(4kz+rz)mod 4=(4k+r)z)mod 4 =(xyz)mod 4同理x(yz) =(xyz)mod 4所以，(xy)z = x(yz)，结合律成立。(3) xS, (x1)=(1x)=x,，所以1是单位元。(4) 0和2没有逆元所以，S，不构成群9.设Z为整数集合，在Z上定义二元运算。如下： " x,yZ,xoy= x+y-2 问Z关于o运算能否构成群？为什么？解：(1) x,yZ, xoy= x+y-2,o是Z上的代数运算。(2) x,y,zZ, (xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4同理(xoy)oz= xo(yoz)，结合律成立。(3)设是单位元，xZ, xo= ox=x,即x+-2= +x-2=x, e=2(4) xZ , 设x的逆元是y, xoy= yox=, 即x+y-2=y+x-2=2, 所以，所以Z，o构成群11.设G=，证明G关于矩阵乘法构成一个群解：(1) x,yG, 易知xyG,乘法是Z上的代数运算。(2) 矩阵乘法满足结合律(3)设是单位元，(4)每个矩阵的逆元都是自己。所以G关于矩阵乘法构成一个群14.设G为群，且存在aG,使得 G=akkZ证明：G是交换群。证明:x,yG，设，则所以，G是交换群17.设G为群，证明e为G中唯一的幂等元。证明:设也是幂等元，则，即，由消去律知18.设G为群，a,b,cG,证明 abc=bca=cab证明：先证设设则，即左边同乘，右边同乘得反过来，设则由元素阶的定义知，abc=bca，同理bca=cab19.证明：偶数阶群G必含2阶元。证明：设群G不含2阶元，当时，是一阶元，当时，至少是3阶元,因为群G时有限阶的，所以是有限阶的，设是k阶的,则也是k阶的，所以高于3阶的元成对出现的，G不含2阶元，G含唯一的1阶元,这与群G是偶数阶的矛盾。所以，偶数阶群G必含2阶元20.设G为非Abel群，证明G中存在非单位元a和b,ab,且ab=ba.证明：先证明G含至少含3阶元。若G只含1阶元,则G=e,G为Abel群矛盾；若G除了1阶元e外,其余元均为2阶元，则，与G为Abel群矛盾；所以，G含至少含一个3阶元，设为，则，且。令的证。21.设G是Mn(R)上的加法群，n2，判断下述子集是否构成子群。（1）全体对称矩阵 是子群（2）全体对角矩阵 是子群（3）全体行列式大于等于0的矩阵. 不是子群（4）全体上（下）三角矩阵。 是子群22.设G为群，a是G中给定元素，a的正规化子N（a）表示G中与a可交换的元素构成的集合，即 N（a）=xxGxa=ax证明N（a）构成G的子群。证明：ea=ae, ,所以由，得，即，所以所以N（a）构成G的子群31.设1是群G1到G2的同态，2是G2到G3的同态，证明12是G1到G3的同态。证明：有已知1是G1到G2的函数，2是G2到G3的函数，则1·2是G1到G3的函数。 所以:1·2是G1到G3的同态。33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。 证明：设G是循环群,令G=<a>,令,那么,G是阿贝尔群 克莱因四元群,是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。36.设是5元置换，且，(1)计算；(2)将表成不交的轮换之积。(3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。解：(1) (2) (3) 奇置换， 偶置换 奇置换第十四章部分课后习题参考答案5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有多少个顶点？在最少顶点的情况下，写出度数列、。解：由握手定理图G的度数之和为：3度与4度顶点各2个，这4个顶点的度数之和为14度。其余顶点的度数共有6度。其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2,所以，G至少有7个顶点, 出度数列为3,3,4,4,2,2,2,.7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求，,.解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2.,8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？解：由握手定理图G的度数之和为：设2度点个，则，该图有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) 22+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的补图的边数。解：21、无向图G如下图(1)求G的全部点割集与边割集，指出其中的割点和桥；(2) 求G的点连通度与边连通度。解：点割集: a,b,(d)边割集e2,e3,e3,e4,e1,e2,e1,e4e1,e3,e2,e4,e5=123、求G的点连通度、边连通度与最小度数。解：、 、28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？解： 得n=6,m=9.31、设图G和它的部图的边数分别为和，试确定G的阶数。解： 得45、有向图D如图 (1)求到长度为1，2，3，4的通路数；(2)求到长度为1，2，3，4的回路数；(3)求D中长度为4的通路数；(4)求D中长度小于或等于4的回路数；(5)写出D的可达矩阵。解：有向图D的邻接矩阵为：， (1)到长度为1，2，3，4的通路数为0,2,0,0；(2)到长度为1，2，3，4的回路数为0,0,4,0；(3)D中长度为4的通路数为32；(4)D中长度小于或等于4的回路数10；(4)出D的可达矩阵第十六章部分课后习题参考答案1、画出所有5阶和7阶非同构的无向树.2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点?解：设3度分支点个，则 ，解得T有11个顶点3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。解：设4度分支点个，则 ，解得度数列1111111133444、棵无向树T有 (i=2，3，k )个i度分支点，其余顶点都是树叶，问T应该有几片树叶?解：设树叶片，则 ，解得评论：2，3，4题都是用了两个结论,一是握手定理，二是5、n(n3)阶无向树T的最大度(T)至少为几？最多为几？解：2，n-16、若n(n3)阶无向树T的最大度(T) =2，问T中最长的路径长度为几？解：n-17、证明：n(n2) 阶无向树不是欧拉图.证明：无向树没有回路，因而不是欧拉图。8、证明：n(n2) 阶无向树不是哈密顿图.证明：无向树没有回路，因而不是哈密顿图。9、证明：任何无向树T都是二部图.证明：无向树没有回路，因而不存在技术长度的圈，是二部图。10、什么样的无向树T既是欧拉图，又是哈密顿图?解：一阶无向树14、设e为无向连通图G中的一条边， e在G的任何生成树中，问e应有什么性质?解：e是桥15、设e为无向连通图G中的一条边， e不在G的任何生成树中， 问e应有什么性质?解：e是环 23、已知n阶m条的无向图 G是k(k2)棵树组成的森林，证明：m = n-k.；证明：数学归纳法。k=1时, m = n-1，结论成立；设k=t-1(t-1)时，结论成立，当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,gT的所有树枝: e,a,b,fT的基本割集系统: S=e,g,h,a,c,d,g,h,b,c,d,g,h,f,d,g(b)有关问题仿照给出25、求图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%用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.并指出传输10n(n2)个按上述频率出现的字母，需要多少个二进制数字.解：a:01 b:10 c:000 d:110 e:001 f:1111 g:1110W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255传输10n(n2)个按上述频率出现的字母，需要255*10n-2个二进制数字.THANKS !致力为企业和个人提供合同协议，策划案计划书，学习课件等等打造全网一站式需求欢迎您的下载，资料仅供参考-可编辑修改-