哈工大威海校区2015春集合图论试题A

姓名:班级:学号:遵守考试纪律注意行为规范出题教师签字:教研室主任签字:第1页(共8页)哈尔滨工业大学（威海）2014/2015学年春季学期集合论与图论试题卷（A）考试形式（开、闭卷）：闭卷答题时间：105（分钟）本卷面成绩占课程成绩30%题号一二三四五卷面总分分数试卷说明：[1]卷面总分100分，取卷面成绩的70%计入总分，平时成绩30%。[2]填空题请在答题卡内答题，其它处无效。[3]答卷时禁止拆开试卷钉，背面即为草稿纸。一、填空题（每小题2分，共20分）题号答案题号答案16273849510得分第2页(共8页)(1)集合的（）表示方法可能产生悖论。(2)映射f左可逆的充分必要条件是：（）。(3)设R={(a,b),(c,d),(e,f)}是一个二元关系，则R的逆记为R-1，R-1=（）。(4)n个顶点的完全图的边的个数是()。(5)一个无向图的边数为20，那么所有顶点的度数和为（）。(6)设G是一个有p个顶点q条边的最大可平面图,则:q=()。(7)一个图是树当且仅当G是连通的且p=（）。(8)G是一个p个顶点q条边的最大平面图,则G的每个面都是()形。(9)若G是偶数个顶点的圈，则G是（）色的。(10)当顶点数大于2时，树的连通度是（）。第3页(共8页)二、简答题(每小题5分，共20分)1.设集合X=｛a,b,c,d,e｝，E={a,b,c}是X的子集。写出E的特征函数。2.R=｛（1，b），（2,c），（3,a），（4,d）｝是集合A=｛1，2，3，4｝到集合B=｛a,b,c,d｝的一个二元关系，画出R的关系矩阵和关系图。3.举例说明什么是偏序关系？什么是偏序集？4.简述图的连通度、边连通度、最小度之间的关系。得分第4页(共8页)三、证明题（每小题10分，共20分）1.A和B是两个集合，证明：(A∪B)c=Ac∩Bc2.证明：3度正则图（每个顶点的度数都是3）的顶点的数目必为偶数。得分第5页(共8页)四、计算题（每小题5分，共20分）1.集合X={a,b,c,d,e,f,g,h},X的两个子集是A=｛a,b,c,d｝,B={e,f,g,h}求：AB,AB,Ac,A\B,AB2、一个学校学生总人数为336人，共有数学，物理，化学3门课。已知参加这3门课的学生人数分别有170,130,120人；同时参加数学、物理两门课的学生有45人；同时参加数学、化学的有20人；同时参加物理、化学的有22人；问同时参加三门课的学生有多少人？得分第6页(共8页)3.集合X=｛1,2,3,4,5｝，Y=｛a,b,c,d,e,f｝，f是X到Y的一个映射，其中：f(1)=b,f(2)=a,f(3)=a,f(4)=c,f(5)=d,A和B分别是X和Y的子集，其中：A=｛1,2,3｝,B={a,c,f}。求：f(A),f-1(B)4.设集合X={a,b,c,d,e,f},R和S是X上的二元关系，其中：R={(a,b),(c,d),(e,f)},S={(b,c),(d,a),(b,a),(f,d)}求：RS和SR第7页(共8页)五、综合题（每小题10分，共20分）1、（1）举例说明什么是偶图？（2分）（2）一个图是偶图的充分必要条件是什么？（3分）（3）已知图G是偶图，写出图G的顶点划分过程。（5分）得分第8页(共8页)2、（1）举例说明什么是欧拉图？（2分）（2）一个图G是欧拉图的充分必要条件是什么？（3分）（3）已知图G是欧拉图，写出求G的欧拉闭迹的过程。（5分）