离散数学秋综合练习题

由天下分享时间：2024/7/5 23:01:30 加入收藏我要投稿点赞

6. 下列各图是否为欧拉图，是否为哈密尔顿图？为什么?

a b v1 v2 v3

c d e v4 v5 v6

f g h i v7 v8 v9

(1）（2)

７. 下列图形中最少需添加几条边才能成为欧拉图．

a a

b e b ｄ

c d ｃ（1) （2)

8. 有向图D如下图所示

e1 v1 e4 e3 e2 e6 v4 e7 v2 e5 v3 (1) 求D的邻接矩阵A；

(2) 求D中长度为4的通路数和回路数,并找出D中从v1到v4长度为4的所有通路。 (3） D是哪类连通图?

9. 设有向图D??V,E?,V?{v1,v2,v3,v4,v5}，其邻接矩阵为

?0??0A??0??0?1?1010??0001?1010?

?0001?0100??(1) 画出有向图D；

(2) D中长度为4的通路有多少条？其中有多少条为回路？ (3) D是那类连通图?

10．设连通图G如下图所示，求它的一棵生成树．

b c

e f 答案不唯一。

五、构造下列推理的证明

1. 证明 ?(p??q),?q?r,?r??p

２. 证明 p?q,p??r,s?t,?s?r,?t?q

３. 证明 p?(q?r),?s?p,q,s?r

4. 证明 (?x)(C(x)?(W(x)?R(x)),(?x)(C(x)?Q(x))?(?x)(Q(x)?R(x))

５．构造下列推理的证明:

每个学术委员会的成员都是专家并且是大学生,有些成员是青年人,所以有些成员是青年专家。

６．“有些病人相信所有的医生，病人都不相信骗子,所以医生都不是骗子。” 在一阶逻辑中证明以上推理是正确的。

六、证明题

1. 设?1,?2为集合A上的等价关系, 试证?1??2也是集合A上的等价关系。

２. 设u,w为无向连通图G中任意两个顶点，证明:若d(u,w)?2,则存在顶点v,使得

d(u,v)?d(v,w)?d(u,w)

３. 证明下面四个矩阵关于矩阵乘法运算构成群。

?10???01??， ?? ????10??， ??0?1??10???0?1??, ????10???01?? ??

4. 设 ?G,?? 是一个群，试证 G 是交换群当且仅当对任意的a,b?G ,有 a?b?(a?b) .

5. 设a是群?G,??的元素，记H?{y|y?G且y?a?a?y}，证明?H,??是?G,??的子群．

６. 设?G,??是一个群,取定u?G,定义 a*b?a?u证明?G,*?是一个群。

?1222?b， ?a,b?G

离散数学综合练习题答案

一、判断下列命题是否正确

(1）错误； (２)错误; （3)正确; (４）错误; (５）错误； (6)正确; (7)错误； (8）正确; （9)正确; (10)错误; (11)正确；（12)正确；（13)正确；（14)正确;(15)正确；（16)正确；（17）正确;(1８)正确;(19）正确;(20）正确；（2１）正确；(22）错误；(23）正确;（24）正确;(25)正确; (２6）正确;（２7）正确；(28)正确；（2９)正确；（30）错误; （31)正确；(3２)错误;(3３)错误;（34）错误；(35）错误； (36）正确;（37)正确;（38)正确；（3９)错误；(4０)错误.

二、填空题

n~??~ （1)2; (2）{?,{?},{{?}},{?,{?}}}； (3）３；（4)40; (5)?21(６） ?????; (7)a称c为外祖父; (8)5,9;

(9)[赵]＝｛赵茵,赵萍}，[钱]= {钱小滨,钱浩，钱钰},[孙］={ 孙丽春}， [李]= {李靖华,李秀娟，李惠芝,李莉}． (１0)

??{??,??,??,{a}?,??,{b}?,??,A?,?{a},{a}?,?{a},A?,?{b},{b}?,?{b},A?,?A,A?}(11） ?,S； (12) 1和2;

(13）?{0},?6?，?{0,3},?6?,?{0,2,4},?6?，?I6,?6?；

(14) ?x； (15) –2；（１６) 1，1; (17） a?x?b，y?a?b； (１8) b?c；（１9) e； (2０) 0； (2１) ５； (2２） m-n+1; (２3) １; （24) 0； (２5) 1; (2６) n(n?1)2; （27) 2m； (2８) 11; （29) k?1; （30）偶数; (31） p?q; (３2) ?p?q； (33） ?p??q；（３4) 0； (35） 0； (36） 2; (3７)F(a1)?F(a2)???F(an)； (38) (?x)(N(x)?(F(x)?G(x))；（39) F(a)?G(a)； (40) (?x)(G(x)?F(x))?(?x)(F(x)??G(x)).

三、选择题

(１）Ａ； (2) Ｃ; (3) Ｃ; （4） B; (5）Ｂ；（6) A；（７） B; (8) D; (9） B； (１0）B; （1１)B; (12）D；（13)B；（1４）D；（15)D；（1６）C； (17）Ｃ; （18)D；（19)C；（20）A; （21）A; （22）B； (２3)B； (24)C; (２5)B；（２６)B; （27）B； (２8)A; (29)B；（30）Ｃ； (31)B; （３2）C; (33)B; （3４)A; (35)Ａ;

(３６）Ｄ；（３7）D; （38)B；（3９)B; （4０)B.

四、解答题

1. 解 (1)?的关系矩阵为

2n?1??1 M???0??0?100??100? ?011?011??（２）从?的关系矩阵可知:?是自反的和对称的。

又由于

?1??1 M??M???0??0?100??1??100??1?011??0???011???0100??1??100??1?011??0???011???0100??100??M?

011??011??所以?是传递的。

因为?是自反的、对称的和传递的,所以?是A上的等价关系。（3) [a]?[b]?{a,b},[c]?[d]?{c,d}

2. 解:

8 12

4 6?

? ２ 3