哈工大2006年秋季学期《集合论及图论》试题

《哈工大2006年秋季学期《集合论及图论》试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈工大2006年秋季学期《集合论与图论》试题本试题满分90，平时作业分满分10分。一、（10分，每小题1分）判断下列各命题真伪（真命题打“√”号，假命题打“×”号）：1．从{1，2，3}到{4，5}共有9个不同的映射。（）2．从{1，2，3}到{4，5}共有5个不同的满射。（）3．从{4，5}到{1，2，3}共3个不同的单射。（）4．集合{1，2，…，10}上共有2100个不同的二元关系。（）5．如果A为可数集，则2A也是可数集合。（）6．欧拉图中没有割点。（）7．有向图的每一条弧必在某个强支中。（）8．

2、P为正整数，Kp的顶点连通度为P－1。（）9．（P，P）连通图至少有2个生成树。（）10．每个有2个支的不连通图，若每个顶点的度均大于或等于2，则该图至少有2个圈。（）二、（20分，每小题2分）计算题。对每一小题给出计算结果：1．{1，2，…，n}上有多少个反自反且对称的二元关系？（）2．把置换分解成循环置换的乘积。（）3．计算下面两个图G1和G2的色数。（）G1：G2：（答：G1的色数为，G2的色数为）4．设X为集合，R为X上的偏序关系，计算等于什么。（）5．求下面的有向图D的邻接矩阵和可达矩阵。D=-

3、------------------：（）6．一个有向图D=(V，A)满足什么条件是V到V的一个映射的图？（）7．P个顶点的无向连通图G的邻接矩阵中至少有多少个1？（）8．设X为n个元素的集合，X上有多少个二元运算？（）9．9个学生，每个学生向其他学生中的3个学生各送一张贺年卡。确定能否使每个学生收到的卡均来自其送过卡的相同人？为什么？（）10．某次会议有100人参加，每人可以是诚实的，也可能是虚伪的。已经知道下面两项事实：（1）这100人中至少有一人是诚实的；（2）任两人中至少有一人是虚伪的。问这100

4、人中有多少人是诚实的？（）三、（12分，每小题6分）1．设A、B、C和D都为非空集合。证明：2．设X为有穷集合，，。证明：f和g都为一一对应且。举例说明，当X为无穷集时，上述结论不成立。四、（12分，每小题6分）1．证明：每个平面图，如果G是偶图，则，使得。2．设为具有P个顶点的二元树，T有个出度为2的顶点。求T的叶子数。五、（12分，每小题6分）1．下图是否是一个哈密顿图？证明你的结论。2．设为一个连通图，e为G的一条边。证明：e是G的桥当且仅当e在G的每个生成树中。六、（12分，每小题6分）1．设，，

5、求R+。2．给出等价关系、等价类的定义。等价关系与集合的划分之间有何联系？七、（12分，每小题6分）1．设。用对角线法证明是不可数集合。2．证明：平面图的欧拉公式。哈工大2006年科季学期《集合论与图论》试题参考答案一、1、5、6、7、9为假；4、8、10题为真。二、1.；2.(15)(278)(396)；3.3、2；4.R；5.邻接矩阵A，可达矩阵R6.，；7.；8.；9.否，因为不存在9（奇数）个顶点的3－正则图；10.1人诚实三、1.[证]设，则，且，于是，、、但或或。if，则，，故右边；if，则。

6、若，则右边。因此，左右。反之，设右。if，则，，，，，，左；if，则，，，故，且，左。2．[证]恒等映射Ix是一一对应，也是单射，也是满射。由，故f是单射，g是满射。又，故f和g均为一一对应，从而。令。定义如下：，；，。于是，，，。所以，但f与g均不是一一对应，。四、1.[证]如果结论不成立，那么，，从而。又偶图中无三角形，故每个面上至少4条边。于是，从而，矛盾。2.[证]设出度为1的顶点数为，则入度之和为，出度之和为，于是，从而。五、1.该图不是哈密顿图。如果是哈氏图，则有哈圈C。于是，边28在C上，否

7、则为C的边构成的圈，不可能；但28在C上，则23、89不在C上，从而43、39在C上。411不在C上，119在C上，9有三边在C上矛盾。或如下证明：去掉点2，4，6，9四个点，有5个分支，故不是哈氏图。2．否则G有一生成树不含边e，但不连通，矛盾。设边e在G的每个生成树中，则无生成树，从而不连通。六、1.2．X上二元关系如果是自反的，对称且传递的，则称为X上等价关系。，集合称的一个等价类。X上每个等价关系的所有等价类之集是X的一个划分，X的每个划分确定X上一个等价关系，其等价类之集为该划分。七、1.[证]

8、如果从N到{0,1}的所有映射之集可数，则可排成无重复项的无穷序列。每个函数确定了一个0,1序列。构造序列，if；否则。该序列对应的函数，，不为任一个，矛盾。2．[证]if，则为树，结论成立。if对时结论成立，则设G有f+1个面。从G中去掉一个内部面上一条边得G'。在G'中有，。五、2.的简单证明：if存在哈密顿圈，则(a)28不在C上，那么6、7、8、9、10、6是C上的圈，不可能；(b)28在C上，则，，，∴119、39、