资源描述：
《07秋季学期考试题a》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、07年秋季学期集合论与图论考试题A本试卷满分90分，06级计算机专业一、判断对错(正确画“丁”，错误画“X”，本题满分10分，每小题各1分)仁若PUQ=Q,PC]Q=0则P=0。()答案：V2.A,B是集合，则命题AqB和AuB不可能同时成立。()答案:X3•若=AAC,则B=C。()答案：V4•设A与B是两个任意集合，若｛AHB,BA｝是AU3的一个划分，则有AB=0.()5•若R是集合A上的传递关系，则F不是集合A上的传递关系。()答案=X6•若图G不连通，则乙连通。(〉答案：V7•极大平面图必是连通图。(〉
2、答案：v8.设G=(V,E〉是连通图,eeE是G的一座桥，则e在G的每棵生成树中。(〉答案：V9•一个有向图G若仅有一个顶点的入度为0,其余顶点的入度全为1,则G—定是有向树。()答案：X10.有根树中最长路的两个端点都是树叶。()答案：X二、填空(要求只给出答案，本题满分15分，每小题各1分》答案：{0,{0},{{d}},{0,{d}}}2•设A={1,2,…/},B={1,2},则从A到B的满射的个数是(〉。答案：(2"-2)2.设X={a,b,c,d},R={(a,b),(b,c),(c,Q)},关系/?的传
3、递闭包是()o答案：(仏仪),(方,b),(c,c),仏方),(/?,c),(c,G),(d,c),(b,c),(c,b),(d,d))4•设3={0,l},E={a,b,c,・・・,x,y,z}。字母表B上所有字符串之集记为B*,字母表E上所有字符串之集记为E*o试求B*和E*的基数有什么关系。()答案：相等5•设X为集合且
4、X
5、=斤，则X上有多少个不同的自反或对称的二元关系。(〉答案：2宀7•设集合X中有3个元素，则X上的不同的等价关系的个数为()o答案：58•某班有学生50人，有26人在第一次考试中得优，有21
6、人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是()o答案：14人9.设A=仏上2,…，知},^<
7、p(p-l)o试求以V为顶点集具有q条边的无向图的个数。(答案:q〃(卩一1)/210.含5个顶点、3条边的不同构的无向图有(〉个。答案=411.设G=(V,E)是一个(p,q)图,且G中每个顶点的度数不是£就是£+1,贝ljG中度为比的顶点的个数是()o答案：p(k+1)-2q12.设无向图G有12条边，有6个3度顶点，其余顶点度数均小于3,则G中至少有(答案=9)个顶点。13•设G=
8、(V,E)是一个(pg)图。若G是一个K-正则图且每个回路圈的长度至少为4,则顶点p至少是()o答案：p>2K14.无向图G是由k(k^2)棵树组成的森林，至少要添加多少条边才能使G成为一棵树。(〉答案：k-115.设V=仏心…知｝。计算以V为顶点集的有向图的个数。()o答案=2“(p-1)三、计算下列各题(本题满分20分，第一题2分，其余每小题各3分〉1•是否存在一个同时不满足自反、反自反、对称、反对称和传递的二元关系?2•设A、B是任意的集合，若AB二B,则A、B有何关系？为什么?3.设集合A={a,b,c,d
9、,e},R二{(a,a),(a,b),(a,c),(a,d),(a,e),(brb),(b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)},验证：(A,R)是偏序集；并画出Hasses图2.设6=(V,E)是一个(p,q)图，每个顶点的度为3且q=2p—3(1)求P和q的值(2)G必为平面图吗？为什么?(3)G必是哈密顿图吗？G必是欧拉图吗？为什么?答案=(1)p=6,q=9(2)不一定是平面图。如6.3就不是平面图.(3)G-定是哈密顿图。因为对任一对不相邻的顶点w,vgV,degu
10、+degvMp=6故G不是欧拉图。因为G的顶点度数不全是偶数。5•设G是一个(p,p)连通图，则(1)G中至少有多少个圈。(2)G中至多有多少个生成树。6.设T是一棵树且△(T)MK,则T中至少有K个顶点的度为1。6.如图所示，求:(1)邻接矩阵；(2)"到v2的长度为4的有向通道的条数;(3)可达矩阵；(4)求强分图。证明下列个题(本题满分45分,每小题各5分》1•设A,B,C是三个任意集合，证明：Ax(BC)=(AxB)(AxC)2•设斤XtY,g：YtZ。若g。/是单射，则/与g那个是单射？并证明之。3•设
11、升XtY,C,DcK,证明：/-'(CAD)=/_,(04•设X={1,2,3},Y={1,2},S={/
12、/:XtY}。三是S上的二元关系:仁gwS,f三gol〉门=I〉g)。证明：(1)三是S上的等价关系；(2)求等价类的集合。5•设D=(V,A)是一个有向图。在V上定义二元关系今：/u,ueV9u=v当且仅当u与〃互达。证明：(1)竺是
