集合论与图论2009f (2)

《集合论与图论2009f (2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本试卷满分90分-参考答案（计算机科学与技术学院08级）一、填空（本题满分20分，每空各1分）1．设为集合，若，则等于什么？（）2．设，则与有何关系？()3．给定集合，找出上的等价的关系，此关系能产生划分。（）4．设分别表示实数，整数，自然数集（包括0），定义映射，试确定它们的性质（单射、满射、双射）。（1）；（是单射）（2）；（是满射）（3）。（是双射）5．在集合上定义的整除关系“

2、”是上的偏序关系，则极大元有几个？　　　　　　　　　　　　　　　（6个）6．设是一个集合，＝n，求上对称的二元关系有多少？（）7．设是集合上的一个二元关系，则（1）是传递的充分必要条件是什么？（）（

3、2）是对称的充分必要条件是什么？（）8．设是有个顶点的正则偶图，则至少是多少？（）9．有个药箱，若每两个药箱里有一种相同的药，而每种药恰好放在两个药箱中，则（1）每个药箱里有多少种药？　　　　　（　　）（2）个药箱里共有多少种药？　　　　（　）10.设是无向图，有12条边，6个3度顶点，其余顶点的度数均小于3，则至少有多少个顶点？（　9）11．设是有个顶点的无向树且的最大度为，则（1）的范围为多少？（）（2）若，则中最长路的长度为多少？（）12．设是有8个顶点的极大平面图，则的面数为多少？（12）13．设是图，若，则的顶点连通度为多少？（0）14．设为任一棵正则二元树，为边数，为

4、树叶数，则等于什么？（）15．设为正整数，则为何值时为欧拉图？（为偶数）二、简答下列各题（本题满分10分）1．设是三个任意集合，且，则与应满足什么关系？说明理由。（3分）解：。两边同并上A有：，；即。2．设为上的二元关系，若且是反自反的和传递的，则是反对称的吗？说明理由。（3分）证：若不是反对称的，则由的传递性有：，与是反自反的矛盾。于是是反对称的二元关系。3．设，试构造两个映射和g：，使得，但。（4分）解：但，故f是满射，但f不是单射。于是令：，，则但。三、简答下列各题（本题满分15分）1．何谓强连通有向图？何谓有向图的强支？（2分）解：设D＝（V,A）是有向图，若，与v互达，

5、则称D是强连通的有向图；有向图D的极大强连通子图称为D的一个强支。2．至少要删除多少条边，才能使不连通且其中有一个连通分支恰有个顶点？（3分）证：要使删除边后的图边数最多，则删除的边最少。则至少应该删除的边数为：。3．具有奇数顶点的偶图是否是哈密顿图？说明理由。（3分）证：设是一个具有奇数顶点的偶图，则的顶点集有一个二划分，即且有。不妨设，则有。由哈密顿图的必要条件可知：不是哈密顿图。4．设是一个有向图，如图所示。写出有向图邻接矩阵、可达矩阵以及顶点2到4长度为2的有向通道的条数。（3分）解：(1)；(2)；0。5．设是一个图，每个顶点的度为3。则（4分）（1）若，则在同构意义下

6、是否唯一？（2）若，则在同构的意义下是否唯一？说明理由。解：（1），唯一。（2），，不唯一。如图所示。四、证明下列各题（本题满分25分）1．设都是非空集合，若，证明：。（5分）证：因为非空，所以，有，即。因此。同理。由集合相等的定义有：。2．设，证明：是满射。（5分）证明：，则，使得，于是，，所以。反过来，，因为是满射，故必有，使得。又，故，所以。因此。假设不是满射，则，使得，。于是令，有，由题意得，矛盾。故一定为满射。3．证明：全体有理数之集是可数集。（5分）证：因为。显然，。因此只须证明是可数集即可。我们知道，每个正有理数均可写成p/q的形式，其中p与q为自然数。于是，，令，

7、则是可数集，并且。由定理可知，是可数集。因此，Q是可数集。4．设是集合上的等价关系，且，则（10分）（1）证明：是上的等价关系；（2）证明：。证：（1）由是等价关系得到自反的；又由，故是对称的；而。从而是传递的，因此，是等价关系。（2）因为是上的等价关系，所以是上的传递关系；又，有或。若，因为，所以；若，因为，所以。两种情况下都有，故。对于上的任一等价关系且，有，，使得或。若，有；若，有。由的传递性，有，故。因此是包含的最小传递关系。从而。五、证明下列各题（本题满分20分，每小题各5分）1．证明：恰有两个顶点度数为1的树必为一条通路。证：设是一棵具有两个顶点度数为1的树，则且。又

8、除两个顶点度数为1外，其他顶点度均大于等于2，故，即。因此个分支点的度数都恰为2，即为一条通路。2.设是一个图，，证明：若，则中必有圈。证：（1）设是连通的，若无圈，则是树，因此与矛盾。故中必有圈。（2）设不连通，则中有个分支，。若中无圈，则的各个分支中也无圈，于是各个分支都是树，所以有：，。相加得：与矛盾，故G中必有圈。综上所述，图中必有圈。3．设是一个图，且，证明：是连通图。证：用反证法。假设图是不连通的，则图至少存在两个连通分支，一个支为是图，另外一些支构成的子图为是。而的