《哈工大2005年秋季学期《集合论与图论》试题》由会员分享，可在线阅读，更多相关《哈工大2005年秋季学期《集合论与图论》试题（6页珍藏版）》请在金锄头文库上搜索。
1、1集合论与图论集合论与图论计算机学院计算机学院 05 年秋季年秋季一、一、解答下列问题，要求只给出答案（每题解答下列问题，要求只给出答案（每题 2 2 分，共分，共 1616 分）分）1.设为集合，试求一个集合，合得。AB、XA XB （ ）A B2.设，试求从到的满射的个数。1,2,3,4A 1,2B AB（）422143.设，试求上反自反二无关系的个数。1,2,10A LA（）290 22nn4.设，。试求以为顶点集具有条边的无向12,pAu uuL112qp pV图的个数。 （） 2/ ) 1(ppq5.设是一个有个顶点的正则二元树，试求下的叶子数，其中是奇数。TPP（1 2P）6.正整
2、数和为什么值时为欧拉图？mn,Km n（）mn和为偶数7.设为无向图，。如果是边通图，那么至少,GV E,VP EPGG有几个生成树？ （）3个8. 具有个顶点条边的平面连通图中，和应满足什么样的关系式？pqpq()36qp二、以下各题要求只给出答案（每题二、以下各题要求只给出答案（每题 2 2 分，共分，共 1414 分）分）.设，试求的传递闭包。 , , ,Xa b c dRa bb cc aR（ ,a ab bc ca bb cc aa cb ac b，）22.将置换（）分解为循环置换的乘积，然后分123456789 791652348解成对换的乘积。 17329846517 13292
3、82426=3.设 0000010110100000010000000A 123451 10000 2 10110 3 10100 4 10110 5 00001 如果是某有向图的邻接矩阵，那么画出这个有向图并写出它的可达矩阵。A4.设。字母表上所有字符串之集记为， 0,1 , , , , ,BEa b cx y zLB*B字母表上所有字符串之集记为。试求和的基数有什么关系。 E*E*B*E （相等）5.集合上可以定义多少个不相同的等价关系？ 1,2,3X （5 个）6.画出偏序集的哈斯图。1,2,32,7.求下图的顶点连通度和边连通度。（3,3x）三、三、1.设为任意集合，试证。,A BC和
4、 ABCA BA CUU设，则且，或且从而 证, x yABCUxAyBxAyC3或因此，, x yAB, x yA C( , )()()x yA BA CU即。 ABCA BA CUU反之，设，则或。如果 , x yA BA CU, x yA B, x yA C，则，从而，故；如果, x yA BxAyByBCU, x yABCU，则且从而，故。因此，, x yA CxAyCyBCU, x yABCU。所以，。 A BA CAB CU ABCA BA CUU2.设。如果是满射，试证是满射。:,:fXY g YZgfog因是满射，所以。令， 证gfo xXg f x ，使得 yf x则。因此，
5、是一个满射。 yYg yg f x 且g四、1.设，在上定义二元关系：1,2,3X 2 , 1y:XYf fXYXY，当且仅当。则,Xf gYfg 123123fffggg（1）证明是等价关系。 （2）求等价类的个数。（1），故是自反的。 证 123123ffffffQ（2）若，则，即gf )3()2() 1 ()3(2() 1 (gggfff，故。是对称的。)3(2() 1 ()3()2() 1 (fffggggf（3）设旦，则，从而，fggh3311( )( )iiig ih3i =1f 33 f ih i i =1i =1故，是传递的。fh因为或 4 或 5 或 6 且每种情况均存在这样
6、的映射，故 3 ,3XfYf i i =1有四个等价类。 2.设为上的二元关系，试证：是传递的当且仅当。RXRR RRo设是传递的，则，有使得， 证RRRzxo),(yX, x yR4。由的传递性知，故。反之，设，往证Rzy),(RRzx),(R RRoR RRo是传递的。为此，设，则由合成的定义有。再由RRzyyx),(),(RRzxo),(得。因此，是传递的。R RRoRzx),(R五、 1.设为可数集，利用康托对角线法证明是不可数集。A2A因为，所以只须证明不可数即可。 证 2 :0,1ACh Af fA Ch A，0，1 的无穷序列。若可数，则的元素可排 fCh A f可表为 Ch A
7、 Ch A列成无重复项的无穷序列。每个可表成 0，1 的无穷序列123,fff Lif。用对角线法构造一个 0，1 序列：，则；123,iiifffL123,g gg L110f若11g 则。一般地，若，则；如果，则，111f若10g 0iif 1ig 1iif 0ig ，则确定的函数，但，矛盾。所1,2,3,i L12,g g L gCh A,1,2,igf iL以，不可数。2A2.设。试证:,fXY CDY、 111fC DfCfD 证 11111111CCCfC DfCDfCfDfCfDfCfDIII六、一个一维立体是这样的无向图：顶点集为长为的所有 0，1 字KKQK符串之集，两个顶点
8、邻接当且仅当相应的两个字符串仅有一个相应位不同，其 他各位均相同。1. 有多少个顶点? ( )KQ2.证明是正则图。 ( )KQK 3.证明是偶图。 ( )KQ4.证明是条边。 ( )KQ12KK5. 是否为哈密顿图？ ( )3Q（1）有个顶点。解KQ2K（2）按中边的定义知每个顶点的度为，所以是正则图；KQKKQK （4）由（1）和（2）知，故边数22KKqg12KqKg5（3）根据中边的定义知每条边的两个端点名中 1 的个数的奇偶性不同。KQ于是，顶点名为偶数个 1 的那些顶点互相之间无边，其余顶点间也无边。所以，为偶图。KQ（5）的图解为下：3Q七、1.设是一个图。如果是一个正则图且每个
9、回路圈的,GV E, p qGK 长度至少为 4，试证：2pK因为中无三角形且为正则图，所以。 证GGK 2 22222pKpqpg因此，。2pK2.设是一个平面图，试证的补图不是平面图。证平G =（V，E）11pVGcG面图中边数满足。边数，若要，qq3p-6cG11362p ppcq（）（）36cgp则要它大于13240p2p（p-1）-12p+240，p，2 213137324224p（），1373736.510.77222p 故当时，不是平面图。11p 36cqpcG八、1.用数学归纳法证明每个比赛图中必有有向哈密顿路。 证设是个顶点的比赛图。施归纳于当时结论显然成立。假Dpp：p=1
10、，2 设当时结论成立，往证对个顶点的比赛图也成立。从中去掉一个p2p+1DD 顶点，则得到一个具有个顶点的比赛图。由归纳假设有哈密顿路upD -uD -u。在中，如或为的弧，则结论成立。今设及为L12pu，u，uD1uupu uD1u upuu的弧。由于比赛图，所以与之间有且仅有一条弧，于是DDukuL（k=2，p-1）必有一个最大 i 使为弧，从而为的弧。于是， 为iu ui +1uuDLL1ii +1puu uuu是哈密顿图，例如 000，010，011，001，011，111，110，100 ，000 为一个哈密顿图。6的哈密顿路。由归纳法原理知对任何本题结论成立。证毕Dp 2.列出无向树的特征性质（至少 5 个） （1）是树当且仅当是连通的且无圈。GG （2）的任两不同顶点间仅有一条路。G （3）是连通的且边数等于顶点数减 1。Gqp （4）中无圈且，其中同（3）中所言。Gq=p-1p，q （5）中无圈且任两不相邻接顶点间加一条边得到一个有唯一圈的图。G （6）是极小连通图。 G
