集合论图论重要习题100文档格式.docx

集合论图论重要习题100文档格式.docx

《集合论图论重要习题100文档格式.docx》由会员分享，可在线阅读，更多相关《集合论图论重要习题100文档格式.docx（18页珍藏版）》请在冰点文库上搜索。

；

（2）f2:

I

N,f2（x）=|x|

f1射，不是射。

f2

不是射，射。

（3）f3:

N

N,f3（n）=n（mod3）

（4）f4:

N,f4（n）=（n,n+1）

f3不是射，不是射；

f4射，不是射。

（5）f5:

R,f5（x）=x+2

（6）f6:

R,f6（x）=x2,x

≥0,f6（x）=-2,x<

0；

1

f5是双射（射,射）；

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:

X

Y，明：

（1）f

是射

F2X

，f–1（f（F））=F

（2）f

E2Y

，f（f–1（E））=E

。

12、f:

XY，

（1）

若存在独一的一个映照

g:

Y

X,使得gf=IX,

f是可逆的？

（2）

X,使得fg=IY,

13、

（1）X={1,2,3},Y={a,b},

求X到Y射的个数;

X={1,2,3,4,5},Y={a,b},

求X到Y的射的个数;

（3）

X={1,2,

⋯,n},Y={a,b}

，求X到Y的射的个数;

（4）

⋯,n},Y={y1,y2,

⋯,ym},nm,若f:

XY，求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不足以下哪些性？

什么？

[aRba∩b≠￠]

（1）自反性

（2）反自反性（3）称性

（4）反称性（5）性

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

xRyx-y=a+bi，a,b非整数，确立R的性。

17、RX上的二元关系，然若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上的关系以下：

（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，证明：

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个极点的简单无向图。

若G的边数q=（p-1）

·

（p-2）/2+2

，证明G为哈密顿图。

（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

73、d1,d2,⋯,dp是p个正整数,p≥2,且di2p2。

存在一棵点度数d1,d2,⋯,dp的。

i1

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<

p-1，χ（G）=0；

（2）若q≥p-1，χ（G）≤[2q/p]

11

10、若G的解已画在平面S上，并且任何两条均不订交（除可能在端点订交外），G称被嵌入平面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⋯upD的一条哈密路。

由法原理知任何p本成立。

12