《电大 离散数学 形成性考核册 作业(三)答案5227.docx》由会员分享，可在线阅读，更多相关《电大 离散数学 形成性考核册 作业(三)答案5227.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、10离散数学形成性考核作业（三）集合论与图图论综合练练习本课程形成成性考核作作业共4次，内容容由中央电电大确定、统统一布置。本本次形考作作业是第三三次作业，大大家要认真真及时地完完成图论部部分的形考考作业，字字迹工整，抄抄写题目，解解答题有解解答过程。一、单项选选择题1若集合合A2，a， a ，4，则下下列表述正正确的是( B )Aaa， a A BB a A CC2A DA 22设B = 2, 3, 4, 2，那那么下列命命题中错误误的是（BB）A2B B2, 2, 3, 4B CC2B D2, 2B3若集合合A=a，b，1，2 ，B=1，2，则（B） AAB A，且BA BB A，但BA
2、CCB A，但BA DB A，且BA 44设集合合A = 1, aa ，则P(A) = ( CC ) AA1, aa BB,1, aa CC,1, aa, 1, aa DD1, aa, 1, aa 5设集集合A = 1，2，3，4，5，6 上的的二元关系系R =a , ba , bA , 且a +b = 88，则R具有的性性质为（BB）A自反反的 B对称的C对称和和传递的 D反反自反和传传递的6设集合合A = 1，2，3，4，5 ，B = 1，2，3，R从A到B的二元关关系，R =aa , baA，bB且则R具有的的性质为（）A自反反的 B对对称的 CC传递的的 D反自自反的注意：此题有误误！
3、自反性性、反自反反性、对称称性、反对对称性以及及传递性指指某一个集合合上的二元元关系的性性质。 77设集合合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）闭包 AA自反 BB传递 C对称称 D以上都不不对8非空集集合A上的二元元关系R，满足( A )，则称R是等价关关系A自反反性，对称称性和传递递性 B反反自反性，对对称性和传传递性C反自反反性，反对对称性和传传递性 D自自反性，反反对称性和和传递性9设集集合A=a, b，则A上的二元元关系R=，是A上的(
4、 C )关系A是等等价关系但但不是偏序序关系 B是偏偏序关系但但不是等价价关系24135C既是等等价关系又又是偏序关关系 DD不是等等价关系也也不是偏序序关系 110设集集合A = 1 , 2 , 3 , 4 , 5上的的偏序关系系的哈斯图如如右图所示示,若A的子集B = 33 , 44 , 55，则元素3为为B的（C） AA下界 B最大大下界 C最小小上界 D以上上答案都不不对 111设函函数f：R R，f (a) = 2a + 11；g：R R，g(a) = a 2则（C）有反函函数 AAgf BBfg CCf Dg12设设图G的邻接矩矩阵为则G的边数数为( D )A5 B6 C3 D41
5、3下下列数组中中，能构成成无向图的的度数列的的数组是( C ) A(11, 1, 2, 3) B(1, 2, 33, 4, 5) C(2, 2, 22, 2) D(1, 3, 33) 114设图图G，则下列列结论成立立的是 ( C )Adegg(V)=2E Bdeg(V)=EC DD解；C为握握手定理。15有向向完全图DD，则图D的边数是是( D )AE(EE1)/22 BV(V1)/22CE(EE1) DV(V1)agbdfce解：有向完完全图是任任意两点间间都有一对对方向相反反的边的图，其边数数应为D，即即 116给定无向向图G如右图所所示，下面面给出的结结点集子集中，不不是点割集集的为（
6、AA） AAb, d Bd CCa, c Dg, e 17设GG是连通平平面图，有有v个结点，ee条边，r个面，则则r= ( A )Aevv2 Bve2 Cev2 Dev218无无向图G存在欧拉拉通路，当当且仅当( D )AG中所所有结点的的度数全为为偶数 BBG中至多有有两个奇数数度结点CG连通通且所有结结点的度数数全为偶数数 DDG连通且至至多有两个个奇数度结结点19设GG是有n个结点，mm条边的连连通图，必必须删去GG的( A )条边，才才能确定GG的一棵生生成树A B C DD 220已知一棵棵无向树TT中有8个结点，44度，3度，2度的分支支点各一个个，T的树叶数数为BA8 B5 C
7、4 D 3二、填空题题 11设集合合，则AB=1，22，3=A，AB=B，A B=3，P(A)-P(B )=33,11,3,2,33,11,2,332设A, B为任意集集合，命题题A-B=的条件是是3设集合合A有n个元素，那那么A的幂集合合P(A)的元素个个数为 44设集合合A = 1，2，3，4，5，6 ，A上的二元元关系且，则R的集合表表示式为5设集合合A = 1，2，3，4，5 ，B = 1，2，3，R从A到B的二元关关系， RR =a , baA，bB且2a + b4则R的集合合表示式为为6设集合合A=0,1,2,B=0,2,4,R是A到B的二元关关系，则R的关系系矩阵MR7设集合合A
8、=1, 2, 3, 44 ，B=6, 8, 12，A到B的二元关关系R那么R11 88设集合合A=a,b,c，A上的二元元关系R=,，S=,则(RS)1=9设集合合A=a,b,c，A上的二元元关系R=, , , ，则二二元关系RR具有的性性质是反自自反性 110设集集合A = 1 , 2 , 3 , 4 上上的等价关关系R = 1 , 2，2 , 1，3 , 4，4 , 3IA那么A中各各元素的等等价类为1=2=1,2, 3=4=3,4411设设A，B为有限集集，且|A|=m，|B|=n,那末A与B间存在双双射，当且且仅当12设集集合A=1, 2,B=a, b，那么集集合A到B的双射函函数是a
9、 b f ce d图G 13已知知图G中有1个1度结点，22个2度结点，33个3度结点，44个4度结点，则则G的边数是是15 114设给定图图G(如由图所所示)，则图G的点割集是15设设G=是具有n个结点的的简单图，若若在G中每一对对结点度数数之和大于于等于，则则在G中存在一一条汉密尔尔顿路16设无无向图G是哈密顿顿图，则VV的任意非非空子集VV1，都有V117设有有向图D为欧拉图图，则图DD中每个结结点的入度度等于出度度68792212318设完完全图K有n个结点(n2)，m条边，当时，K中存在欧欧拉回路19图GG（如右图图所示）带带权图中最最小生成树的权是是1220连通通无向图GG有6个顶
10、点9条边，从从G中删去44条边才有有可能得到到G的一棵生生成树T三、判断说说明题1设A、B、C为任意的的三个集合合，如果AAB=AC，判断结结论B=C是否成立立？并说明明理由解：不一定定成立。反反例：A=1，22，3，BB=1，C=31oo846952772如果RR1和R2是A上的自反反关系，判判断结论：“R-11、R1R2、R1R2是自反的的” 是否成成立？并说说明理由3设R，S是集合A上传递的的关系，判判断R S是否否具有传递递性，并说说明理由4若偏序序集的哈斯图图如右图所所示，则acbedf集合A的最最小元为11，最大元元不存在解：结论正正确。5若偏序序集的哈斯图图如右图所所示，则集合A
11、的极极大元为aa，f；最大元元不存在 解解：结论正正确。v1v2v3v5v4dbacefghn图G6图G(如右图)能否一笔笔画出？说说明理由若能画出，请请写出一条条通路或回回路7判断下下图的树是是否同构？说明理由由(a)(b)(c)8给定两两个图G1，G2（如下图图所示），试试判断它们们是否为欧欧拉图、哈哈密顿图？并说明理理由abcdefg图G2图G1v1v2v3v6v5v4 99判别图G(如下图所所示)是不是平平面图，并并说明理由由 110在有有6个结点，112条边的的简单平面面连通图中中，每个面面有几条边边围成？为为什么？四、计算题题1设，求求：（1）(AAB)C；（2）P(A)P(C)；
12、（3）AB2设集合合Aa, b, c，B=b, d, e，求（1）BAA；（2）AB；（3）AB；（4）BA3设A=1, 2, 33, 4, 5, 6, 77, 8, 9, 10, 11, 12，R是A上的整除除关系，BB=2, 4, 6（1）写出出关系R的表示式式；（2）画出出关系R的哈斯图图；（3）求出出集合B的最大元元、最小元元解：（1）解：（2）画画出哈斯图图（见课堂堂答疑）解：（3）BB=2，44，6，BB的最小元元为2，BB没有最大大元。adbc4设集合合Aa, b, c, d上的二元元关系R的关系图如右右图所示（1）写出出R的表达式式；（2）写出出R的关系矩矩阵；（3）求出出R2
13、5设A=0，1，2，3，4，R=|xA，yA且x+y0，S=|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设图GG=，其中V=a1, a2, a3, a4, a5,E=，（1）试给给出G的图形表表示；（2）求GG的邻接矩矩阵；（3）判断断图D是强连通通图、单侧侧连通图还还是弱连通通图？7设图GG=，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）求出出每个
14、结点点的度数（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), (e, f) ，对对应边的权权值依次为为5，2，1，2，6，1，9，3及8（1）画出出G的图形；（2）写出出G的邻接矩矩阵；51063478921（3）求出出G权最小的的生成树及及其权值 99已知带带权图G如右图所所示试（1）求图图G的最小生生成树；（2）计算算该生成树树的权值10设有有一组权为为2,3,5,7,11,113,177,19,2
15、3,229,311,试（1）画出出相应的最最优二叉树树；（2）计算算它们的权权值五、证明题题 11试证明明集合等式式：A (BC)=(AB) (AC) 22证明对任任意集合AA，B，C，有 33设R是集合A上的对称称关系和传传递关系，试试证明：若若对任意aaA，存在bA，使得R，则R是等价关关系 44若非空集集合A上的二元元关系R和S是偏序关关系，试证明：也是是A上的偏序序关系 5若无无向图G中只有两两个奇数度度结点，则则这两个结结点一定是是连通的6设G是是连通简单单平面图，则则它一定有有一个度数数不超过55的结点（提示：用反证法法） 77设连通通图G有k个奇数度度的结点，证证明在图GG中至少要要添加条边边才能使其其成为欧拉拉图 88证明任任何非平凡凡树至少有有2片树叶10