电大 离散数学 形成性考核册 作业(三)答案.

《电大 离散数学 形成性考核册 作业(三)答案.》由会员分享，可在线阅读，更多相关《电大 离散数学 形成性考核册 作业(三)答案.（8页珍藏版）》请在装配图网上搜索。

1、8 离散数学形成性考核作业（三） 集合论与图论综合练习 本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第三次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。 一、单项选择题 1．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( B )． A．{a，{ a }}ÎA B．{ a }ÍA C．{2}ÎA D．ÎA 2．设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（ B

2、 ）． A．{2}B B．{2, {2}, 3, 4}ÌB C．{2}ÌB D．{2, {2}}ÌB 3．若集合A={a，b，{ 1，2 }}，B={ 1，2}，则（ B ）． A．B Ì A，且BÎA B．BÎ A，但BËA C．B Ì A，但BÏA D．BË A，且BÏA 4．设集合A = {1, a }，则P(A) = ( C )． A．{{1}, {a}}

3、 B．{,{1}, {a}} C．{,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 5．设集合A = {1，2，3，4，5，6 }上的二元关系R ={a , bêa , bA , 且a +b = 8}，则R具有的性质为（ B ）． A．自反的 B．对称的 　　C．对称和传递的　 D．反自反和传递的 6．设集合A = {1，2，3，4，5 }，B = {1，2，3}，R从A到B的二元关系，

4、 R ={a , bêaA，bB且} 则R具有的性质为（ ）． A．自反的 B．对称的 C．传递的 D．反自反的 [注意]：此题有误！自反性、反自反性、对称性、反对称性以及传递性指 某一个集合上的二元关系的性质。 7．设集合A={1 , 2 , 3 , 4}上的二元关系 R = {1 , 1，2 , 2，2 , 3，4 , 4}， S = {1 , 1，2 , 2，2 , 3，3 , 2，4 , 4}， 则S是R的（ C ）闭包． A．自反 B．传递 C．对称

5、 D．以上都不对 8．非空集合A上的二元关系R，满足( A )，则称R是等价关系． A．自反性，对称性和传递性 B．反自反性，对称性和传递性 　　C．反自反性，反对称性和传递性　 D．自反性，反对称性和传递性 9．设集合A={a, b}，则A上的二元关系R={，}是A上的( C )关系． A．是等价关系但不是偏序关系　　 B．是偏序关系但不是等价关系 2 4 1 3 5 　　C．既是等价关系又是偏序关系　　 D．不是等价关系也不是偏序关系 10．设集合A = {1 , 2

6、 , 3 , 4 , 5}上的偏序关系 的哈斯图如右图所示,若A的子集B = {3 , 4 , 5}， 则元素3为B的（ C ）． A．下界 B．最大下界 C．最小上界 D．以上答案都不对 11．设函数f：R R，f (a) = 2a + 1；g：R R，g(a) = a 2．则（ C ）有反函数． A．g·f B．f·g C．f D．g 12．设图G的邻接矩阵为 则G的边数为( D )． A．5 B．6

7、 C．3 D．4 13．下列数组中，能构成无向图的度数列的数组是( C ) ． A．(1, 1, 2, 3) B．(1, 2, 3, 4, 5) C．(2, 2, 2, 2) D．(1, 3, 3) 14．设图G＝，则下列结论成立的是 ( C )． A．deg(V)=2½E½ B．deg(V)=½E½ C． D． 解；C为握手定理。 15．有向完全图D＝， 则图D的边数是( D )．

8、 A．½E½(½E½－1)/2 B．½V½(½V½－1)/2 C．½E½(½E½－1) D．½V½(½V½－1) a g b d f c e 解：有向完全图是任意两点间都有一对方向相反的边的 图，其边数应为D，即 16．给定无向图G如右图所示，下面给出的结点 集子集中，不是点割集的为（ A ） A．{b, d} B．{d} C．{a, c} D．{g, e} 17．设G是连通平面图，有v个结点，e条

9、边，r个面，则r= ( A )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 18．无向图G存在欧拉通路，当且仅当( D )． A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点 C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点 19．设G是有n个结点，m条边的连通图，必须删去G的( A )条边，才能确定G的一棵生成树． A． B． C． D． 20．已知一棵无向树T中有8个结点，4度，3度，2度的分支点

10、各一个，T的树叶数为 B ． A．8 B．5 C．4 D． 3 二、填空题 1．设集合，则AB= {1，2，3}=A ，AB= B ，A – B= {3} ，P(A)-P(B )= {{3},{1,3},{2,3},{1,2,3} } ． 2．设A, B为任意集合，命题A-B=Æ的条件是 ． 3．设集合A有n个元素，那么A的幂集合P(A)的元素个数为 ． 4．设集

11、合A = {1，2，3，4，5，6 }，A上的二元关系且}，则R的集合表示式为 ． 5．设集合A = {1，2，3，4，5 }，B = {1，2，3}，R从A到B的二元关系， R ={a , bêaA，bB且2a + b4} 则R的集合表示式为 ． 6．设集合A={0,1,2},B={0,2,4},R是A到B的二元关系， 则R的关系矩阵MR＝ 　　　　　　　　　　　　　　　　　． 7．设集合A={1, 2, 3, 4 }，B={6, 8, 12}， A到B的二元关系 R＝ 那么R－1＝

12、 8．设集合A={a,b,c}，A上的二元关系 R={,}，S={,,} 则(R·S)－1=　　　　　　　　　　　． 9．设集合A=｛a,b,c｝，A上的二元关系R={, , , }，则二元关系R具有的性质是　反自反性　　　　　　　　． 10．设集合A = {1 , 2 , 3 , 4 }上的等价关系 R = {1 , 2，2 , 1，3 , 4，4 , 3}IA． 那么A中各元素的等价类为 [1]=[2]={1,2}, [3]=[4]={3,4}

13、 ． 11．设A，B为有限集，且|A|=m，|B|=n,那末A与B间存在双射，当且仅当 ． 12．设集合A={1, 2},B={a, b}，那么集合A到B的双射函数是 ． a　 b f 　 c e d 图G 13．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 15 ． 14．设给定图G(如由图所示)，则图G的点 割集是 {} ．

14、 15．设G=是具有n个结点的简单图，若在G中每一对结点度数之和大于等于 ，则在G中存在一条汉密尔顿路． 16．设无向图G＝是哈密顿图，则V的任意非空子集V1，都有 　 　 £½V1½． 17．设有向图D为欧拉图，则图D中每个结点的入度 　等于出度　． 6 8 7 9 2 2 1 2 3 18．设完全图K有n个结点(n≥2)，m条 边，当 时，K中存在欧拉回路． 19．图G（如右图所示）带权图中最小生 成树的

15、权是 12 20．连通无向图G有6个顶点9条边，从 G中删去 4 条边才有可能得到G的一棵生成树T． 三、判断说明题 1．设A、B、C为任意的三个集合，如果A∪B=A∪C，判断结论B=C 是否成立？并说明理由． 解：不一定成立。反例：A={1，2，3}，B={1}，C={3} 1 o o 8 4 6 9 5 2 7 7 2．如果R1和R2是A上的自反关系，判断结论：“R-11、R1∪R2、R1ÇR2是自反的” 是否成立？并说明理由． 3．设R，S是集合A上传递的关系，判断 R S是否具有传递性，并说明理由．

16、 4．若偏序集的哈斯图如右图所示，则 a c b e d f 集合A的最小元为1，最大元不存在． 解：结论正确。 5．若偏序集的哈斯图如右图所示，则 集合A的极大元为a，f；最大元不存在． 解：结论正确。 v1 v2 v3 v5 v4 d b a c e f g h n 图G 6．图G(如右图)能否一笔画出？说明理由． 若能画出，请写出一条通路或回路． 7．判断下图的树是否同构？说明理由． (a) (b) (c)

17、 8．给定两个图G1，G2（如下图所示），试判断它们是否为欧拉图、哈密顿图？并说明理由． a b c d e f g 图G2 图G1 v1 v2 v3 v6 v5 v4 9．判别图G(如下图所示)是不是平面图，并说明理由． 10．在有6个结点，12条边的简单平面连通图中，每个面有几条边围成？为什么？ 四、计算题 1．设，求：　 （1）(AÇB)È~C； （2）P(A)－P(C)； （3）AÅB． 2．设集合A

18、＝{a, b, c}，B={b, d, e}，求 （1）BÇA； （2）AÈB； （3）A－B； （4）BÅA． 3．设A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R是A上的整除关系，B={2, 4, 6}． （1）写出关系R的表示式； （2）画出关系R的哈斯图； （3）求出集合B的最大元、最小元． 解：（1） 解：（2）画出哈斯图（见课堂答疑） 解：（3）B={2，4，6}，B的最小元为2，B没有最大元。 a d b c 4．设集合A＝{a, b, c, d}上的二元关

19、系R的 关系图如右图所示． （1）写出R的表达式； （2）写出R的关系矩阵； （3）求出R2． 5．设A={0，1，2，3，4}，R={|xÎA，yÎA且x+y<0}，S={|xÎA，yÎA且x+y<=3}，试求R，S，R°S，R-1，S-1，r(R)，s(R)，t(R)，r(S)，s(S)，t(S)． 6．设图G=，其中V={a1, a2, a3, a4, a5}, E={，，，，} （1）试给出G的图形表示； （2）求G的邻接矩阵； （3）判

20、断图D是强连通图、单侧连通图还是弱连通图？ 7．设图G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }． （1）试给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数 （4）画出图G的补图的图形． 解：（1）画出G的图形 8．图G=，其中V={a, b, c, d, e, f }，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f),

21、(e, f) }，对应边的权值依次为5，2，1，2，6，1，9，3及8． （1）画出G的图形； （2）写出G的邻接矩阵； 5 10 6 3 4 7 8 9 2 1 （3）求出G权最小的生成树及其权值． 9．已知带权图G如右图所示．试 （1）求图G的最小生成树； （2）计算该生成树的权值． 10．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试 （1）画出相应的最优二叉树； （2）计算它们的权值． 五、证明题 1．试证明集合等式：AÈ (BÇC)=(AÈB) Ç (AÈC)． 2．证明对任意集合A，B，C，有． 3．设R是集合A上的对称关系和传递关系，试证明：若对任意aÎA，存在bÎA，使得ÎR，则R是等价关系． 4．若非空集合A上的二元关系R和S是偏序关系，试证明：也是A上的偏序关系． 5．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的． 6．设G是连通简单平面图，则它一定有一个度数不超过5的结点．（提示：用反证法） 7．设连通图G有k个奇数度的结点，证明在图G中至少要添加条边才能使其成为欧拉图． 8．证明任何非平凡树至少有2片树叶． 8