集合论图论重要习题100.docx
- 文档编号:6583473
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:18
- 大小:24.40KB
集合论图论重要习题100.docx
《集合论图论重要习题100.docx》由会员分享,可在线阅读,更多相关《集合论图论重要习题100.docx(18页珍藏版)》请在冰点文库上搜索。
集合论图论重要习题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)nN,S(n)=n+1,S称自然数集N上的后函数。
(2)S
(1)=1,nN,S(n)=n-1,n≥2,S称自然数集N上的前仆函数。
5、f:
N×NN,f((x,y))=xy。
(1)明f是不是射、射或双射?
(2)求f(N×{1}),f-1({0})。
(1,4)≠(2,2),f((1,4))=f((2,2))=4;
yN,f((1,y))=1y=y,·任一元都有原象;
[f不是射,f是射]
f(N×{1})={n·1|nN}=N;
f-1({0})={(x,y)|xy=0}={N×{0}}?
{{0}×N}。
6、R、I、N是数、整数、自然数会合,下边定映照
f1,f2,f3,f4,f5,f6,确立
它的性。
(0N)
(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,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)
若存在独一的一个映照
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},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上的关系以下:
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最大多少?
:
在每个地区放一个点,当两地区相,就在相的两个点一条,这样
结构了一个平面且是完整平面,而最大的完整平面K4,所以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≤4。
又对任意得极点v∈V,degv≥3,有3n≤2m,故n≤2m/3,因为n是整数,故n≤4。
所以n+r≤4+4=8与(1)矛盾,所以结论正确。
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
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 (2)若q≥p-1,χ(G)≤[2q/p] 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⋯upD的一条哈密路。 由法原理知任何p本成立。 12
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 集合论 重要 习题 100