答案08秋季集合论与图论试题a

《答案08秋季集合论与图论试题a》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、试题：班号：姓名：本试卷满分90分（计算机科学与技术学院07级）一、填空（本题满分10分，每小题各1分）1.设是集合，若，则等于什么？（）2．设X为集合，为X上的偏序关系，计算等于什么？（）3．把置换分解成循环置换的乘积。（（149）（2367）（58））4．什么是无穷集合？（凡能与自身的一个真子集对等的集称为无穷集合）5．设是一棵树，，则个顶点的树至多有多少个割点？（-2）6．设是一个有个顶点条弧的有向图，若是连通的，则至少是多大？（-1）7．设，则以V为顶点集的无向图共有多少个？（）8．设，则以V为顶点集的有向图共有多少个？）第7页（共7页）试题：班号：姓名：9．每个有3个支的不连通

2、图，若每个顶点的度均大于或等于2，则该图至少有多少个圈？（3）10．设是一个正则二元树，它有个叶子，则有多少条弧？（2（-1））二、判断对错（本题满分10分，每小题各1分）1.设是两个集合，则且不可能同时成立。（错）2．在集合上可以定义个二元运算。（错）3．设，若存在唯一一个映射，使得，则一定是可逆的。（错）4．设是一个集合，则上的自反和反自反的二元关系个数相同。（对）5.设为一个有限字母表，上所有字（包括空字）之集记为。则不是可数集。（错）6.设是一个图，若，则中必有圈。（对）7.若G是一个连通图，则至多有个生成树。（对)8.设，是正则图且顶点连通度为1，则。（对）9．把平面分成个区域

3、，每两个区域都相邻，则最大为5。（错）10.有向图的每一条弧必在某个强支中。（错）三、证明下列各题(本题满分18分，每小题各6分)1．设是三个任意的集合，则第7页（共7页）试题：班号：姓名：（1）证明：；（2）举例说明。证：(1)证明：，有，即但，从而，于是，即。(2)若，则。2．设是三个任意的集合，证明：。证明：设，则，，从而,,。于是，,因此，即。反之，设，有，，从而，，，故且。于是，即。因此，。3．设是两个任意的集合，证明：。证：，则若，则。因而且，故；若，则，同理可得。因此。反之，因为，故＝。于是，有。第7页（共7页）试题：班号：姓名：若，则，故；若，则，故。因此。从而＝。四、回

4、答下列各题(本题满分14分)1．如图1所示是彼德森图，回答下列问题：（6分）（1）是否是偶图？（不是）（2）是否是欧拉图？（不是）（3）是否是平面图？（不是）（4）是否是哈密顿图？（不是）（5）的色数为多少？（3）图12．设G是如图2所示的有向图，则（8分）（1）写出G的邻接矩阵。（2）求顶点到间长为10的有向通道的条数的方法是什么？（不必算出具体的数）（3）写出G的可达矩阵。（4）画出对应于表达式（A＋B*C）/（A-C）的二元树表示。解：（1）；（2）元素的值；（3）（4）第7页（共7页）试题：班号：姓名：五、证明下列各题(本题满分18分,每小题各6分)1．设。若是单射，则与哪个是单

5、射？请证明之。解：是单射。因为是单射，所以，若，则。因此，，故是单射。2．设。“”是上如下的二元关系：，当且仅当。则(1)证明：是等价关系；(2)求等价类数。证：(1)等价关系显然；(2)等价类数为：。3．令，利用康托对角线法证明S是不可数集。证:假设从N到{0,1}的所有映射之集可数，则可排成无重复项的无穷序列。每个函数确定了一个0,1序列。构造序列，若；否则。该序列对应的函数，，不为任一个，矛盾。六、证明下列各题（本题满分20分，每小题各5分）1.设是一个恰有两个不邻接的奇度顶点和的无向图，证明：第7页（共7页）试题：班号：姓名：连通连通。证：显然成立。假设不连通，则恰有2个分支：。

6、由题意不在一个分支上，于是含有的顶点的分支只有一个奇度数顶点与握手定理的推论矛盾。于是假设不成立，即是连通的。2．证明：任意一棵非平凡树至少有两个树叶。证明：设为一棵非平凡的无向树，中最长的路为。若端点和中至少有一个不是树叶，不妨设不是树叶，即有，则除与上的顶点相邻外，必存在与相邻，而不在上，否则将产生回路。于是仍为的一条比更长的路，这与为最长的路矛盾。故必为树叶。同理，也是树叶。3．证明：若每个顶点的度数大于或等于3，则不存在有7条边的平面连通图。证明：假设存在这样的平面图，则由，有而由；由；为整数，故，于是与(1)矛盾。4．证明每个比赛图中必有有向哈密顿路。（用数学归纳法证明）证：设

7、是个顶点的比赛图。施归纳于当时,结论显然成立。第7页（共7页）试题：班号：姓名：假设当时结论成立，往证对个顶点的比赛图也成立。从中去掉一个顶点，则得到一个具有个顶点的比赛图。由归纳假设有哈密顿路。在中，若或为的弧，则结论成立。今设及为的弧，由于比赛图，所以与之间有且仅有一条弧，于是必有一个最大i使为弧，从而为的弧。于是，为的哈密顿路。由归纳法原理知对任何本题结论成立。第7页（共7页）