07秋季学期考试题A.docVIP

07年秋季学期 集合论与图论考试题A 本试卷满分90分， 06级计算机专业 一、判断对错 （ 正确画“√”，错误画“×”，本题满分10分，每小题各1分 ） 1.若则。（ ） 答案：√ 2.A，B是集合，则命题和不可能同时成立。（ ） 答案：× 3.若则B＝C。（ ） 答案：√ 4.设A与B是两个任意集合，若是的一个划分，则有。 （ ） 答案：√ 5.若R是集合A上的传递关系，则R2不是集合A上的传递关系。（ ） 答案：× 6.若图G不连通，则连通。（ ） 答案：√ 7.极大平面图必是连通图。（ ） 答案：√ 8.设G＝（V，E）是连通图，是G的一座桥，则e在G的每棵生成树中。（ ） 答案：√ 9.一个有向图G若仅有一个顶点的入度为0，其余顶点的入度全为1，则G一定是有向树。（ ） 答案：× 10.有根树中最长路的两个端点都是树叶。（ ） 答案：× 二、填空 （要求只给出答案，本题满分15分，每小题各1分） 1.集合（ ）。 答案： 2.设，，则从到的满射的个数是（ ）。 答案：（） 3.设，关系的传递闭包是 （ ）。 答案：（，（d,d）） 4.设。字母表上所有字符串之集记为，字母表上所有字符串之集记为。试求和的基数有什么关系。　　　　　　（ ） 答案：相等 5.设为集合且，则上有多少个不同的自反或对称的二元关系。（ ） 答案： 7.设集合中有3个元素，则上的不同的等价关系的个数为（ ）。 答案：5 8.某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是（ ）。 答案：14人 9.设，。试求以为顶点集具有条边的无向图的个数。（ ） 　答案：　　 10.含5个顶点、3条边的不同构的无向图有（ ）个。 答案：4 11. 设是一个图,且G中每个顶点的度数不是就是，则G中度为的顶点的个数是（ ）。 答案：p（k＋1）－2q 12.设无向图G有12条边，有6个3度顶点，其余顶点度数均小于3，则G中至少有（ ）个顶点。 答案：9 13.设是一个图。若是一个正则图且每个回路圈的长度至少为4，则顶点至少是（ ）。 答案： 14.无向图G是由k（k≥2）棵树组成的森林，至少要添加多少条边才能使G成为一棵树。（ ） 答案：k－1 15.设V＝。计算以V为顶点集的有向图的个数。（ ）。 答案： 三、计算下列各题 （本题满分20分，第一题2分，其余每小题各3分） 1.是否存在一个同时不满足自反、反自反、对称、反对称和传递的二元关系？ 2.设A、B是任意的集合,若A\B=B,则A、B有何关系？为什么？ 3.设集合A={a,b,c,d,e},R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b), (b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)}， 验证：（A,R）是偏序集；并画出Hasses图 4．设G＝（V，E）是一个（p，q）图，每个顶点的度为3且q＝2p－3 (1) 求p和q的值 (2) G必为平面图吗？为什么？ (3) G必是哈密顿图吗？G必是欧拉图吗？为什么？ 答案： （1） p＝6，q＝9 （2）不一定是平面图。如K3,3就不是平面图． （3）G一定是哈密顿图。因为对任一对不相邻的顶点， degu＋degv≥p＝6 　　故G不是欧拉图。因为G的顶点度数不全是偶数。 5.设G是一个（p，p）连通图，则 （1）G中至少有多少个圈。 （2）G中至多有多少个生成树。 6．设T是一棵树且Δ(T)≥K，则T中至少有K个顶点的度为1。 7．如图所示，求： （1）邻接矩阵； （2）v1到v2的长度为4的有向通道的条数； （3）可达矩阵； （4）求强分图。 四、证明下列个题（本题满分45分，每小题各5分） 1.设是三个任意集合，证明： 2.设。若是单射，则与那个是单射？并证明之。 3.设证明： 4.设。是S上的二元关系： 。证明： （1）是S上的等价关系； （2）求等价类的集合。 5.设D＝（V,A）是一个有向图。在V上定义二元关系≌：当且仅当u与互达。证明： （1）≌是等价关系； （2）求≌的等价类； （3）每个等价类导出的子图是什么子图？ 6.设是集合上的一个二元关系，证明： （1）是对称的；（2）是传递的。 7.设为可数集，利