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

11离散数学形成性考核作业（三）集合论与图论综合练习本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第三次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。一、单项选择题1．若集合A＝{2，a，{a}，4}，则下列表述正确的是(B)．A．{a，{a}}AB．{a}AC．{2}AD．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．BA，且BAB．BA，但BAC．BA，但BAD．BA，且BA4．设集合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,ba,bA,且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,baA，bB且1ba}则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．自反性，反对称性和传递性229．设集合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：RR，f(a)=2a+1；g：RR，g(a)=a2．则（C）有反函数．A．gfB．fgC．fD．g12．设图G的邻接矩阵为0101010010000011100000100则G的边数为(D)．A．5B．6C．3D．413．下列数组中，能构成无向图的度数列的数组是(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)=2EB．deg(V)=EC．EvVv2)deg(D．EvVv)deg(解；C为握手定理。15．有向完全图D＝V，E，则图D的边数是(D)．A．E(E－1)/2B．V(V－1)/2C．E(E－1)D．V(V－1)解：有向完全图是任意两点间都有一对方向相反的边的图，其边数应为D，即)1(2VVPv16．给定无向图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＋224135agbdfce3318．无向图G存在欧拉通路，当且仅当(D)．A．G中所有结点的度数全为偶数B．G中至多有两个奇数度结点C．G连通且所有结点的度数全为偶数D．G连通且至多有两个奇数度结点19．设G是有n个结点，m条边的连通图，必须删去G的(A)条边，才能确定G的一棵生成树．A．1mnB．mnC．1mnD．1nm20．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为B．A．8B．5C．4D．3二、填空题1．设集合AB{,,},{,}12312，则AB={1，2，3}=A，AB=B，A–B={3}，P(A)-P(B)={{3},{1,3},{2,3},{1,2,3}}．2．设A,B为任意集合，命题AB的条件是BA．3．设集合A有n个元素，那么A的幂集合P(A)的元素个数为n2．4．设集合A={1，2，3，4，5，6}，A上的二元关系AbabaR,,{且1ba}，则R的集合表示式为}5,6,6,5,4,5,5,4,3,4,4,3,2,3,3,2,1,2,2,1{．5．设集合A={1，2，3，4，5}，B={1，2，3}，R从A到B的二元关系，R={a,baA，bB且2a+b4}则R的集合表示式为}1,3,2,2,1,2,3,1,2,1,1,1{．6．设集合A={0,1,2},B={0,2,4},R是A到B的二元关系，},,{BAyxByAxyxR且且则R的关系矩阵MR＝011000011．7．设集合A={1,2,3,4}，B={6,8,12}，A到B的二元关系R＝},,2,{ByAxxyyx那么R－1＝}4836{}8463{1，，，，所以，，，解：RR8．设集合A={a,b,c}，A上的二元关系R={a,b,c.a}，S={a,a,a,b,c,c}则(RS)－1=．111},,,{)(},,,,{RScbcaSRbcacSR所以解：449．设集合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间存在双射，当且仅当nmBA即,．12．设集合A={1,2},B={a,b}，那么集合A到B的双射函数是.)2(,)1(),(;)2(,)1(),(agbgxgbfafxf即即．13．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15．14．设给定图G(如由图所示)，则图G的点割集是{f}．15．设G=V，E是具有n个结点的简单图，若在G中每一对结点度数之和大于等于1n，则在G中存在一条汉密尔顿路．16．设无向图G＝V,E是哈密顿图，则V的任意非空子集V1，都有)(1VGWV1．17．设有向图D为欧拉图，则图D中每个结点的入度等于出度．18．设完全图Kn有n个结点(n≥2)，m条边，当为奇数n时，Kn中存在欧拉回路．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、R1R2是自反的”是否成立？并说明理由．是自反的。，，那么，，，，从而，，上的自反关系，必有是和解：结论都成立。2121112121112121RRRRRRRIRRIRIRIRIARRAAAAAabfced图G184695277687922123553．设R，S是集合A上传递的关系，判断RS是否具有传递性，并说明理由．不具传递性。，，，，，，，，，，，但，，，，，，，，，，，，，，，反例：不一定具有传递性。上的传递关系，是，解：}221331111221{}221331{}111221{}321{SRSRASRASR4．若偏序集A，R的哈斯图如右图所示，则集合A的最小元为1，最大元不存在．解：结论正确。5．若偏序集，R的哈斯图如右图所示，则集合A的极大元为a，f；最大元不存在．解：结论正确。6．图G(如右图)能否一笔画出？说明理由．若能画出，请写出一条通路或回路．1543425321evdvcvnvhvfvgvbvavv写一条回路如下：此图是欧拉图。解：能一笔画出。因为7．判断下图的树是否同构？说明理由．同构。与可见，，，，，，；，，，，，，；，，，，，，下：它们的结点度数序列如同构。与不同构；与不同构；与解：)()(}331111{)(}331111{)(}241111{)()()()()()()(cbcbacbcaba8．给定两个图G1，G2（如下图所示），试判断它们是否为欧拉图、哈密顿图？并说明理由．.,,,,,,,,,,,,,2211ebbaaccddggffeGGGG回路如下，是哈密顿图，有哈密顿不是欧拉图，但不是哈密顿图。路。都是偶数，具有欧拉回通的且每个结点的度数是欧拉图。因为它是连解：v1v2v3v5v4dbacefghn图Gabcdefg图G2图G1acbedf(a)(b)(c)669．判别图G(如下图所示)是不是平面图，并说明理由．去掉交叉点。请画图。分别向外拉出，就可以边解：是平面图。可以将314151,,,,,vvvvvv10．在有6个结点，12条边的简单平面连通图中，每个面有几条边围成？为什么？条边围成。且每个面都有个面。应有，由欧拉定理知，条边的简单平面连通图个结点，解：画出一个38,812622,2126evrrev四、计算题1．设}4,2{},5,2,1{},4,1{},5,4,3,2,1{CBAE，求：（1）(AB)~C；（2）P(A)－P(C)；（3）AB．5,4,25,24)3(}4,1{},1{}4,2{},4{},2{,}4,1{},4{},1{,)()()2(5,3,15,3,11))(1(BACPAPCBA解：2．设集合A＝{a,b,c}，B={b,d,e}，求（1）BA；（2）AB；（3）A－B；（4）BA．bAB)1(解：edcbaBA,,,,)2(caBA,)3(edcacaedAB,,,,,)4(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）,12,1,11,1,10,1,9,1,8,1,7,1,6,1,5,1,4,1,3,1,2,1,1,1{R,8,4,4,4,12,3,9,3,6,3,3,3,12,2,10,2,8,2,6,2,4,2,2,2}12,12,11,11,10,10,9,9,8,8,7,7,12,6,6,6,10,5,5,5,12,4v1v2v3v6v5v477解：（2）画出哈斯图（见课堂答疑）解：（3）B={2，4，6}，B的最小元为2，B没有最大元。4．设集合A＝{a,b,c,d}上的二元关系R的关系图如右图所示．（1）写出R的表达式；（2）写出R的关系矩阵；（3）求出