离散数学形成性综合练习_第1页
离散数学形成性综合练习_第2页
离散数学形成性综合练习_第3页
离散数学形成性综合练习_第4页
离散数学形成性综合练习_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

离散数学形成性考核作业(三)集合论与图论综合练习本课程形成性考核作业共4次,内容由中央电大确定、统一布置。本次形考作业是第三次作业,大家要认真及时地完成图论部分的形考作业,字迹工整,抄写题目,解答题有解答过程。一、单项选择题1.若集合A={2,a,{a},4},则下列表述正确的是(B). A.{a,{a}}AB.{a}A C.{2}A D.A2.设B={{2},3,4,2},那么下列命题中错误的是(B).A.{2}BB.{2,{2},3,4}BC.{2}BD.{2,{2}}B3.若集合A={a,b,{1,2}},B={1,2},则(B).A.BA,且BAB.BA,但BAC.BA,但BAD.BA,且BA4.设集合A={1,a},则P(A)=(C).A.{{1},{a}}B.{,{1},{a}}C.{,{1},{a},{1,a}}D.{{1},{a},{1,a}}5.设集合A={1,2,3,4,5,6}上的二元关系R={a,ba,bA,且a+b=8},则R具有的性质为(B). A.自反的B.对称的C.对称和传递的D.反自反和传递的6.设集合A={1,2,3,4,5},B={1,2,3},R从A到B的二元关系,R={a,baA,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.对称D.以上都不对8.非空集合A上的二元关系R,满足(A),则称R是等价关系. A.自反性,对称性和传递性B.反自反性,对称性和传递性C.反自反性,反对称性和传递性D.自反性,反对称性和传递性 9.设集合A={a,b},则A上的二元关系R={<a,a>,<b,b>}是A上的(C)关系. A.是等价关系但不是偏序关系B.是偏序关系但不是等价关系C.既是等价关系又是偏序关系D.不是等价关系也不是偏序关系10.设集合A={1,2,3,4,5}上的偏序关系的哈斯图如右图所示,若A的子集B={3,4,5},则元素3为B的(C).A.下界B.最大下界C.最小上界D.以上答案都不对11.设函数f:RR,f(a)=2a+1;g:RR,g(a)=a2.则(C)有反函数.A.gfB.fgC.fD.g 12.设图G的邻接矩阵为 则G的边数为(D). A.5B.6C.3D.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=<V,E>,则下列结论成立的是(C). A.deg(V)=2EB.deg(V)=EC.D.解;C为握手定理。 15.有向完全图D=<V,E>,则图D的边数是(D). A.E(E-1)/2B.V(V-1)/2C.E(E-1)D.V(V-1)解:有向完全图是任意两点间都有一对方向相反的边的图,其边数应为D,即16.给定无向图G如右图所示,下面给出的结点集子集中,不是点割集的为(A)A.{b,d}B.{d}C.{a,c}D.{g,e}17.设G是连通平面图,有v个结点,e条边,r个面,则r=(A).A.e-v+2B.v+e-2C.e-v-2D.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度的分支点各一个,T的树叶数为B. A.8B.5C.4D.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为任意集合,命题AB的条件是.3.设集合A有n个元素,那么A的幂集合P(A)的元素个数为.4.设集合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,baA,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=8.设集合A={a,b,c},A上的二元关系R={<a,b>,<c.a>},S={<a,a>,<a,b>,<c,c>}则(RS)-1=.9.设集合A={a,b,c},A上的二元关系R={<a,b>,<b,a>,<b,c>,<c,d>},则二元关系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}. 11.设A,B为有限集,且m,n,那末A与B间存在双射,当且仅当.12.设集合A={1,2},B={a,b},那么集合A到B的双射函数是.13.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是15.14.设给定图G(如由图所示),则图G的点割集是{}. 15.设G=<V,E>是具有n个结点的简单图,若在G中每一对结点度数之和大于等于,则在G中存在一条汉密尔顿路.16.设无向图G=<V,E>是哈密顿图,则V的任意非空子集V1,都有V1.17.设有向图D为欧拉图,则图D中每个结点的入度等于出度.18.设完全图K有n个结点(n≥2),m条边,当时,K中存在欧拉回路.19.图G(如右图所示)带权图中最小生成树的权是1220.连通无向图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}2.如果R1和R2是A上的自反关系,判断结论:“R-11、R1∪R2、R1R2是自反的”是否成立?并说明理由.3.设R,S是集合A上传递的关系,判断RS是否具有传递性,并说明理由.4.若偏序集<A,R>的哈斯图如右图所示,则集合A的最小元为1,最大元不存在.解:结论正确。5.若偏序集,R的哈斯图如右图所示,则集合A的极大元为a,f;最大元不存在.解:结论正确。6.图G(如右图)能否一笔画出?说明理由.若能画出,请写出一条通路或回路.7.判断下图的树是否同构?说明理由.8.给定两个图G1,G2(如下图所示),试判断它们是否为欧拉图、哈密顿图?并说明理由.9.判别图G(如下图所示)是不是平面图,并说明理由.10.在有6个结点,12条边的简单平面连通图中,每个面有几条边围成?为什么?四、计算题1.设,求:(1)(AB)~C;(2)P(A)-P(C);(3)AB.2.设集合A={a,b,c},B={b,d,e},求(1)BA;(2)AB;(3)A-B;(4)BA.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没有最大元。4.设集合A={a,b,c,d}上的二元关系R的关系图如右图所示.(1)写出R的表达式;(2)写出R的关系矩阵;(3)求出R2.5.设A={0,1,2,3,4},R={<x,y>|xA,yA且x+y<0},S={<x,y>|xA,yA且x+y<=3},试求R,S,RS,R-1,S-1,r(R),s(R),t(R),r(S),s(S),t(S).6.设图GV,E,其中Va1,a2,a3,a4,a5,Ea1,a2,a2,a4,a3,a1,a4,a5,a5,a2(1)试给出G的图形表示;(2)求G的邻接矩阵;(3)判断图D是强连通图、单侧连通图还是弱连通图?7.设图G=<V,E>,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,E>,其中V={a,b,c,d,e,f},E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e),(d,f),(e,f)},对应边的权值依次为5,2,1,2,6,1,9,3及8.(1)画出G的图形;(2)写出G的邻接矩阵;(3)求出G权最小的生成树及其权值.9.已知带权图G如右图所示.试(1)求图G的最小生成树;(2)计算该生成树的权值.10.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试(1)画出相应的最优二叉树;(2)计算它们的权值.五、证明题1.试证明集合等式:A

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论