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

哈尔滨工业大学（威海）2014 / 2015学年春季学期 集合论与图论 试题卷（A）考试形式（开、闭卷）：闭卷 答题时间：105（分钟）本卷面成绩占课程成绩 30 % 题号一二三四五卷 面总 分分数试卷说明：1 卷面总分100分，取卷面成绩的70%计入总分，平时成绩30%。2 填空题请在答题卡内答题，其它处无效。3 答卷时禁止拆开试卷钉，背面即为草稿纸。得分一、填空题（每小题2分，共20分）题号答案题号答案16273849510(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时，树的连通度是（ ）。得分二、简答题(每小题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.简述图的连通度、边连通度、最小度之间的关系。得分三、证明题（每小题10分，共20分）1. A和B是两个集合，证明： (AB)c=AcBc2. 证明：3度正则图（每个顶点的度数都是3）的顶点的数目必为偶数。得分四、计算题（每小题5分，共20分）1. 集合X=a,b,c,d,e,f,g,h,X的两个子集是A=a,b,c,d,B=e,f,g,h 求：AB,AB,Ac,AB,ADB2、一个学校学生总人数为336人，共有数学，物理，化学3门课 。已知参加这3门课的学生人数分别有170,130,120人；同时参加数学、物理两门课的学生有45人；同时参加数学、化学的有20人；同时参加物理、化学的有22人；问同时参加三门课的学生有多少人？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)求：RS和SR得分五、综合题（每小题10分，共20分）1、（1）举例说明什么是偶图？（2分）（2）一个图是偶图的充分必要条件是什么？（3分）（3）已知图G是偶图，写出图G的顶点划分过程。（5分）2、 （1）举例说明什么是欧拉图