电大_离散数学形成性考核作业集合

1离散数学形成性考核作业（一）集合论部分分校_________学号____________姓名___________分数___________本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第一次作业，大家要认真及时地完成集合论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。第1章集合及其运算1．用列举法表示“大于2而小于等于9的整数”集合．2．用描述法表示“小于5的非负整数集合”集合．3．写出集合B={1,{2,3}}的全部子集．4．求集合A={,{}}的幂集．5．设集合A={{a},a}，命题：{a}P(A)是否正确，说明理由．6．设ABC{,,},{,,},{,,},123135246求(1)AB(2)ABC(3)C-A(4)AB7．化简集合表示式：((AB)B)-AB．8．设A,B,C是三个任意集合，试证：A-(BC)=(A-B)-C．9．填写集合{4,9}{9,10,4}之间的关系．10．设集合A={2,a,{3},4}，那么下列命题中错误的是（）．A．{a}AB．{a,4,{3}}AC．{a}AD．A11．设B={{a},3,4,2}，那么下列命题中错误的是（）．A．{a}BB．{2,{a},3,4}BC．{a}BD．{}B第2章关系与函数1．设集合A={a,b}，B={1,2,3}，C={3,4}，求A(BC)，(AB)(AC)，并验证A(BC)=(AB)(AC)．2．对任意三个集合A,B和C，若ABAC，是否一定有BC？为什么？23．对任意三个集合A,B和C，试证若AB=AC，且A，则B=C．4．写出从集合A={a，b，c}到集合B={1}的所有二元关系．5．设集合A={1，2，3，4，5，6}，R是A上的二元关系，R={a,ba,bA,且a+b=6}写出R的集合表示式．6．设R从集合A={a，b，c，d}到B={1，2，3}的二元关系，写出关系R={a,1，a,3，b,2，c,2，c,3}的关系矩阵，并画出关系图．7．设集合A={a,b,c,d}，A上的二元关系R={a,b，b,d，c,c，c,d}，S={a,c，b,d，d,b，d,d}．求RS，RS，R-S，~（RS），RS．8．设集合A={1,2}，B={a,b,c}，C={,}，R是从A到B的二元关系，S是从B到C的二元关系，且R={1,a，1,b，2,c}，S={a,，b,}，用关系矩阵求出复合关系R·S．39．设集合A={1,2,3,4}上的二元关系R={1,1，1,3，2,2，3,1，3,3，3,4，4,3，4,4}，判断R具有哪几种性质？10．设集合A={a,b,c,d}上的二元关系R={a,a，a,b，b,b，c,d}，求r(R)，s(R)，t(R)．11．设集合A={a,b,c,d}，R，S是A上的二元关系，且R={a,a,a,b,b,a,b,b,c,c,c,d,d,c,d,d}S={a,b,b,a,a,c,c,a,b,c,c,b,a,a,b,b,c,c}试画出R和S的关系图，并判断它们是否为等价关系，若是等价关系，则求出A中各元素的等价类及商集．12．图1.1所示两个偏序集A，R的哈斯图，试分别写出集合A和偏序关系R的集合表达式．dbaecfg(1)bgdcefa(2)图1.1题12哈斯图413．画出各偏序集A，1的哈斯图，并指出集合A的最大元、最小元、极大元和极小元．其中：A={a,b,c,d,e}，1={a,b，a,c，a,d，a,e，b,e,c,e，d,e}IA；14．下列函数中，哪些是满射的？那些是单射的？那些是双射的？(1)f1：RR，f(a)=a3+1；(2)f4：N{0,1}，f(a)=为偶数为奇数aa,1,0．15．设集合A={1,2}，B={a,b,c}，则BA=．16．设集合A={1，2，3，4}，A上的二元关系R={1,2，1,4，2,4，3,3}，S={1,4，2,3，2,4，3,2}，则关系（）={1,4，2,4}．A．RSB．RSC．R-SD．S-R17．设集合A={1,2,3,4}上的二元关系R={1,1，2,3，2,4，3,4}，则R具有（）．A．自反性B．传递性C．对称性D．反自反性18．设集合A={a,b,c,d,e}上的偏序关系的哈斯图如图1.2所示．则A的极大元为，极小元为．19．设R为实数集，函数f：RR，f(a)=-a2+2a-1，则f是（）．A．单射而非满射B．满射而非单射C．双射D．既不是单射也不是满射离散数学形成性考核作业（二）图论部分本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第二次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。第3章图的基本概念与性质1．计算出下图2.1的结点数与边数，并说明其满足握手定理．图2.1习题1的图bcaed图1.2题18哈斯图52．试分别画出下列图2.2(a)、(b)、(c)的补图．图2.2习题2的图3．找出下图2.3中的路、通路与圈．图2.3习题3的图4．设G为无向图，|G|=9，且G每个结点的度数为5或6，试证明G中至少有5个6度结点或至少有6个5度结点．5．设有向图D=V,E如图2.4所示，图2.4习题5的图试问图中是否存在长度分别为3,4,5,6的回路，如存在，试找出．6．若无向图G有10条边，3度与4度结点均2个，其余结点的度数均小于3，试问G中至少有几个结点？若无向图G中有6条边，3度与5度结点均有一个，其余结点的度数均是2，试问G中有几个结点?7．试求图2.5中有向图的强分图，单侧分图和弱分图．图2.5习题7的图8．试说明图2.6中G1和G2同构．G2G1图2.6习题8的图9．试求图2.7中的邻接矩阵与可达矩阵．6图2.7习题9的图10．有n个结点的无向完全图的边数为．11．图中度数为奇数的结点为数个．12．已知图G的邻接矩阵为，则G有（）．A．5点，8边B．6点，7边C．5点，7边D．6点，8边第4章几种特殊图1．试分别构造满足下列条件的无向欧拉图（1）有偶数个结点，奇数条边．（2）有偶数个结点，偶数条边．（3）有奇数个结点，偶数条边．（4）有奇数个结点，奇数条边．2．分别构造满足下列条件的四个汉密尔顿图（1）偶数个结点，奇数条边．（2）有偶数个结点，偶数条边．（3）有奇数个结点，偶数条边．（4）有奇数个结点，奇数条边．3．试画出一个没有一条欧拉回路，但有一条汉密尔顿回路的图．4．如图2.8是否为欧拉图？试说明理由．图2.8判断是否为欧拉图5．如图2.9是否为汉密尔顿图？试说明理由．图2.9判断是否为汉密尔顿图6．试分别说明图4.3（a）、（b）与（c）是否为平面图．图2.10判断是否为平面图77．试分别求出图2.11（a）、（b）与（c）的每个图的面的次数．图2.11求面的次数8．试利用韦尔奇·鲍威尔算法分别对图2.12（a）、（b）与（c）着色．图2.12图的着色9．若G是一个汉密尔顿图，则G一定是()．A．欧拉图B．平面图C．连通图10．设G是有n个结点m条边的连通平面图，且有k个面，则k等于()．A．m-n+2B．n-m-2C．n+m-2D．m+n+211．无向连通图G是欧拉图的充分必要条件是_________________．12．设G是具有n个结点的简单图，若在G中每一对结点度数之和大于等于________，则在G中存在一条汉密尔顿路．13．现有一个具有k个奇数度结点的图，若要使图中有一条欧拉回路，最少要向图中添加_________条边．第5章树及其应用1．试指出图2.13中那些是树，那些是森林，并说明理由．图2.13习题1的图2．试画出图2.14中的一个生成树，并说明其中的树枝、弦，以及对应生成树的补．图2.14习题2的图3．试画出如图2.15的完全图K5的所有不同构的生成树．图2.15习题3的图4．试求出图2.16中的最小生成树及其权值．8图2.16习题4的图5．给定一组权值为1，2，2，3，6，7，9，12，是求出相应的一个最优树．6．无向树T有7片树叶,3个3度结点,其余的都是4度结点，则T有（）个4度结点？A．1B．2C．3D．47．无向树T有3个3度结点,2个4度结点,其余的都是树叶，则T有（）片树叶？A．3B．7C．9D．118．无向树T有1个2度结点,3个3度结点,4个4度结点,1个5度结点,其余的都是树叶，则T有（）片树叶？A．12B．14C．16D．209．无向树T有9片树叶,5个3度结点,其余的都是4度结点，则T有几个4度结点？A．0B．1C．2D．3离散数学形成性考核作业（三）集合论与图论综合练习本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第三次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。一、单项选择题1．若集合A＝{2，a，{a}，4}，则下列表述正确的是()．A．{a，{a}}AB．{a}AC．{2}AD．A2．设B={{2},3,4,2}，那么下列命题中错误的是（）．A．{2}BB．{2,{2},3,4}BC．{2}BD．{2,{2}}B3．若集合A={a，b，{1，2}}，B={1，2}，则（）．A．BA，且BAB．BA，但BAC．BA，但BAD．BA，且BA4．设集合A={1,a}，则P(A)=()．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具有的性质为（）．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的（）闭包．A．自反B．传递C．对称D．以上都不对8．非空集合A上的二元关系R，满足()，则称R是等价关系．A．自反性，对称性和传递性B．反自反性，对称性和传递性C．反自反性，反对称性和传递性D．自反性，反对称性和传递性9．设集合A={a,b}，则A上的二元关系R={a,a，b,b}是A上的()关系．9A．是等价关系但不是偏序关系B．是偏序关系但不是等价关系C．既是等价关系又是偏序关系D．不是等价关系也不是偏序关系10．设集合A={1,2,3,4,5}上的偏序关系的哈斯图如右图所示,若A的子集B={3,4,5}，则元素3为B的（）．A．下界B．最大下界C．最小上界D．以上答案都不对11．设函数f：RR，f(a)=2a+1；g：RR，g(a)=a2．则（）有反函数．A．gfB．fgC．fD．g12．设图G的邻接矩阵为0101010010000011100000100则G的边数为()．A．5B．6C．3D．413．下列数组中，能构成无向图的度数列的数组是()．A．(1,1,2,3)B．(1,2,3,4,5)C．(2,2,2,2)D．(1,3,3)14．设图G＝V,E，则下列结论成立的是()．A．deg(V)=2EB．deg(V)=EC．EvVv2)deg(D．EvVv