哈工大2005年秋季学期《集合论与图论》试题.doc

集合论与图论计算机学院05年秋季一、 解答下列问题，要求只给出答案（每题2分，共16分）1.设为集合，试求一个集合，合得。（）2.设，试求从到的满射的个数。（）3.设，试求上反自反二无关系的个数。（）4.设，。试求以为顶点集具有条边的无向图的个数。（）5.设是一个有个顶点的正则二元树，试求下的叶子数，其中是奇数。（）6.正整数和为什么值时为欧拉图？（）7.设为无向图，。如果是边通图，那么至少有几个生成树？（）8. 具有个顶点条边的平面连通图中，和应满足什么样的关系式？()二、以下各题要求只给出答案（每题2分，共14分）.设，试求的传递闭包。（）2.将置换（）分解为循环置换的乘积，然后分解成对换的乘积。3.设 如果是某有向图的邻接矩阵，那么画出这个有向图并写出它的可达矩阵。4.设。字母表上所有字符串之集记为，字母表上所有字符串之集记为。试求和的基数有什么关系。（相等）5.集合上可以定义多少个不相同的等价关系？（5个）6.画出偏序集的哈斯图。7.求下图的顶点连通度和边连通度。（）三、1.设为任意集合，试证。设，则且，或且从而或因此，。反之，设，则或。如果，则，从而，故；如果，则且从而，故。因此，。所以，。2.设。如果是满射，试证是满射。因是满射，所以。令，则。因此，是一个满射。四、1.设，在上定义二元关系：，当且仅当。则（1）证明是等价关系。（2）求等价类的个数。（1），故是自反的。（2）若，则，即，故。是对称的。（3）设旦，则，从而，故，是传递的。因为或4或5或6且每种情况均存在这样的映射，故有四个等价类。2.设为上的二元关系，试证：是传递的当且仅当。设是传递的，则，有使得，。由的传递性知，故。反之，设，往证是传递的。为此，设，则由合成的定义有。再由得。因此，是传递的。五、1.设为可数集，利用康托对角线法证明是不可数集。因为，所以只须证明不可数即可。，0，1的无穷序列。若可数，则的元素可排列成无重复项的无穷序列。每个可表成0，1的无穷序列。用对角线法构造一个0，1序列：，则；则。一般地，若，则；如果，则，则确定的函数，但，矛盾。所以，不可数。2.设。试证六、一个一维立体是这样的无向图：顶点集为长为的所有0，1字符串之集，两个顶点邻接当且仅当相应的两个字符串仅有一个相应位不同，其他各位均相同。1. 有多少个顶点? ( )2.证明是正则图。( )3.证明是偶图。( )4.证明是条边。( )5. 是否为哈密顿图？( )（1）有个顶点。（2）按中边的定义知每个顶点的度为，所以是正则图；（4）由（1）和（2）知，故边数（3）根据中边的定义知每条边的两个端点名中1的个数的奇偶性不同。于是，顶点名为偶数个1的那些顶点互相之间无边，其余顶点间也无边。所以，为偶图。（5）的图解为下：是哈密顿图，例如000，010，011，001，011，111，110，100，000为一个哈密顿图。七、1.设是一个图。如果是一个正则图且每个回路圈的长度至少为4，试证：因为中无三角形且为正则图，所以。因此，。2.设是一个平面图，试证的补图不是平面图。证平面图中边数满足。边数，若要，则要它大于故当时，不是平面图。八、1.用数学归纳法证明每个比赛图中必有有向哈密顿路。证设是个顶点的比赛图。施归纳于当时结论显然成立。假设当时结论成立，往证对个顶点的比赛图也成立。从中去掉一个顶点，则得到一个具有个顶点的比赛图。由归纳假设有哈密顿路。在中，如或为的弧，则结论成立。今设及为的弧。由于比赛图，所以与之间有且仅有一条弧，于是必有一个最大i使为弧，从而为的弧。于是， 为的哈密顿路。由归纳法原理知对任何本题结论成立。证毕2.列出无向树的特征性质（至少5个）（1）是树当且仅当是连通的且无圈。（2）的任两不同顶点间仅有一