答案08秋季集合论与图论试题A.docVIP

本试卷满分90分 （计算机科学与技术学院07级） 一、填空（本题满分10分，每小题各1分） 1.设是集合，，则等于什么？ （ ） 2．设X为集合，为X上的偏序关系，计算等于什么？ （ ） 3．把置换分解成循环置换的乘积。 （（149）（2367）（58）） 4．什么是无穷集合？ （凡能与自身的一个真子集对等的集称为无穷集合是一棵树，，则个顶点的树至多有多少个割点？ （-2 ） 6．设是一个有个顶点条弧的有向图，若是连通的，则至少是多大？（ -1 ） 7．设，则以V为顶点集的无向图共有多少个？ （） 8．设，则以V为顶点集的有向图共有多少个？） 9．每个有3个支的不连通图，若每个顶点的度均大于或等于2，则该图至少有多少个圈？ （ 3 ） 10．设是一个正则二元树，个叶子，则有多少条弧？（2（-1）） 二、判断对错（本题满分10分，每小题各1分） 1.设是两个集合，则且不可能同时成立。 （ 错 ） 2．在集合上可以定义个二元运算。 （ 错 ） 3．设，若存在唯一一个映射，使得，则一定是可逆的。 （ 错 ） 4．设是一个集合，则上的自反和反自反的二元关系个数相同。 （ 对 ） 5.设为一个有限字母表，上所有字（包括空字）之集记为。则不是可数集。 （ 错 ） 6.设是一个图，若，则中必有圈。 （ 对连通图，则至多有个生成树。 （ 对，是正则图且顶点连通度为1，则。（ 对个区域，每两个区域都相邻，则最大为5。（ 错 ） 10.有向图的每一条弧必在某个强支中。 （ 错 ） 三、证明下列各题(本题满分18分，每小题各6分) 1．设是三个任意的集合，则 （1）证明：；（2） 举例说明。 证：(1) 证明：，有，即但， 从而，于是，即。 (2) 若，则。 2．设是三个任意的集合，证明：。 证明：设 ，则，，从而,,。 于是，,因此，即 。 反之，设，有，，从而， ，，故且。于是， 即。 因此，。 3．设是个任意集合，：，若，则。因而且，；若，则，同理可得。。 ，故＝，有。若，则，；若，则。。＝。 ，回答下列问题：（6分） （1）是否是偶图？ （不是 ） （2）是否是欧拉图？ （不是 ） （3）是否是平面图？ （不是 ） （4）是否是哈密顿图？ （不是 ） （5）的色数为多少？ （ 3 ） 图1 2．设G是如图2所示的有向图，则（8分） （1）写出G的邻接矩阵。 （2）求顶点到间长为10的有向通道的条数的方法是什么？ （不必算出具体的数） （3）写出G的可达矩阵。 （4）画出对应于表达式（A＋B*C）/（A-C）的二元树表示。 解：（1）；（2）元素的值；（3） （4） 五、证明下列各题(本题满分18分, 每小题各6分) 1．设。若是单射，则与哪个是单射？请证明之。 解：是单射。 因为是单射，所以，若，则。 因此，，故是单射。 2．设。“”是上如下的二元关系：， 当且仅当。 则(1) 证明：是等价关系；(2)求等价类数。 证：(1)等价关系显然； (2)等价类数为：。 3．令利用康托对角线法证明S是不可数集。 证:假设从N到{0, 1}的所有映射之集可数，则可排成无重复项的无穷序列。每个函数确定了一个0,1序列。构造序列，若；否则。该序列对应的函数，，不为任一个，矛盾。 六、证明下列各题（本题满分20分，每小题各5分） 1.设是一个恰有两个不邻接的奇度顶点和的无向图，证明： 连通连通。 证： 显然成立。 假设不连通，则恰有2个分支：。由题意不在一个分支上，于是含有的顶点的分支只有一个奇度数顶点与握手定理的推论矛盾。于是假设不成立，即是连通的。 2．证明：任意一棵非平凡树至少有两个树叶。 证明：设为一棵非平凡的无向树，中最长的路为。若端点和中至少有 一个不是树叶，不妨设不是树叶，即有，则除与上的顶点相邻外， 必存在与相邻，而不在上，否则将产生回路。于是仍为的一条比 更长的路，这与为最长的路矛盾。故必为树叶。 同理，也是树叶。 3．证明：若每个顶点的度数大于或等于3，则不存在有7条边