集合论、图论重要习题100

例：

1、设A,B是两个集合,B≠￠,试证:若A×B=B×B, 则A=B。

2、设A,B,C,D是任意四个集合，证明： （A∩B)×(C∩D)=(A×C)∩(B×D)

3、某班30名学生中学英语有7人，学日语有5人，这两科都选有3人，问两科都不选的有多少人？

(|AC∩BC|+|A∪B|=30, |AC∩BC|=21人)

4、令N={1,2,3,…}，S:N→N，则

(1)?n?N,S(n)=n+1,Ｓ称为自然数集N上的后继函数。

(2)S(1)=1,?n?N,S(n)=n-1,n≥2,Ｓ称为自然数集N 上的前仆函数。

5、设f:N×N ?N,f((x,y))=xy。则 （1）说明f是否是单射、满射或双射？ （2）求f(N×{1}),f-1({0})。

(1,4)≠(2,2),f((1,4))=f((2,2))=4；

?y?N,f((1,y))=1·y=y,任一元都有原象； [f不是单射,f是满射]

f(N×{1})={n·1|n ?N}=N；

f-1({0})={(x,y)|xy=0}={N×{0}}?{{0}×N}。

6、设R、I、N是实数、整数、自然数集合，下面定义映射f1,f2,f3,f4,f5,f6，试确定它们的性质。 （0 ?N） （1）f1:R?R,f1(x)=2x； （2）f2:I?N,f2(x)=|x|；

f1单射，不是满射。f2不是单射，满射。 （3）f3:N?N,f3(n)=n(mod3)； （4）f4:N?N×N,f4(n)=(n,n+1)；

f3不是单射，不是满射；f4单射，不是满射。 （5）f5:R?R,f5(x)=x+2；

（6）f6:R?R,f6(x)=x2,x≥0,f6(x)=-2,x<0；

1

f5是双射(单射,满射)；f6不是单射,不是满射。

7、证明：在52个正整数中，必有两个整数，使得这两个整数之和或差能被100整除。

8、已知m个整数a1，a2，…，am，试证：存在两个整数k,l,0?k?i?m，使得ak+1+ak+2+…+al能被m整除。

9、设N={1,2,3,…},试构造两个映射f,g:N?N，使得fg=IN，但gf?IN。

10、设N={1,2,3,…},试构造两个映射f,g:N?N，使得gf=IN，但fg?IN。

11、设f:X?Y，证明：

(1)f是单射??F?2X，f–1(f(F))=F； (2)f是满射??E?2Y，f(f–1(E))=E。

12、设f:X?Y，则

(1)若存在唯一的一个映射g:Y?X,使得gf=IX,则f是可逆的吗？ (2)若存在唯一的一个映射g:Y?X,使得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},n?m,若f:X?Y，求X到Y的满射的个数。

14、设X是一个集合，|X|＝n，求：

(7) X上既不是自反的也不是反自反的关系有多少？

2

(9) X上自反的或对称的关系有多少？

(12)X上既不是对称的也不是反对称的关系有多少？

15、设 A={1,2,3}，R是A的幂集2A上的二元关系且 R={(a,b)|a∩b≠￠}，则R不满足下列哪些性质？为什么？[aRb ?a∩b≠￠] (1) 自反性 (2) 反自反性 (3) 对称性 (4) 反对称性 (5) 传递性

16、设R是复数集合C上的一个二元关系且满足

xRy?x-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上的一个自反的和传递的关系；

T是A上的一个关系，使得(a,b)∈T?(a,b)∈R且 (b,a)∈R。证明：T是A上的等价关系。

20、设R是A上的二元关系，S={(a,b)|?c∈A,使得(a,c)∈R且(c,b)∈R}。证明：若R是等价关系，则S也是等价关系。 说明：本题可以证明R＝S。

21、设{A1,A2,…,An}是集合A的划分，若Ai∩B≠φ，1≤i≤n，证明：{A1∩B,A2∩B,…,An∩B}是集合A∩B的划分。

3

22、设S={1,2,3,4},并设A＝S×S,在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,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度顶点，其余均是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是顶点p≥11的平面图，证明：G的补图Gc是非平面图。

(设G是顶点p≥11的图，证明：G与G的补图Gc至少有一个是非平面图。)

33、设G是边数q<30的平面图,证明:G中存在顶点v， 使得degv≤4。

34、设G是(p,q)平面连通图，f个面，证明： （1）若p≥3，则f≤2p-4；

（2）若δ(G)=4，则G中至少有6个顶点的度数 小于等于5。

证: (1) p-q+f=2,q≤3p-6,从而有:f≤2p-4。

(2) 假设G中至多含有5个顶点的度数≤5，又δ(G)=4,所以5×4+6×(p-5)≤2q ，得q≥3p-5。

而q≤3p-6，从而有：3p-5≤3p-6，矛盾。

故假设不成立，因此G中至少有6个顶点的度数≤5

35、把平面分成n个区域，每两个区域都相邻,问n最大为多少？

证：在每个区域放一个顶点，当两区域相邻时，就在相邻的两个顶点间连一条边，如此构造了一个平面图且是完全平面图，而最大的完全平面图为K４，所以n最大为4。

36、证明:当每个顶点的度数大于等于3时，不存在有7条边的简单连通平面图。 证：设G=(n，m)为简单连通平面图，有r个面。若m=7，由欧拉公式知n+r=m+2=9

5

(1) 而每个面至少由3条边围成，有3r≤2m，则r≤2m/3，因r是整数,故r≤４。 又对任意得顶点v∈V，degv≥3，有3n≤2m，故n≤2m/3，因为n是整数， 故n≤４。所以n+r≤４＋４=８与（１）矛盾，所以结论正确。

37、设G是一个没有三角形的平面图，则

（1）证明：G中存在一个顶点v，使得degv≤3； （2）证明：G是4-可着色的。

38、设树T中有2n个度为1的顶点,有3n个度为2的顶点,有n个度为3的顶点,则这棵树T有几个顶点和几条边？

39、设T是一棵树且△(T)≥k,证明:T中至少有k个度为1的顶点。

40、设G是一个(p,q)图, 若q≥p,证明G中必有圈。 41、证明:任一非平凡树最长路的两个端点都是树叶。(任一非平凡树中至少有两个度为1的顶点。)

42、证明:恰有两个顶点度数为1的树必为一条通路。

43、设T=(V,A)是一个有根树,其每个顶点的出度不是0就是2。若T有n0个叶子，试求T的弧的条数。

44、设T=(V,A)是一个正则二元树,若T有n0个叶子，试求的弧的条数。

45、设T是有n0个叶子的正则二元树，n2个出度为2的顶点，证明：n0=n2+1。

6

46、设T是有n0个叶子的二元树，出度为2的顶点为n2，证明：n0=n2+1。

47、设T是一个有p个顶点的正则二元树，求T的叶子数，其中p奇数。

48、证明：任一棵正则(满)二元树必有奇数个顶点。

49、菱形12面体的表面上有无哈密顿回路？

50、设G=(V,E)是连通图且顶点数为p,最小度数为δ，若p>2δ,则G中有一长至少为2δ的路。

51、设G=(V,E)是p(p>3)个顶点的简单无向图,设G中最长路L的长度为l(l≥2)，起点与终点分别为u,v，而且degu+degv≥p。证明：G中必有与L不完全相同但长度也为L的路。

52、已知a,b,c,d,e,f,g7个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？

53、设G为p个顶点的简单无向图。则

(1) 若G的边数q= (p-1)·(p-2)/2+2，证明G为哈密顿图。

(2) 若G的边数q= (p-1)·(p-2)/2+1，则G是否一定为哈密顿图？

7

54、已知9个人v1,v2,…,v9，其中v1和两个人握过手，v2,v3,v4,v5各和3个人握过手，v6和4个人握过手，v7,v8各和5个人握过手，v9和6个人握过手。证明:这9个人中一定可以找出3个人互相握过手。

55、(1)一棵无向树有ni个度数为i的顶点,i=1,2,…,k。n2,n3,….nk均为已知数，问n1应为多少？

(2)在(1)中，若nr(3≤r≤k)未知，nj(j≠r)均为已知数，问nr应为多少？

56、设G是平面连通图，顶点为p面数f，证明:

(1)若p≥3，则f≤2p-4。(2)若δ(G)=4,则G中至少有6个顶点的度数≤5。 57、设d=(d1,d2,…,dn),其中di为非负整数，i=1,2,…,n。若存在n个顶点的(简单)无向图,使得顶点vi的度为di，则称d是可图解的。下面给出的各序列中哪些是可图解的？哪些不是，为什么？ （1）（1,1,1,2,3）； （6）（1,3,3,3）； （2）（0,1,1,2,3,3）；（7）（2,3,3,4,5,6）； （3）（3,3,3,3）； （8）（1,3,3,4,5,6,6）； （4）（2,3,3,4,4,5）；（9）（2,2,4）； （5）（2,3,4,4,5）； （10）(1,2,2,3,4,5）。

58、设G是有个p顶点，q条边的无向图，各顶点的度数均为3。则 (1)若q=3p-6,证明:G在同构意义下唯一，并求p,q。 (2)若p=6，证明:G在同构的意义下不唯一。

59、已知p阶(简单)无向图中有q条边，各顶点的度数 均为3，又2p=q+3，试画出满足条件的所有不同 构的G。

60、证明：在一个连通图中，两条最长的路有一个公共的顶点。

8

61、若G是一个恰有两个奇度顶点u和v的无向图，则 G连通?G+uv连通。

62、证明：若无向图G是不连通的，则G的补图GC是连通的。（逆命题不成立）

63、某工厂生产由6种不同颜色的纱织成的双色布。双色布中，每一种颜色至少和其他3种颜色搭配。证明:可以挑出3种不同的双色布,它们含有所有6种颜色。

64、设G是一个有p(p≥3)个顶点的连通图。u和v是G的两个不邻接的顶点,并且degu+degv≥p。证明：G是哈密顿图?G+uv是哈密顿图。

65、证明：完全图K9中至少存在彼此无公共边的两条哈密顿圈和一条哈密顿路？

66、把平面分成p个区域，每两个区域都相邻，问p最大为多少？

67、证明：不存在具有5个面，每两个面都共享一条公共边的平面图G。

68、设T为任一棵正则二元树，q为边数，n0为树叶数，证明：q=2n0-2。其中n0≥2。

69、设图G中有9个顶点，每个顶点的度不是5就是6。证明:G中至少有5个6度顶点或至少有6个5度顶点。

70、将无向完全图K6的边随意地涂上红色或绿色,证明:无论何种涂法,总有红色的K3

9

或绿色K3。

71、给无向完全图Kp(p≥7)的各边随意地涂上红色或绿色，若已知从某点v0引出的p-1条边中至少有6条边涂红色，则Kp存在红色的K4或绿色的K3。

72、有17位学者，每2位讨论3篇论文中的一篇且仅一篇，证明：至少有3位学者，他们相互讨论的是同一篇论文。

p

d i ?73、设d1,d2,…,dp是p个正整数,p≥2,且 2 p ? 2 。

证明:存在一棵顶点度数为d1,d2,…,dp的树。 i?1

74、判断下面命题是否正确，并说明理由。

任意平面图G的对偶图G*的对偶图G**与G同构。

75、设G*是平面图G的对偶图，证明：p*=f，q*=q， f*=p-k+1。其中k(k≥1)为G的连通分支数。

76、证明：若G是自对偶的平面图，则q=2p-2。其中p和q是G的边与顶点数。

定义、定理及推论：

1、对于“5”这个数。世界上有“5”这个事物吗？没有。有的只是具体的5个事物，如5个人，5只笔，5张桌子等等，而这个“5”无非就是一个符号，它表明具有5个事物所形成的集合的共性。它们的共性就是它们相互对等，即它们的元素之间可以建立起一一对应。于是， “5”这个符号就是赋给每个含有五个元素的集合的一个记号，即若与含有五个元素的集对等，则都赋以相同的记号“5”。实际上，这就是“5”的本质。

2、设X，Y，Z为三个非空集合。一个从X×Y到Z的映射称为X与Y到Z的一个二

? 10

元运算或二元代数运算。

当X＝Y＝Z时，即若?:?????，则称?为X上的二元运算。

3、设X，Y是两个非空集合，一个从X到Y的映射称为X到Y的一个一元运算。 若X=Y，则?称为X上的一元运算。也称X的一个变换。

4、设A1,A2,…,An,D为非空集合，一个从A1×A2×…×An到D的映射?称为A1,A2,…,An到D的一个n元（代数）运算。

若A1=A2=…=An=D=A，则称?为A上的n元运算。 说明：1. 最常用的是一元运算和二元运算。

5、七桥问题就变成了如下的一笔画问题：

能否笔不离开纸，把图2的“图”一笔画成，使每条线画一次且只画一次，最后笔又回到出发点？

欧拉证明了这个图不能一笔画成。 6、若G的图解已画在平(曲)面S上，而且任何两条边均不相交(除可能在端点相交外)，则图G称为嵌入平(曲)面S内。 已嵌入平面S内的图称为平面图。

若一个图可以嵌入平面，则称此图是可平面的

说明：可平面图：能画在平面上 ，但还没有画；平面图：已经画在平面上了。以后这两个概念不加区分。

7、任一非平凡树中至少有两个度为1的顶点(两片叶子)。

8、每个非平凡的连通图至少有两个顶点不是割点。

9、设G是一个(p,q)图，则

(1) 若q

11

10、若G的图解已画在平面S上，而且任何两条边均不相交(除可能在端点相交外)，则图G称为被嵌入平面S内。

已嵌入平面S内的图称为平面图。

若一个图可以嵌入平面，则称此图是可平面的 说明：可平面图：能画在平面上 ，但还没有画；

平面图：已经画在平面上了。以后这两个概念不加区分。 例如：图K4是可平面的， 图K5没有平面嵌入法；

K5画不出来，并不等于就是非平面图，必须证明。实际上，K5是典型的不可平面图，还有K3,3。

11、平面图G把平面分成了若干个区域，这些区域都是连通的，称之为G的面，其中无界的那个连通区域称为G的外部面，其余的单连通区域称为G的内部面。 说明：

(1) 平面图的每个内部面都是G的某个圈围成的单连通区域；

(2) 一个平面图可以没有内部面，但必有外部面，而且外部面唯一； 例如：树作为平面图就没有内部面。

(3) K4有4个面，f4是外部面，f1，f2，f3都是内部面。

12、(欧拉公式)设G是(p,q)平面连通图，有f个面，则p-q+f=2。 证：用数学归纳法证明，施归纳于面f的个数：

注意：定理中的连通性是必要的。若G不连通，则定理不成立。但却有下面的结论。 推论:设G是一个具有f个面、k个分支的(p,q)平面图，则p-q+f=k+1

13、每个比赛图必有一条有向哈密顿路(即生成有向路)。 [用数学归纳法证明每个比赛图中必有有向哈密顿路] 证：设D是p个顶点的比赛图。施归纳于p: 当p=1,2时结论显然成立。

假设当有p(p≥2)时结论成立，往证对p+1个顶点的比赛图也成立。从中去掉一个顶点u，则得到一个具有p个顶点的比赛图D-u。由归纳假设D-u有哈密顿路u1,u2,…,up。

在D中，若(u,u1)∈A或(up,u)∈A，则结论成立。

今设(u1,u)∈A及(u,up)∈A，由于D是比赛图，所以u与uk(k=2,3,…,p-1)之间有且仅有一条弧，于是必有一个最大i使(ui,u)∈A且(u,ui+1)∈A。于是，u1u2…uiuui+1…up为D的一条哈密顿路。由归纳法原理知对任何p本题结论成立。

12

本文来源：https://www.bwwdw.com/article/eid.html