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

《离散数学答案屈婉玲版第二版高等教育出版社课后答案.pdf》由会员分享，可在线阅读，更多相关《离散数学答案屈婉玲版第二版高等教育出版社课后答案.pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案 第一章部分课后习题参考答案 16 设 p、q 的真值为 0；r、s 的真值为 1,求下列各命题公式的真值;1pqr 001 0 2prqs 0111 010.3pqrpqr 111 0000 4rspq 0110 001 17判断下面一段论述是否为真：“是无理数;并且,如果 3 是无理数,则2也是无理数;另外 6 能被 2 整除,6 才能被 4 整除;”答：p:是无理数 1 q:3 是无理数 0 r:2是无理数 1 s:6 能被 2 整除 1 t:6 能被 4 整除 0 命题符号化为：pqrts 的真值为 1,所以这一段的论述为真;19用

2、真值表判断下列公式的类型：4pq qp 5pr pq 6pq qr pr 答：4 p q pq q p qp pqqp 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 2ppqpr 3pqpr 答：2ppqprppqprppqr1 所以公式类型为永真式 3 P q r pq pr pqpr 0 0 0 0 0 1 0 0

3、 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式：2pqprpqr 4pqpqpq pq 证明 2pqpr pqpr pqr pqr 4pqpqppq qpq pppqqp qq 1pqpq1 pqpq 5.求下列公式的主析取范式与主合取范式,并求成真赋值 1pqqp 2pqqr 3pqrpqr 解：1 主析取范式 pqqp p p pp ppqppqpq pqpqpq 0,2,3 主合取范式：pqqp p p pp pqpp

4、1pq pq M1 1 2 主合取范式为：p r p r p r0 所以该式为矛盾式.主合取范式为0,1,2,3,4,5,6,7 矛盾式的主析取范式为 0 3 主合取范式为：pqrpqr pqrpqr pqrpqr ppqrqrpqr 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 前提引入 p3 拒取

5、式 证明 4：tr 前提引入 t 化简律 qs 前提引入 st 前提引入 qt 等价三段论 qttq 置换 qt 化简 q 假言推理 qp 前提引入 p 假言推理 11pq 合取 15 在自然推理系统 P 中用附加前提法证明下面各推理：(1)前提：pqr,sp,q 结论：sr 证明 s 附加前提引入 sp 前提引入 p 假言推理 pqr 前提引入 qr 假言推理 q 前提引入 r 假言推理 16 在自然推理系统 P 中用归谬法证明下面各推理：1 前提：pq,rq,rs 结论：p 证明：p 结论的否定引入 pq 前提引入 q 假言推理 rq 前提引入 r 化简律 rs 前提引入 r 化简律 rr

6、 合取 由于最后一步 rr 是矛盾式,所以推理正确.第四章部分课后习题参考答案 3.在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为 a,b 条件时命题的真值:1 对于任意 x,均有x22=x+2x2.2 存在 x,使得 x+5=9.其中 a 个体域为自然数集合.b 个体域为实数集合.解：Fx:x22=x+2x2.Gx:x+5=9.1 在两个个体域中都解释为)(xxF,在 a 中为假命题,在 b 中为真命题;2 在两个个体域中都解释为)(xxG,在 ab 中均为真命题;4.在一阶逻辑中将下列命题符号化:1 没有不能表示成分数的有理数.2 在北京卖菜的人不全是外地人.解:1Fx:x 能

7、表示成分数 Hx:x 是有理数 命题符号化为:)()(xHxFx 2Fx:x 是北京卖菜的人 Hx:x 是外地人 命题符号化为:)()(xHxFx 5.在一阶逻辑将下列命题符号化:1 火车都比轮船快.3 不存在比所有火车都快的汽车.解:1Fx:x 是火车;Gx:x 是轮船;Hx,y:x 比 y 快 命题符号化为:),()()(yxHyGxFyx 2 1Fx:x 是火车;Gx:x 是汽车;Hx,y:x 比 y 快 命题符号化为:),()()(yxHxFxyGy 9.给定解释 I 如下:a 个体域 D 为实数集合 R.b D 中特定元素a=0.c 特定函数fx,y=xy,x,yD.d 特定谓词Fx

8、,y:x=y,Gx,y:xy,x,yD.说明下列公式在 I 下的含义,并指出各公式的真值:答:1 对于任意两个实数 x,y,如果 xy,那么 xy.真值 1.2 对于任意两个实数 x,y,如果 x-y=0,那么 xy.真值 0.10.给定解释 I 如下：a 个体域 D=NN 为自然数集合.b D 中特定元素a=2.c D 上函数f(x,y)=x+y,g x,y=xy.d D 上谓词Fx,y:x=y.说明下列各式在 I 下的含义,并讨论其真值.(1)xFgx,a,x(2)xyFfx,a,yFfy,a,x 答:1 对于任意自然数 x,都有 2x=x,真值 0.2 对于任意两个自然数 x,y,使得如

9、果 x+2=y,那么 y+2=x.真值 0.11.判断下列各式的类型:1 F(x,y)(G(x,y)F(x,y).3 xyF(x,y)xyFx,y.解:1 因为 1)()(pqppqp 为永真式；所以 F(x,y)(G(x,y)F(x,y).为永真式；3 取解释 I 个体域为全体实数 Fx,y：x+y=5 所以,前件为任意实数 x 存在实数 y 使 x+y=5,前件真；后件为存在实数 x 对任意实数 y 都有 x+y=5,后件假,此时为假命题 再取解释 I 个体域为自然数 N,Fx,y：:x+y=5 所以,前件为任意自然数 x 存在自然数 y 使 x+y=5,前件假;此时为假命题;此公式为非永

10、真式的可满足式;13.给定下列各公式一个成真的解释,一个成假的解释;1 xFx G(x)2 xFxGxHx 解:1 个体域:本班同学 Fx：x 会吃饭,Gx：x 会睡觉.成真解释 Fx：x 是泰安人,Gx：x 是济南人.2 成假解释 2 个体域:泰山学院的学生 Fx：x 出生在山东,Gx:x 出生在北京,Hx:x 出生在江苏,成假解释.Fx：x 会吃饭,Gx：x 会睡觉,Hx：x 会呼吸.成真解释.第五章部分课后习题参考答案 5.给定解释如下:a 个体域 D=3,4;b)(xff为3)4(,4)3(ff c1)3,4()4,3(,0)4,4()3,3(),(FFFFyxF为.试求下列公式在下的

11、真值.1),(yxyFx 3)(),(),(yfxfFyxFyx 解:1)4,()3,(),(xFxFxyxyFx 2)(),(),(yfxfFyxFyx 12.求下列各式的前束范式;1),()(yxyGxxF 5),()(),(2121211xxGxxHxxFx 本题课本上有错误 解:1),()(yxyGxxF),()(ytyGxxF),()(ytGxFyx 5),()(),(2121211xxGxxHxxFx 15.在自然数推理系统 F 中,构造下面推理的证明:(1)前提:)()()()(yRyGyFyxxF,)(xxF 结论:xRx(2)前提:xFxGaRx,xFx 结论:xFxRx 证

12、明 1)(xxF 前提引入 Fc EI )()()()(yRyGyFyxxF 前提引入 )()()(yRyGyFy 假言推理 FcGcRc UI FcGc 附加 Rc 假言推理 xRx EG 2 xFx 前提引入 Fc EI xFxGaRx 前提引入 FcGaRc UI GaRc 假言推理 Rc 化简 FcRc 合取引入 xFxRx EG 第六章部分课后习题参考答案 5.确定下列命题是否为真：1 真 2 假 3 真 4 真 5a,ba,b,c,a,b,c 真 6a,ba,b,c,a,b 真 7a,ba,b,a,b 真 8a,ba,b,a,b 假 6设 a,b,c 各不相同,判断下述等式中哪个等

13、式为真:1 a,b,c,=a,b,c 假 2a,b,a=a,b 真 3 a,b=a,b 假 4,a,b=,a,b 假 8求下列集合的幂集：1a,b,c PA=,a,b,c,a,b,a,c,b,c,a,b,c 21,2,3 PA=,1,2,3,1,2,3 3 PA=,4,PA=,1,2,3,1,2,3 14化简下列集合表达式：1ABB-AB 2ABC-BCA 解:1ABB-AB=ABB AB=ABABB=B=2ABC-BCA=ABCBCA=ABCBC BCA=ABCA=ABCA=A 18 某班有 25 个学生,其中 14 人会打篮球,12 人会打排球,6 人会打篮球和排球,5 人会打篮球和网球,

14、还有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,计算下列表达式：1A 2A 3A 4A 解:1A=1,22,31,3=1,2,3,2A=1,22,31,3=3A=123=4A=27、设 A,B,C 是任意集合,证明 1A-B-C=A-BC 2A-B-C=A-C-B-C 证明 1 A-B-

15、C=AB C=A BC=ABC=A-BC 2 A-C-B-C=AC B C=AC BC=ACB ACC=ACB =ABC=A-BC 由 1 得证;第七章部分课后习题参考答案 7.列出集合 A=2,3,4上的恒等关系 I A,全域关系 EA,小于或等于关系 LA,整除关系 DA.解：IA=,EA=,LA=,DA=13.设 A=,B=,求 AB,AB,domA,domB,domAB,ranA,ranB,ranAB,fldA-B.解：AB=,AB=domA=1,2,3 domB=1,2,4 domAB=1,2,3,4 ranA=2,3,4 ranB=2,3,4 ranAB=4 A-B=,fldA-B

16、=1,2,3 14.设 R=,求 RR,R-1,R0,1,R1,2 解：RR=,R-1,=,R0,1=,R1,2=ranR|1,2=2,3 16设 A=a,b,c,d,1R,2R为 A 上的关系,其中 1R=,a aa bb d 求23122112,RR RR RR;解:R1R2=,R2R1=R12=R1R1=,R22=R2R2=,R23=R2R22=,36设 A=1,2,3,4,在 AA 上定义二元关系 R,AA,u,v R u+y=x+v.(1)证明 R 是 AA 上的等价关系.2 确定由 R 引起的对 AA 的划分.1 证明：R u+y=x-y Ru-v=x-y AA u-v=u-v R

17、 R 是自反的 任意的,AA 如果R,那么 u-v=x-y x-y=u-v R R 是对称的 任意的,AA 若R,R 则 u-v=x-y,x-y=a-b u-v=a-b R R 是传递的 R 是 AA 上的等价关系 2=,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 R R 是自反的 任意的,AA 设R,则 a+b=c+d c+d=a+b R R 是对称的 任意的,AA 若R,R 则 a+b=c+d,c+d=x+y a+b=x+y R R

18、是传递的 R 是 AA 上的等价关系 2=,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 b 解:aA=a,b,c,d,e,f,g R=,AI b A=a,b,c,d,e,f,g R=,AI 46.分别画出下列各偏序集的哈斯图,并找出A的极大元极小元最大元和最小元.1A=a,b,c,d,e R=,IA.2A=a,b,c,d,e,R=IA.解:1 2 项目 1 2 极大元:e a,b,d,e 极小元:a a,b,

19、c,e 最大元:e 无 最小元:a 无 第八章部分课后习题参考答案 1设 f:NN,且 f x=12xxx，若 为奇数若 为偶数，求 f 0,f 0,f 1,f 1,f 0,2,4,6,f 4,6,8,f-13,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,fx=x2+2 不是满射,不是单射 2 f:NN,fx=xmod 3,x 除以 3 的余数 不是满射,不是单射 3 f:NN,fx=10 xx，若 为奇数，若 为偶数

20、不是满射,不是单射 4 f:N0,1,fx=01xx，若 为奇数，若 为偶数 是满射,不是单射 5 f:N-0R,fx=lgx 不是满射,是单射 6 f:RR,fx=x2-2x-15 不是满射,不是单射 5.设 X=a,b,c,d,Y=1,2,3,f=,判断以下命题的真假:1f 是从 X 到 Y 的二元关系,但不是从 X 到 Y 的函数;对 2f 是从 X 到 Y 的函数,但不是满射,也不是单射的;错 3f 是从 X 到 Y 的满射,但不是单射;错 4f 是从 X 到 Y 的双射.错 第十章部分课后习题参考答案 4判断下列集合对所给的二元运算是否封闭：（1）整数集合 Z 和普通的减法运算;封闭

21、,不满足交换律和结合律,无零元和单位元（2）非零整数集合Z和普通的除法运算;不封闭（3）全体nn实矩阵集合MnR 和矩阵加法及乘法运算,其中 n2;封闭 均满足交换律,结合律,乘法对加法满足分配律；加法单位元是零矩阵,无零元；乘法单位元是单位矩阵,零元是零矩阵；4 全体nn实可逆矩阵集合关于矩阵加法及乘法运算,其中 n2;不封闭 5 正实数集合R+和 运算,其中 运算定义为：a，b R+，a b=ab a b 不封闭 因为 R1111111 6n Z+,nZ=nz|z Z.nZ关于普通的加法和乘法运算;封闭,均满足交换律,结合律,乘法对加法满足分配律 加法单位元是 0,无零元；乘法无单位元1n

22、,零元是 0；1n单位元是 1 7A=,21naaa n 2.运算定义如下：a，b A，a b=b 封闭 不满足交换律,满足结合律,8S=2x 1|x Z+关于普通的加法和乘法运算;封闭 均满足交换律,结合律,乘法对加法满足分配律 9S=0,1,S 是关于普通的加法和乘法运算;加法不封闭,乘法封闭；乘法满足交换律,结合律 10S=x|x=2n,n Z+,S 关于普通的加法和乘法运算;加法不封闭,乘法封闭,乘法满足交换律,结合律 5对于上题中封闭的二元运算判断是否适合交换律,结合律,分配律;见上题 7设 为Z上的二元运算Zyx,X Y=min x,y,即 x 和 y 之中较小的数.(1)求 4

23、6,7 3;4,3 2 在Z上是否适合交换律,结合律,和幂等律 满足交换律,结合律,和幂等律 3 求运算的单位元,零元及Z中所有可逆元素的逆元;单位元无,零元 1,所有元素无逆元 8QQS Q为有理数集,为 S 上的二元运算,S 有 =1 运算在 S 上是否可交换,可结合是否为幂等的 不可交换：=可结合：=不是幂等的 2 运算是否有单位元,零元 如果有请指出,并求 S 中所有可逆元素的逆元;设是单位元,S,=则=,解的=,即为单位;设是零元,S,=则=,无解;即无零元;S,设是它的逆元=a=1/x,b=-y/x 所以当 x0 时,xyxyx,1,1 10令 S=a,b,S 上有四个运算：,，和

24、分别有表确定;a b c d 1 这 4 个运算中哪些运算满足交换律,结合律,幂等律 a 交换律,结合律,幂等律都满足,零元为 a,没有单位元；b 满足交换律和结合律,不满足幂等律,单位元为 a,没有零元 c 满足交换律,不满足幂等律,不满足结合律 没有单位元,没有零元 d 不满足交换律,满足结合律和幂等律 没有单位元,没有零元(2)求每个运算的单位元,零元以及每一个可逆元素的逆元;见上 16设 V=N,+,其中+,分别代表普通加法与乘法,对下面给定的每个集合确定它是否构成 V 的子代数,为什么 1S1=2n|n Z 是 2S2=2n+1|n Z 不是 加法不封闭 3S3=-1,0,1 不是,

25、加法不封闭 第十一章部分课后习题参考答案 8.设 S=0,1,2,3,为模 4 乘法,即 x,yS,xy=xymod 4 问S,是否构成群为什么 解：1 x,yS,xy=xymod 4S,是 S 上的代数运算;2 x,y,zS,设 xy=4k+r 30 r xyz=xymod 4z=rz=rzmod 4=4kz+rzmod 4=4k+rzmod 4=xyzmod 4 同理 xyz=xyzmod 4 所以,xyz=xyz,结合律成立;3 xS,x1=1x=x,所以 1 是单位元;4,33,1111 0 和 2 没有逆元 所以,S,不构成群 9.设 Z 为整数集合,在 Z 上定义二元运算;如下：x

26、,yZ,xoy=x+y-2 问 Z 关于 o 运算能否构成群为什么 解：1 x,yZ,xoy=x+y-2Z,o 是 Z 上的代数运算;2 x,y,zZ,xoy oz=x+y-2oz=x+y-2+z-2=x+y+z-4 同理 xoyoz=xoyoz,结合律成立;3 设e是单位元,xZ,xoe=eox=x,即 x+e-2=e+x-2=x,e=2 4 xZ,设 x 的逆元是 y,xoy=yox=e,即 x+y-2=y+x-2=2,所以,xyx41 所以Z,o构成群 11.设 G=1001,1001,1001,1001,证明 G 关于矩阵乘法构成一个群 解：1 x,yG,易知 xyG,乘法是 Z 上的

27、代数运算;2 矩阵乘法满足结合律 3 设1001是单位元,4 每个矩阵的逆元都是自己;所以 G 关于矩阵乘法构成一个群 14.设 G 为群,且存在 aG,使得 G=akkZ 证明：G 是交换群;证明:x,yG,设lkayax,则 所以,G 是交换群 17.设 G 为群,证明 e 为 G 中唯一的幂等元;证明:设Ge 0也是幂等元,则020ee,即eee020,由消去律知ee 0 18.设 G 为群,a,b,cG,证明 abc=bca=cab 证明：先证设ebcaeabckk)()(设,)(eabck则eabcabcabcabc)()()(,即 eabcabcabcabcaa1)()()(左边同

28、乘1a,右边同乘a得 反过来,设,)(eback则.)(eabck 由元素阶的定义知,abc=bca,同理bca=cab 19.证明：偶数阶群G 必含 2 阶元;证明：设群 G 不含 2 阶元,Ga,当ea 时,a是一阶元,当ea 时,a至少是 3 阶元,因为群 G 时有限阶的,所以a是有限阶的,设a是 k 阶的,则1a也是 k 阶的,所以高于 3 阶的元成对出现的,G不含 2阶元,G 含唯一的 1阶元e,这与群 G是偶数阶的矛盾;所以,偶数阶群 G 必含 2 阶元 20.设 G 为非 Abel 群,证明 G 中存在非单位元 a 和 b,ab,且 ab=ba.证明：先证明 G 含至少含 3 阶

29、元;若 G 只含 1 阶元,则 G=e,G 为 Abel 群矛盾；若 G 除了 1 阶元 e 外,其余元a均为 2 阶元,则ea 2,aa1 bababaabababbbaaGba111111)(,)(,所以,与 G 为 Abel 群矛盾；所以,G 含至少含一个 3 阶元,设为a,则a2a,且22aaaa;令2ab 的证;21.设 G 是 MnR 上的加法群,n2,判断下述子集是否构成子群;1 全体对称矩阵 是子群 2 全体对角矩阵 是子群 3 全体行列式大于等于0 的矩阵.不是子群 4 全体上下三角矩阵;是子群 22.设G为群,a是G中给定元素,a的正规化子Na表示G中与a可交换的元素构成的

30、集合,即 Na=xxGxa=ax 证明 Na 构成 G 的子群;证明：ea=ae,)(aNe axyyaxayxyxayaxxya)()()()()()(,所以)(aNxy 由xaax,得111111,eaxaexxaxxaxxx,即11 axax,所以)(1aNx 所以 Na 构成 G 的子群 31.设1是群 G1到 G2的同态,2是 G2到 G3的同态,证明12是 G1到 G3的同态;证明：有已知1是 G1到 G2的函数,2是 G2到 G3的函数,则12是 G1到 G3的函数;所以:12是 G1到 G3的同态;33.证明循环群一定是阿贝尔群,说明阿贝尔群是否一定为循环群,并证明你的结论;证

31、明：设 G 是循环群,令 G=,Gyx,令lkayax,那么 yxaaaaaaxyklkllklk,G 是阿贝尔群 克莱因四元群,cbaeG 是交换群,但不是循环群,因为 e 是一阶元,a,b,c 是二阶元;36.设,是 5 元置换,且 3541254321,2154354321 1 计算111,；2 将11,表成不交的轮换之积;3 将 2 中的置换表示成对换之积,并说明哪些为奇置换,哪些为偶置换;解：1 1235454321 5213454321 32154543211 2)1425()14253(1 )25)(143(1 3)15)(12)(14(奇置换,)13)(15)(12)(14(1

32、 偶置换 )25)(13)(14(1 奇置换 第十四章部分课后习题参考答案 5、设无向图 G 有 10 条边,3 度与 4 度顶点各 2 个,其余顶点的度数均小于3,问 G 至少有多少个顶点在最少顶点的情况下,写出度数列、)()(GG、;解：由握手定理图 G 的度数之和为：20102 3 度与 4 度顶点各 2 个,这 4 个顶点的度数之和为 14 度;其余顶点的度数共有 6 度;其余顶点的度数均小于 3,欲使 G 的顶点最少,其余顶点的度数应都取 2,所以,G 至少有 7 个顶点,出度数列为 3,3,4,4,2,2,2,2)(,4)(GG.7、设有向图 D 的度数列为 2,3,2,3,出度列

33、为 1,2,1,1,求 D 的入度列,并求)(),(DD,)(),(DD,)(),(DD.解：D 的度数列为 2,3,2,3,出度列为 1,2,1,1,D 的入度列为 1,1,1,2.2)(,3)(DD,1)(,2)(DD,1)(,2)(DD 8、设无向图中有 6 条边,3 度与 5 度顶点各 1 个,其余顶点都是 2 度点,问该图有多少个顶点 解：由握手定理图 G 的度数之和为：1262 设 2 度点x个,则1221513x,2x,该图有 4 个顶点.14、下面给出的两个正整数数列中哪个是可图化的对可图化的数列,试给出 3 种非同构的无向图,其中至少有两个时简单图;1 2,2,3,3,4,4

34、,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 的补图G的边数m

35、;解：mnnm2)1(21、无向图 G 如下图 1 求 G 的全部点割集与边割集,指出其中的割点和桥；2 求 G 的点连通度)(Gk与边连通度)(G;解：点割集:a,b,d 边割集e2,e3,e3,e4,e1,e2,e1,e4e1,e3,e2,e4,e5)(Gk=)(G=1 23、求 G 的点连通度)(Gk、边连通度)(G与最小度数)(G;解：2)(Gk、3)(G、4)(G 28、设 n 阶无向简单图为 3-正则图,且边数 m 与 n 满足 2n-3=m 问这样的无向图有几种非同构的情况 解：mnmn3223 得 n=6,m=9.31、设图 G 和它的部图G的边数分别为m和m,试确定 G 的阶

36、数;解：2)1(nnmm 得2)(811mmn 45、有向图 D 如图 1 求2v到5v长度为 1,2,3,4的通路数；2 求5v到5v长度为 1,2,3,4的回路数；3 求 D 中长度为 4 的通路数；4 求 D 中长度小于或等于4 的回路数；5 写出 D 的可达矩阵;解：有向图 D 的邻接矩阵为：0101000101100000010110000A,00202200000101020000010102A40000020200020202020002023A 12v到5v长度为 1,2,3,4 的通路数为 0,2,0,0；25v到5v长度为 1,2,3,4 的回路数为 0,0,4,0；3D

37、中长度为 4 的通路数为 32；4D 中长度小于或等于 4 的回路数 10；4 出 D 的可达矩阵1111111111111111111111111P 第十六章部分课后习题参考答案 1、画出所有 5 阶和 7 阶非同构的无向树.2、一棵无向树 T 有 5 片树叶,3 个 2 度分支点,其余的分支点都是 3 度顶点,问 T 有几个顶点 解：设 3 度分支点x个,则 )135(232315xx,解得3x T 有 11 个顶点 3、无向树 T 有 8 个树叶,2 个 3 度分支点,其余的分支点都是 4 度顶点,问 T 有几个 4 度分支点根据T 的度数列,请至少画出 4 棵非同构的无向树;解：设 4

38、 度分支点x个,则 )128(243218xx,解得2x 4、棵无向树 T 有in i=2,3,k 个 i 度分支点,其余顶点都是树叶,问 T 应该有几片树叶 解：设树叶x片,则 )1(21xnxinii,解得2)2(inix 评论：2,3,4 题都是用了两个结论,一是握手定理,二是1 nm 5、nn3 阶无向树 T 的最大度(T)至少为几最多为几 解：2,n-1 6、若 nn3 阶无向树 T 的最大度(T)=2,问 T 中最长的路径长度为几 解：n-1 7、证明：nn2 阶无向树不是欧拉图.证明：无向树没有回路,因而不是欧拉图;8、证明：nn2 阶无向树不是哈密顿图.证明：无向树没有回路,因

39、而不是哈密顿图;9、证明：任何无向树 T 都是二部图.证明：无向树没有回路,因而不存在技术长度的圈,是二部图;10、什么样的无向树 T 既是欧拉图,又是哈密顿图 解：一阶无向树 14、设 e 为无向连通图 G 中的一条边,e 在 G 的任何生成树中,问 e 应有什么性质 解：e 是桥 15、设 e 为无向连通图 G 中的一条边,e 不在 G 的任何生成树中,问 e 应有什么性质 解：e 是环 23、已知 n 阶 m 条的无向图 G 是 kk2 棵树组成的森林,证明：m=n-k.；证明：数学归纳法;k=1 时,m=n-1,结论成立；设 k=t-1t-11时,结论成立,当 k=t 时,无向图 G

40、是 t 棵树组成的森林,任取两棵树,每棵树任取一个顶点,这两个顶点连线;则所得新图有 t-1 棵树,所以 m=n-k-1.所以原图中 m=n-k 得证;24、在图所示 2 图中,实边所示的生成子图 T 是该图的生成树.1 指出 T 的弦,及每条弦对应的基本回路和对应 T 的基本回路系统.2 指出 T 的所有树枝,及每条树枝对应的基本割集和对应 T 的基本割集系统.a b 图 解：aT 的弦：c,d,g,h T 的基本回路系统:S=a,c,b,a,b,f,d,e,a,b,h,e,a,b,f,g T 的所有树枝:e,a,b,f T 的基本割集系统:S=e,g,h,a,c,d,g,h,b,c,d,g

41、,h,f,d,g b 有关问题仿照给出 25、求图所示带权图中的最小生成树.a b 图 解：注：答案不唯一;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算法求传输它们的前缀码.要求画出最优树,指出每个字母对应的编码.并指出传输10nn2 个按上述频率出现的字母,需要多少个二进制数字.解：a:01 b:10 c:000 d:110 e:001 f:1111 g:1110 WT=54+54+103+103+153+202+352=255 传输 10nn2 个按上述频率出现的字母,需要 25510n-2个二进制数字.