《电大 离散数学 形成性考核册 作业(三)答案679.docx》由会员分享，可在线阅读，更多相关《电大 离散数学 形成性考核册 作业(三)答案679.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、10离散数学学形成性性考核作作业（三三）集合论与与图论综综合练习习本课程形形成性考考核作业业共4次，内内容由中中央电大大确定、统统一布置置。本次次形考作作业是第第三次作作业，大大家要认认真及时时地完成成图论部部分的形形考作业业，字迹迹工整，抄抄写题目目，解答答题有解解答过程程。一、单项项选择题题1若集集合A2，a， a ，4，则则下列表表述正确确的是( B )Aa， a A B a A C2A DA 2设设B = 2, 3, 4, 2，那么么下列命命题中错错误的是是（B）A22B B2, 22, 3, 4BB C2B D2, 22BB3若集集合A=a，b，1，2 ，B=1，2，则则（B） AB
2、 A，且且BA BBB A，但但BA CB AA，但BA DDB A，且且BA 4设设集合AA = 1, a ，则则P(A) = ( C ) A11, a BB,11, a C,11, a, 1, a D11, a, 1, a 5设设集合AA = 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传传递
3、的 D反自反反的注意：此题题有误！自反性性、反自自反性、对对称性、反反对称性性以及传传递性指指某一个集集合上的的二元关关系的性性质。 7设设集合AA=11 , 2 , 3 , 44上的的二元关关系R = 1 , 11，2 , 2，2 , 3，4 , 4，S = 1 , 11，2 , 2，2 , 3，3 , 2，4 , 4，则S是RR的（C）闭包包 A自自反 B传递 C对对称 DD以上上都不对对8非空空集合AA上的二二元关系系R，满足足( A )，则则称R是等价价关系A自自反性，对对称性和和传递性性 B反反自反性性，对称称性和传传递性C反自自反性，反反对称性性和传递递性 DD自反反性，反反对称性
4、性和传递递性9设设集合AA=a, b，则A上的二二元关系系R=，是A上的( C )关系系A是是等价关关系但不不是偏序序关系 BB是偏偏序关系系但不是是等价关关系24135C既是是等价关关系又是是偏序关关系 D不是等等价关系系也不是是偏序关关系 10设集合合A = 1 , 22 , 3 , 4 , 55上的的偏序关关系的哈斯图图如右图图所示,若A的子集集B = 3 , 44 , 5，则元素33为B的（C） A下下界 B最大下下界 C最小上上界 D以上答答案都不不对 11设函数数f：R R，f (a) = 2aa + 1；g：R R，g(a) = a 2则（CC）有反反函数 Agf BBfg CC
5、f Dg12设图GG的邻接接矩阵为为则G的边边数为( DD )A55 B6 CC3 DD413下列数数组中，能能构成无无向图的的度数列列的数组组是( C ) A(1, 1, 2, 3) BB(1, 2, 3, 4, 5) C(2, 2, 2, 2) D(1, 3, 3) 14设图GG，则下下列结论论成立的的是 ( CC )Adeeg(VV)=22E BBdegg(V)=EC D解；C为为握手定定理。15有有向完全全图D，则图D的边数数是( D )AE(E1)/2 BV(V1)/2CE(E1) DV(V1)agbdfce解：有向向完全图图是任意意两点间间都有一一对方向向相反的的边的图，其边边数应
6、为为D，即即 16给定无无向图GG如右图图所示，下下面给出出的结点点集子集中中，不是是点割集集的为（A） Ab, d Bd Ca, c DDg, e 17设设G是连通通平面图图，有vv个结点点，e条边，rr个面，则则r= ( AA )Aev2 BBve2 CCev2 DDev218无向图图G存在欧欧拉通路路，当且且仅当( D )AG中中所有结结点的度度数全为为偶数 BG中至多多有两个个奇数度度结点CG连连通且所所有结点点的度数数全为偶偶数 DG连通且且至多有有两个奇奇数度结结点19设设G是有n个结点点，m条边的的连通图图，必须须删去GG的( A )条边边，才能能确定GG的一棵棵生成树树A B
7、C D 20已知一一棵无向向树T中有8个结点点，4度，3度，2度的分分支点各各一个，T的树叶数为BA88 B5 CC4 DD 3二、填空空题 1设设集合，则则AB=1，22，3=A，AB=B，A B=3，P(A)-P(B )=33,1,33,2,33,1,22,32设AA, B为任意意集合，命命题A-B=的条件件是3设集集合A有n个元素素，那么么A的幂集集合P(A)的元素素个数为为 4设设集合AA = 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 +
8、bb4则R的集集合表示示式为6设集集合A=00,1,2,B=00,2,4,R是A到B的二元元关系，则R的关关系矩阵阵MR7设集集合A=11, 22, 33, 44 ，B=66, 88, 112，A到B的二元元关系R那么R1 8设设集合AA=a,b,c，A上的二二元关系系R=,，S=,则(RSS)1=9设集集合A=a,b,c，A上的二二元关系系R=, , , ，则则二元关关系R具有的的性质是是反自反反性 10设集合合A = 1 , 22 , 3 , 4 上的的等价关关系R = 1 , 22，2 , 1，3 , 4，4 , 3IA那么A中中各元素素的等价价类为1=2=11,2, 33=4=3,41
9、1设A，B为有限限集，且且|A|=m，|B|=n,那末A与B间存在在双射，当当且仅当当12设设集合AA=11, 22,BB=a, b，那么么集合AA到B的双射射函数是是a b f ce d图G 13已已知图GG中有1个1度结点点，2个2度结点点，3个3度结点点，4个4度结点点，则GG的边数数是155 14设给定定图G(如由图图所示)，则图图G的点割集是15设G=是具有有n个结点点的简单单图，若若在G中每一一对结点点度数之之和大于于等于，则则在G中存在在一条汉汉密尔顿顿路16设设无向图图G是哈密密顿图，则则V的任意意非空子子集V1，都有有V117设设有向图图D为欧拉拉图，则则图D中每个个结点的的
10、入度等等于出度度68792212318设设完全图图K有n个结点点(n2)，m条边，当时时，K中存在在欧拉回回路19图图G（如右右图所示示）带权权图中最最小生成树的权权是12220连连通无向向图G有6个顶点点9条边，从从G中删去去4条边才才有可能能得到GG的一棵棵生成树树T三、判断断说明题题1设AA、B、C为任意意的三个个集合，如如果AB=AC，判断断结论BB=C是否成成立？并并说明理理由解：不一一定成立立。反例例：A=1，22，3，B=1，C=31oo846952772如果果R1和R2是A上的自自反关系系，判断断结论：“R-11、R1R2、R1R2是自反反的” 是否成成立？并并说明理理由3设R
11、R，S是集合合A上传递递的关系系，判断断R S是是否具有有传递性性，并说说明理由由4若偏偏序集的哈斯斯图如右右图所示示，则acbedf集合A的的最小元元为1，最大大元不存存在解：结论论正确。5若偏偏序集的哈斯斯图如右右图所示示，则集合A的的极大元元为a，f；最大大元不存存在 解：结结论正确确。v1v2v3v5v4dbacefghn图G6图GG(如右图图)能否一一笔画出出？说明明理由若能画出出，请写写出一条条通路或或回路7判断断下图的的树是否否同构？说明理理由(a)(b)(c)8给定定两个图图G1，G2（如下下图所示示），试试判断它它们是否否为欧拉拉图、哈哈密顿图图？并说说明理由由abcdefg
12、图G2图G1v1v2v3v6v5v4 9判别图图G(如下图图所示)是不是是平面图图，并说说明理由由 10在有66个结点点，122条边的的简单平平面连通通图中，每每个面有有几条边边围成？为什么么？四、计算算题1设，求求：（1）(AB)C；（2）P(A)P(C)；（3）AB2设集集合Aa, b, c，B=b, d, e，求（1）BBA；（2）AB；（3）AB；（4）BA3设AA=11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 11, 122，R是A上的整整除关系系，B=22, 44, 66（1）写写出关系系R的表示示式；（2）画画出关系系R的哈斯斯图；（3）求求出
13、集合合B的最大大元、最最小元解：（11）解：（22）画出出哈斯图图（见课课堂答疑疑）解：（33）B=2，44，6，B的的最小元元为2，BB没有最最大元。adbc4设集集合Aa, b, c, d上的二二元关系系R的关系图如如右图所所示（1）写写出R的表达达式；（2）写写出R的关系系矩阵；（3）求求出R25设AA=00，1，2，3，4，R=|xA，yA且x+y0，S=|xA，yA且x+y=33，试试求R，S，RS，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）试试给出GG的图形形表示；（2）求求G
14、的邻接接矩阵；（3）判判断图DD是强连连通图、单单侧连通通图还是是弱连通通图？7设图图G=，V= v1，v2，v3，v4，v5，E= (v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) （1）试试给出GG的图形形表示；（2）写写出其邻邻接矩阵阵；（3）求求出每个个结点的的度数（4）画画出图GG的补图图的图形形解：（11）画出出G的图图形8图GG=，其中中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
15、) ，对应应边的权权值依次次为5，2，1，2，6，1，9，3及8（1）画画出G的图形形；（2）写写出G的邻接接矩阵；51063478921（3）求求出G权最小小的生成成树及其其权值 9已已知带权权图G如右图图所示试（1）求求图G的最小小生成树树；（2）计计算该生生成树的的权值10设设有一组组权为22,3,5,77,111,133,177,199,233,299,311,试（1）画画出相应应的最优优二叉树树；（2）计计算它们们的权值值五、证明明题 1试试证明集集合等式式：A (BC)=(AB) (AC) 2证明对对任意集集合A，B，C，有 3设R是集合合A上的对对称关系系和传递递关系，试试证明：若对任任意aA，存在在bA，使得得R，则R是等价价关系 4若非空空集合AA上的二二元关系系R和S是偏序序关系，试证明：也是A上的偏序关系 5若若无向图图G中只有有两个奇奇数度结结点，则则这两个个结点一一定是连连通的6设GG是连通通简单平平面图，则则它一定定有一个个度数不不超过55的结点点（提提示：用用反证法法） 7设设连通图图G有k个奇数数度的结结点，证证明在图图G中至少少要添加加条边才才能使其其成为欧欧拉图 8证证明任何何非平凡凡树至少少有2片树叶叶10