《集合论、图论重要习题100》由会员分享，可在线阅读，更多相关《集合论、图论重要习题100（3页珍藏版）》请在装配图网上搜索。
1、集合论、图论重要习题100 ; 例：1、设A,B是两个汇合,B,试证:假设AB=BB, 那么A=B。2、设A,B,C,D是任意四个汇合，证明：AB)(CD)=(AC)(BD)3、某班30名学生中学英语有7人，学日语有5人，这两科都选有3人，问两科都不选的有多少人？(|ACBC|+|AB|=30, |ACBC|=21人)4、令N=1,2,3,，S:NN，那么(1)nN,S(n)=n+1,称为自然数集N上的后继函数。(2)S(1)=1,nN,S(n)=n-1,n2,称为自然数集N上的前仆函数。5、设f:NN N,f(x,y)=xy。那么 1表明f是否是单射、满射或双射？ 2求f(N1),f-1(0
2、)。(1,4)(2,2),f(1,4)=f(2,2)=4； yN,f(1,y)=1y=y,任一元都有原象；f不是单射,f是满射 f(N1)=n1|n N=N； f-1(0)=(x,y)|xy=0=N00N。 6、设R、I、N是实数、整数、自然数汇合，下面定义映射f1,f2,f3,f4,f5,f6，试确定它们的性质。 0 N 1f1:RR,f1(x)=2x； 2f2:IN,f2(x)=|x|； f1单射，不是满射。f2不是单射，满射。 3f3:NN,f3(n)=n(mod3)； 4f4:NNN,f4(n)=(n,n+1)； f3不是单射，不是满射；f4单射，不是满射。 5f5:RR,f5(x)=
3、x+2； 6f6:RR,f6(x)=x2,x0,f6(x)=-2,x1f5是双射(单射,满射)；f6不是单射,不是满射。7、证明：在52个正整数中，必有两个整数，使得这两个整数之和或差能被100整除。8、已知m个整数a1，a2，am，试证：存在两个整数k,l,0kim，使得ak+1+ak+2+al能被m整除。9、设N=1,2,3,试构造两个映射f,g:NN，使得fg=IN，但gfIN。10、设N=1,2,3,试构造两个映射f,g:NN，使得gf=IN，但fgIN。11、设f:XY，证明：(1)f是单射F2X，f1(f(F)=F； (2)f是满射E2Y，f(f1(E)=E。12、设f:XY，那么
4、(1)假设存在唯一的一个映射g:YX,使得gf=IX,那么f是可逆的吗？ (2)假设存在唯一的一个映射g:YX,使得fg=IY,那么f是可逆的吗？13、(1)设X=1,2,3,Y=a,b,求X到Y满射的个数; (2)设X=1,2,3,4,5,Y=a,b,求X到Y的满射的个数; (3)设X=1,2,n,Y=a,b，求X到Y的满射的个数;(4)设X=1,2,n,Y=y1,y2,ym,nm,假设f:XY，求X到Y的满射的个数。14、设X是一个汇合，|X|n，求：(7) X上既不是自反的也不是反自反的关系有多少？ 2(9) X上自反的或对称的关系有多少？(12)X上既不是对称的也不是反对称的关系有多少
5、？15、设 A=1,2,3，R是A的幂集2A上的二元关系且R=(a,b)|ab，那么R不满足以下哪些性质？为什么？aRb ab(1) 自反性 (2) 反自反性 (3) 对称性(4) 反对称性 (5) 传递性16、设R是复数汇合C上的一个二元关系且满足xRyx-y=a+bi，a,b为非负整数，试确定R的性质。17、设R为X上的二元关系，显然假设R，那么R是反自反的、对称和传递的；但假设R且R是反自反的和对称的，那么R不是传递的。本题可变形为：但假设R且R是反自反的和传递的,那么R是反对称的。18、设R是汇合A上的反对称关系，那么t(R)一定是反对称的吗？19、设R是汇合A上的一个自反的和传递的关
6、系； T是A上的一个关系，使得(a,b)T(a,b)R且 (b,a)R。证明：T是A上的等价关系。 20、设R是A上的二元关系，S=(a,b)|cA,使得(a,c)R且(c,b)R。证明：假设R是等价关系，那么S也是等价关系。表明：此题可以证明RS。21、设A1,A2,An是汇合A的划分，假设AiB，1in，证明：A1B,A2B,AnB是汇合AB的划分。 322、设S=1,2,3,4,并设ASS,在A上定义关系R为:(a,b)R(c,d)a+b=c+d。证明:(1) R是A上的等价关系；(2) 计算A/R。23、设汇合A=a,b,c,d,e上关系R定义如下： R=(a,a),(a,b),(a,
7、c),(a,d),(a,e),(b,b),(b,c),(b,e), (c,c),(c,e),(d,d),(d,e),(e,e)。 1.写出R的关系矩阵； 2.验证(A,R)是偏序集; 3.画出Hasse图;4.假设A上的关系如下： R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e), (c,c), (c,d),(c,e),(d,d),(d,e),(e,e)，那么有如何？24、用对角线办法证明：假设A是可数集，那么2A是不可数集。25、用对角线办法证明：所有0,1的无穷序列所构成的汇合是不可数集。26、设T是一棵树,T有3个度为3顶点,1个2度顶点
8、，其余均是1度顶点。那么 1求T有几个1度顶点？2画出满足上述要求的不同构的两棵树。27、设T是一棵树且(T)k，证明T中至少有k个度为1顶点。28、设G是一棵树且(G)k，证明：G中至少有k个度为1的顶点。 4 29、一棵树T有n2个度为2的顶点，n3个度为3的顶点，nk个度为k的顶点，那么T有多少个度为1的顶点？30、如下图是彼德森图，回答下列问题：1图是否是自补图？2图是否是偶图？3图是否是欧拉图？4图是否是哈密顿图？ 5图是否是平面图？6图的色数是多少？31、证明：假设每个顶点的度数大于等于3时，那么不存在有7条边的平面连通图。 (等价命题：证明：不存在7条棱的凸多面体)32、设G是顶
9、点p11的平面图，证明：G的补图Gc是非平面图。(设G是顶点p11的图，证明：G与G的补图Gc至少有一个是非平面图。)33、设G是边数q34、设G是(p,q)平面连通图，f个面，证明：1假设p3，那么f2p-4；2假设(G)=4，那么G中至少有6个顶点的度数 小于等于5。证: (1) p-q+f=2,q3p-6,从而有:f2p-4。(2) 若G中至多含有5个顶点的度数5，又(G)=4,所以54+6(p-5)2q ，得q3p-5。而q3p-6，从而有：3p-53p-6，矛盾。故若不成立，因此G中至少有6个顶点的度数535、把平面分成n个区域，每两个区域都相邻,问n最大为多少？证：在每个区域放一个顶点，当两区域相邻时，就在相邻的两个顶点间连一条边，如此构造了一个平面图且是完全平面图，而最大的完全平面图为K，所以n最大为4。36、证明:当每个顶点的度数大于等于3时，不存在有7条边的简单连通平面图。 证：设G=(n，m)为简单连通平面图，有r个面。假设m=7，由欧拉公式知n+r=m+2=9 5
集合论、图论重要习题100
