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