《离散数学》图论部分习题

第一篇：《离散数学》图论部分习题

《离散数学》图论部分习题

1.已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形.（24-3*6）/2 +6=9 2.是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶无向简单图G中最大度≤6 3.设d1、d2、…、dn为n个互不相同的正整数.证明：不存在以d1、d2、…、dn为度序列的无向简单图.Max{d1，d2，…，dn}≥n，n阶无向简单图G中最大度≤n-1 4.求下图的补图.5.1)试画一个具有5个顶点的自补图

2)是否存在具有6个顶点的自补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整 数，n=4k或n=4k+1，不存在6阶自补图。

6.设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现

7.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。

8.图G如下图所示：

1)写出上图的一个生成子图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v)| vV } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下无向完全图Kn为欧拉图？

n为奇数时

10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数； 桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分支上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分支上只有一个奇度顶点，与握手引理矛盾。

11.证明：有桥的图不是哈密尔顿图.若G是K2，显然不是哈密尔顿图；

否则n≥3，则桥的两个端点u和v至少有一个不是悬挂顶点（容易证明悬挂顶点不是割点）；设u不是悬挂点，则u是割点，存在割点显然不是哈密尔顿图。

12.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？

X+2*4+3*3=2*（2+3+x-1）

x=9 13.证明：最大度Δ（T）≥k的树T至少有k片树叶。

设有n个顶点，其中x片树叶

2*（n-1）≥1*K+（n-x-1）*2+x*1

x≥k 14.已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数.n-9+4=3+1

n=9

15.给出全部互不同构的4阶简单无向图的平面图形。

16.如果G是平面图, 有n个顶点、m条边、f个面，G有k个连通分支。试利用欧拉公式证明:：n-m+f=k+1.

第二篇：离散数学图论习题

第4章图论

综合练习

一、单项选择题

1．设L是n阶无向图G上的一条通路，则下面命题为假的是()．

(A)L可以不是简单路径，而是基本路径

(B)L可以既是简单路径,又是基本路径

(C)L可以既不是简单路径，又不是基本路径

(D)L可以是简单路径，而不是基本路径

答案：A

2．下列定义正确的是()．

(A)含平行边或环的图称为多重图(B)不含平行边或环的图称为简单图

(C)含平行边和环的图称为多重图(D)不含平行边和环的图称为简单图答案：D

3．以下结论正确是()．

(A)仅有一个孤立结点构成的图是零图

(B)无向完全图Kn每个结点的度数是n

(C)有n(n>1)个孤立结点构成的图是平凡图

(D)图中的基本回路都是简单回路

答案：D

4．下列数组中，不能构成无向图的度数列的数组是()．

(A)(1,1,1,2,3)(B)(1,2,3,4,5)(C)(2,2,2,2,2)(D)(1,3,3,3)

答案：B

5．下列数组能构成简单图的是()．

(A)(0,1,2,3)(B)(2,3,3,3)(C)(3,3,3,3)(D)(4,2,3,3)

答案：C

6．无向完全图K3的不同构的生成子图的个数为（）．

(A)6(B)5(C)4(D)

3答案：C

7．n阶无向完全图Kn中的边数为（）．(A)n(n1)n(n1)(B)(C)n(D)n(n+1)2

2答案：B

8．以下命题正确的是()．

(A)n(n1)阶完全图Kn都是欧拉图

(B)n(n1)阶完全图Kn都是哈密顿图

(C)连通且满足m=n－1的图(V=n,E=m)是树

(D)n(n5)阶完全图Kn都是平面图

答案：C

10．下列结论不正确是()．

(A)无向连通图G是欧拉图的充分必要条件是G不含奇数度结点

(B)无向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点

(C)有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度

(D)有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等

1于出度 答案：D

11．无向完全图K4是（）．

（A）欧拉图（B）哈密顿图（C）树答案：B

12．有4个结点的非同构的无向树有()个．

(A)2(B)3(C)4(D)5 答案：A

13．设G是有n个结点，m条边的连通图，必须删去G的()条边，才能确定G的一棵生成树．

(A)mn1(B)nm(C)mn1(D)nm1 答案：A

14．设G是有6个结点的完全图，从G中删去()条边，则得到树．(A)6(B)9(C)10(D)15 答案：C

二、填空题

1．数组{1，2，3，4，4}是一个能构成无向简单图的度数序列，此命题的真值是.答案：0

2．无向完全图K3的所有非同构生成子图有个． 答案：

43．设图GV,E，其中Vn,Em．则图G是树当且仅当G是连通的，且m． 答案：n－

14．连通图G是欧拉图的充分必要条件是 答案：图G无奇数度结点

5．连通无向图G有6个顶点9条边，从G中删去G的一棵生成树T． 答案：4

6．无向图G为欧拉图，当且仅当G是连通的，且G中无 答案：奇数度

7．设图GV,E是简单图，若图中每对结点的度数之和，则G一定是哈密顿图． 答案：

8．如图1所示带权图中最小生成树的权是．

答案：1

2三、化简解答题

1．设无向图G＝，V={v1，v2，v3，v4，v5，v6}，E={(v1，v2),(v2，v2),(v4，v5),(v3，v4),(v1，v3),(v3，v1),(v2，v4)}．(1)画出图G的图形；

图

1图

2(2)写出结点v2, v4，v6的度数；(3)判断图G是简单图还是多重图．解：(1)图G的图形如图5所示．

(2)deg(v2)4,deg(v4)3,deg(v6)0．

(3)图G是多重图．作图如图2.2．设图G＝，其中

V＝{a,b,c,d,e}, E={(a,b),(b,c),(c,d),(a,e)}

试作出图G的图形，并指出图G是简单图还是多

重图？是连通图吗？说明理由.be

解：图G如图8所示．.图G中既无环，也无平行边，是简单图． cd 图G是连通图．G中任意两点都连通.图

3所以，图G有9个结点．作图如图3．

四、计算题

1．设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图．

解：设图G有x个结点，由握手定理

21+22+34+3（x223）＝12

23x24211827x＝9 故图G有9个结点． 图

4满足该条件的简单无向图如图4所示

2．设图G(如图5表示)是6个结点a,b,c, d,e,f的图，试求，图G的最小生成树，并计算它的权．

c 解：构造连通无圈的图，即最小生成树，用

克鲁斯克尔算法：

第一步： 取ab＝1；第二步： 取af=4第三步： 取fe＝3；第四步： 取ad=9图5第五步： 取bc=2

3如图6．权为1+4+3+9+23=40

3．一棵树T有两个2度顶点，1个3度顶点；3个4

问它有几片树叶？

解：设T有n顶点，则有n－1条边．T中有2个 2度顶点，1个3度顶点，3个4度顶点，其余n－2－1-3个1度顶

点．

由握手定理： 2·2+1·3+3·4+(n－2－1-3)=2(n－1)解得 n=15．于是T有15-6=9片树叶

五、证明题

1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．

证：用反证法．设G中的两个奇数度结点分别为u和v．假若u和v不连通．

即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与握手定理的推论矛盾．因而u和v一定是连通的．

第三篇：离散数学习题

集合论

1.A={,1}，B={{a}}求A的幂集、A×B、A∪B、A+B。2.A={1,2,3,4,5}, R={(x,y)|x

4.A={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b关于R的等价类。

5.R是A上的等价关系，A/R={{1,2}，{3}},求A，R。6.请分别判断以下结论是否一定成立，如果一定成立请证明，否则请举出反例。

①如果A∪BC，则AC或者BC。②如果A×B=A×C且A，则B=C。

27.如果R是A上的等价关系，R,r(R)是否一定是A上的等价关系？证明或举例。

8.已知A∩CB∩C,A-CB-C,证明：AB。9.证明：AX(B∩C)=(AXB)∩(AXC)10.证明：P(A)∪P(B)P(A∪B)-111.证明：R[sym] iff R=R

-1212.证明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.证明：s(R∪S)=s(R)∪s(S)14.R是A上的关系，证明：如果R是对称的，则r(R)也是对称的。

15.I是整数集，R={(x,y)|x-y是3的倍数}，证明：R是I上的等价关系。

16.如果R是A上的等价关系，则A/R一定是A的划分。17.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。18.I是正整数集合，R是I×I上的二元关系，R={<,>|xv=yu},证明：R是等价关系。

19.f:AB，R是B上的等价关系，令S={|xA且yA且R}，证明：S是A上的等价关系。

20.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。

21.P和Q都是集合A上的划分，请问P∪Q，P-Q是否是A上的划分，22.RAXA,R[irref]且R[tra],证明：r(R)是A上的偏序关系。

23.画出{1,2,3,4,6}上整除关系的哈斯图，求{2,3,6}的4种元素。

24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),画出S的哈斯图并求{b,c,d,f}的极大元等8种元素。

25.f:A→B,g:B→C都是单（满）射，证明：复合映射gof一定是单（满）射。

26.f:A→B,g:B→C，gof是单射，请问f和g是否一定是单射？请证明或举出反例。27.R是实数集，f:R×RR×R,f()=,请问f是否为单射？是否为满射？分别证明或举反例。28.已知B∩C=,令f：P(B∪C)P(B)×P(C)，对XP(B∪C),令f(X)=(B∩X,C∩X),证明：f是双射。

代数系统

1.是模8加群，Z8={0,1,2,3,4,5,6,7},+8是模8加法，求出的单位元、每个元素的逆元、所有的生成元和所有的子群。

2.求的单位元，零元，每个元素的逆元，每个元素的阶，它是循环群吗？求出它所有的子群。

3.R是实数集，在R上定义运算*为x*y=x+y+xy,问：是代数系统吗？有单位元吗？每个元素都有逆元吗？ ***4.R是非零实数集合，是代数系统，对于R中元素*x,y，令xoy=2x+2y-2。请问中是否存在单位元、零元、哪些元素有逆元？运算o是否满足交换律和结合律。分别说明理由。

5.R是实数集，R上的6运算定义如下：对R中元素x,y，f1()=x+y；f2()=x-y；f3()=xy；f4()=x/y；f5()=max{x,y}；f6()=|x-y|。问：哪些满足交换律、结合律、有单位元、有零元？说明理由。

6.是一个群，证明：G是交换群当且仅当对任意G中222元素x,y,都有等式(xy)=xy成立。

7.证明：如果群G中每个元素的逆元素都是它自已，则G是交换群。

8.循环群一定是交换群。

9.证明：阶为素数的群一定是循环群。

-110.是一个群，uG,定义运算*：x*y=xouoy, 证明：是一个群。

11.整数集Z上定义运算*：对任意整数x和y,x*y=x+y-4,其中+，-为普通加减法。证明：是一个群。

12.证明：如果群G中至少有两个元素，则群中没有零元。13.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分

14.是一个群,aG,n是a的阶(周期)，证明：k<{a|k=0,2,…,n-1},o>是的一个子群。

15.H，K都是群G的子群，请问H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的两个子群，aG, 试证：aHaK当且仅当HK。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，请问(G,*)是否构成群？

n18.是群，e是单位元，aG,a的阶为k,证明：a=e当且仅当 n是k的倍数。

19.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分

20.G是群，证明：S={aG|xG(ax=xa)},则S是G的子群。21.是偶数阶群，则G中必存在2阶元素。22.证明：6个元素的群在同构意义下只有两个。

++23.R为实数集，R为正实数集，与是否同构？ 24.是有限群，证明：G不可能表示成两个真子群的并。25.图论

1.如何判断二部图？完全图、完全二部图的边数。2.如何求E回路？

3.Petersen图是否为E图或H图。

4.哪些完全图是H图？哪些完全图是E图？ 5.n为何值时轮图为H图？ 6.如何求最小生成树。

7.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。8.证明：如果G是欧拉图，则其边图L(G)也是欧拉图。9.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。10.G是平面图，G有m条边，n个顶点，证明：m3n-6。并由此证明K5不是平面图。

11.证明：有6个顶点的简单无向图G和它的补图中至少有一个三角形。

12.证明：在至少有两个顶点的无向树中，至少有2个一度顶点。

13.G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？

14.证明：简单无向图G和它的补图中至少有一个是连通图。15.证明：无向图中奇度点（度数为奇数的点）有偶数个。16.证明：n个顶点的无向连通图至少有n-1条边。17.G是H图，V是G的顶点集，证明：对任意顶点集S，SV，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分图数目。18.一棵无向树有3个3次点，1个顶点次数为2，其余顶点次数为1，问它有几个次数为1的顶点？写出求解过程。19.证明：每个简单平面图都包含一个次至多为5的顶点。20.连通平面图G有n个顶点，m条边和f个面，证明：n-m+f=2。21.如果图G的最大顶点次数≤ρ，证明：G是ρ+1可点着色的。

22.G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？

23.如果一个简单图G和它的补图同构，则称G是自补图，求所有4个顶点自补图。

24.G是平面图，G有m条边，n个顶点，证明：m3n-6。如果G中无三角形，则m2n-4。数理逻辑

1.如果今天是星期一，则要进行英语或数理逻辑考试。

没有不犯错误的人。整数都是有理数。有的有理数不是整数。

不存在最大的整数。有且只有一个偶数是素数。2.求真值表及范式：P(┓QR)、(┓QR)(PR)3.推理：

p(qr)，┓s∨p，q ├ sr pr，qs，p∨q ├ r∨s p∨q，p┓r，st，┓sr，┓t ├ q p(┓(r∧s)┓q),p,┓s ├ ┓q 4.如果小王是理科学生，他一定会学好数学。如果小王不是文科学生，他一定是理科学生。小王没学好数学。所以小王是文科学生。

5.判断各公式在给定解释时的真假值，并且改变论域使该公式在新的解释下取值相反。论域：D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y<4 ①x(F(x)∨G(x))②yyR(x,y)

第四篇：离散数学及其应用集合论部分课后习题答案

作业答案：集合论部分

P90:习题六

5、确定下列命题是否为真。（2）（4）{}

（6）{a,b}{a,b,c,{a,b}} 解答：（2）假（4）真（6）真

8、求下列集合的幂集。（5）{{1,2},{2,1,1},{2,1,1,2}}（6）{{,2},{2}} 解答：

（5）集合的元素彼此互不相同，所以{2,1,1,2}{1,2}，所以该题的结论应该为

{,{{1,2}},{{2,1,1}},{{1,2},{2,1,1}}}

（6）{,{{,2}},{{2}},{{,2},{2}}}

9、设E{1,2,3,4,5,6}，A{1,4}，B{1,2,5},C{2,4},求下列集合。（1）A（2）解答：（1）A（2）

31、设A,B,C为任意集合，证明 B

(AB)

B{1,4}{3,4,6}{4}

(AB){1}{2,3,4,5,6}

(AB)证明：

(BA)(AB)(AB)

(AB)(BA){x|xABxBA}{x|(xAxB)(xBxA)}{x|(xAxB)(xBxB)(xAxA)(xBxA)} {x|(xAxB)(xBxA)}{x|(xA{x|(xAA

B)(xAxB)}{x|(xAB)(xABB)}{x|(xAB)(xAxB)}B)}B)(xABA34、设A,B为集合，证明：如果(AB)证明：（反证法）

设aA(BA)AB，则AB。

B，则aA,aB，所以aAB,aBA； 所以a(AB)但是aA与(AB)

37、设A,B,C为任意集合，证明：CACBC(A证明：

对任意xC，由于CA,CB，所以xA且xB所以xA因此，C(A

(BA)

B矛盾。

B)。

B B。

(BA)AB)。

P121:习题七

5、设A,B为任意集合，证明

若AABB，则AB。

证明：

xAx,xAA

x,xBBxB所以有AB

9、设A{1,2,4,6}，列出下列关系R（2）R{x,y|x,yA|xy|1}（3）R{x,y|x,yAy为素数} 解答：

11、Ri是X上的二元关系，对于xX定义集合（2）R{1,2,2,1}

（3）R{1,2,2,2,4,2,6,2}

Ri(x){y|xRy}

显然Ri(x)X。如果X{4,3,2,1,0,1,2,3,4},且令

R1{x,y|x,yXxy}

R2{x,y|x,yXy1xy2} R3{x,y|x,yXx2y}

求R1(0),R1(1),R2(0),R2(1),R3(3)。解答：

R1(0){1,2,3,4}R1(1){2,3,4}R2(0){1,0}R2(1){2,1}R3(3)，B{1,3,2,4,4,2}。求A13、设A{1,2,2,4,3,3}

B，AB，domA,domB,dom(A解答：

B),ranA,ranB,ran(AB),fld(AB).AAB{1,2,2,4,3,3,1,3,4,2} B{2,4}

domA{1,2,3} domB{1,2,4} dom(AB){1,2,3,4}

ranA{2,3,4} ranB{2,3,4} ran(A B){4}

fld(AB){1,2,3}

16、设A{a,b,c,d}，R1,R2为A上的关系，其中

R1{a,a,a,b,b,d}，R2{a,d,b,c,b,d,c,b}。求R1R2，R2R1，R12，R23。

解答：

R1R2{a,d,a,c,a,d} R2R1{c,d}

R12{a,a,a,b,a,d} R22{b,b,c,c,c,d} R23{b,c,b,d,c,b}

20、给定A{1,2,3,4}，A上的关系R{1,3,1,4,2,3,2,4,3,4}（1）画出R的关系图。（2）说明R的性质。解答：

（1）

（2）R具有反自反性，反对称性，传递性

21、设A{1,2,3}，图7.11给出12种A上的关系，对于每种关系写出相应的关系矩阵，并说明它所具有的性质。

解答：

110（a）111,具有自反性。101110（b）001,具有反对称性和传递性。100111（c）111,具有自反性，对称性和传递性。111

23、设R的关系图如图7.12所示，试给出r(R)，s(R)和t(R)的关系图。

25、设A{1,2,3,4}，R是A上的等价关系，且R是A上所构成的等价类为{1},{2,3,4}。（1）求R。（2）求RR（3）求R传递闭包。解答：

（1）R{1,1,2,2,3,3,4,4,2,3,3,2,2,4,4,2,3,4, 14,3}

（2）由于等价关系满足对称性，所以R所以RR11R

R

（3）由于等价关系满足传递性，所以传递闭包为其自身，即t(R)R

26、对于给定的A和R，判断R是否为A上的等价关系。（1）A为实数集，x,yA,xRyxy2。（2）A{1,2,3}，x,yA,xRyxy3。（3）AZ，x,yA,xRyxy为奇数。

（5）AP(X),CX，x,yA,xRyxyC 解答：

（1）不是，不满足自反性、对称性、传递性。（2）不是，由于A{1,2,3}集合较小，①自反性：xA,xx3x,xR

②对称性，x,yR,xy3yx3y,xR 但是传递性不满足，1,3,3,2R，但是1,2R。（3）不是，满足对称性、传递性，但是不满足自反性 取x2，但是224不为奇数，所以2,2R。

（5）满足

①自反性：xAxXxxCx,xR ②对称性：x,yRyxxyCy,xR ③传递性：x,y,y,zR

xyC,yzC (xy)(yx)C,(yz)(zy)C(xy)C,(yx)C,(yz)C,(zy)C下面证明(xz)C

a(xz)ax,az

若ay，则ayz，所以aC 若ay，则axy，所以aC

所以(xz)C，同理可证，(zx)C 所以xz(xz)(zx)C 所以x,zR。因此满足传递性。

27、设A{a,b,c,d},A上的等价关系

R{a,b,b,a,c,d,d,c}IA

画出R的关系图，并求出A中各元素的等价类。解答：关系图为

等价类[a][b]{a,b}；[c][d]{c,d}

30、设A{1,2,3,4},，在AA上定义二元关系R，u,v,x,yAA,u,vRx,yuyxv。

（1）证明R为AA上的等价关系。（2）确定由R引起的对AA的划分。解答：（1）证明：

①自反性：x,yAA，由于xyxy，所以x,y,x,yR； ②对称性：x,y,u,vR

有xvuy，所以uyxv 因此u,v,x,yR

③传递性：x,y,u,v,u,v,s,tR

有xvuy，utsv，所以xsty 因此x,y,s,tR。

（2）等价类有

[1,1]{1,1,2,2,3,3,4,4} [1,2]{1,2,2,3,3,4} [1,3]{1,3,2,4} [1,4]{1,4} [2,1]{2,1,3,2,4,3} [3,1]{3,1,4,2} [4,1]{4,1}

37、对于下列集合与整除关系画出哈斯图。（1）{1,2,3,4,6,8,12,24}（2）{1,2,3,4,5,6,7,8,9,10,11,12} 解答：（1）

（2）

38、针对图7.14中的每个哈斯图，写出集合以及偏序关系的表达式。

解答：

（a）集合为A{1,2,3,4,5}，偏序关系为{1,3,1,5,2,4,2,5,3,5,4,5}IA（b）集合为B{a,b,c,d,e,f}，偏序关系为{a,b,c,d,e,f}IB（c）集合为C{1,2,3,4,5}，偏序关系{1,2,1,3,1,4,1,5,2,4,2,5,3,4,3,5,4,5}IC

40、分别画出下列偏序集A,R的哈斯图，并找出A的极大元、极小元、最大元和最小元。

（1）A{a,b,c,d,e,f}，R{a,d,a,c,a,b,a,e,b,e,c,e,d,e}IA

R{c,d}IA（2）A{a,b,c,d,e}

解答：

（1）哈斯图为

极小元为a,f,极大元为e,f，无最大元、最小元（2）哈斯图为

极小元为a,b,c,e，极大元为a,b,d,e，无最大元、最小元

41、A{1,2,3....,12}，R为整除关系，B{x|2x4}，在偏序集A,R中求B的上界、下界、最小上界和最大下界。

解：下界即为公约数，2，3，4的公约数只有1，所以下界为1，最大下界也为1；

下界即为公倍数，2，3，4的公倍数只有12，所以上界为1，最大上界也为12；

P141:习题八

4、判断下列函数中哪些是满射？哪些是单射？哪些是双射？（2）f:NN,f(x)x22（4）f:N{0,1},f(x)01xisodd

xiseven（6）f:RR,f(x)x22x15

解答：（2）单射；（3）满射；（4）既不为单射也不为满射。

{1,2,3}

5、设X{a,b,c,d},Y，f{a,1,b,2,c,3}，判断下列命题的真假。

（1）f是从X到Y的二元关系，但不是X到Y的函数。（3）f是从X到Y的满射，但不是单射。解答：（1）真；（3）假

15、设A{a,b,c}，R为A上的等价关系，且R{a,b,b,a}IA，求自然映射g:AA/R。

解答： A/R{{a,b},{c}}

{a,b}g(x)cxa,b xc19、设f,g是从N到N的函数，且

x1f(x)0x（1）求f（2）说明f解答： x0,1,2,3x4x5g

x

g(x)23xiseven

xisoddg是否为单射、满射、双射？

（1）f3x1gg(f(x))20x2x0,2,5,7,9......x1,3x4x6,8,10,12.....（2）为满射，但是不为单射。

20、设f:NNN，f(x)x,x1（1）说明f是否为单射和满射，说明理由。

（2）f的反函数是否存在，如果存在，求出f的反函数；（3）求ranf。解答：

（1）xy时，x,x1y,y1，所以为单射； 而对1,3NN，不存在xN，使得f(x)x,x1，所以不为满射。

（2）不存在反函数，因为不是双射函数；（3）ranf{x,x1|xN}

22、对于以下集合A和B，构造从A到B的双射函数。（1）A{1,2,3},B{a,b,c}（2）A(0,1),B(0,2)

（3）A{x|xZx0},BN（4）AR,BR 解答： a（1）f(x)bc（2）f(x)2xx1x2 x3x(0,1)（3）f(x)x1

（4）f(x)ax(a0,a1)

第五篇：离散数学习题及答案

离散数学考试试题（A卷及答案）

一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

(1)若A去，则C和D中要去1个人；

(2)B和C不能都去；

(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此

(ACD)∧(B∧C)∧(CD)

(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))

(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)

F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)

(A∧C)∨(B∧C∧ D)∨(C∧D)

T

故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：

x(S(x)∧W(x))，xY(x)x(S(x)∧Y(x))

下面给出证明：

(1)xY(x)P

(2)Y(c)T(1)，ES

(3)x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)x(S(x)∧Y(x))T(6)，EG

三、（10分）设A、B和C是三个集合，则AB(BA)。

证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)

x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)

(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))

(BA)。

四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i14232－

15>}。

五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。

证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。

下证对任意正整数n，R对称。

因R对称，则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx，所以R对称。若Rn对称，则xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1x，所以Rn1对称。因此，对任意正整数n，Rn对称。对任意的x、y∈A，若xt(R)y，则存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是对称的。

六、（10分）若f：A→B是双射，则f：B→A是双射。

证明因为f：A→B是双射，则f是B到A的函数。下证f是双射。

对任意x∈A，必存在y∈B使f(x)＝y，从而f(y)＝x，所以f是满射。

对任意的y1、y2∈B，若f(y1)＝f(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B是函数，则y1＝y2。所以f是单射。

综上可得，f：B→A是双射。

七、（10分）设是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。

证明因为是一个半群，对任意的b∈S，由*的封闭性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因为S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j－i，则bj＝bp*bj。所以对q≥i，有bq＝bp*bq。

因为p≥1，所以总可找到k≥1，使得kp≥i。对于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，则a∈S且a*a＝a。

八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：

m≤

rl(n－2)。l2l证明设G有r个面，则2m＝

2)。d(f)≥lr。由欧拉公式得，n－m＋r＝2。于是，m≤l2(n－ii

1（2）设平面图G＝是自对偶图，则| E|＝2(|V|－1)。

证明设G＝是连通平面图G＝的对偶图，则G G，于是|F|＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

离散数学考试试题（B卷及答案）

一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R

证明因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。

(1)R附加前提

(2)PRP

(3)PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)QSP

(7)ST(5)(6)，I

(8)RSCP

(9)S∨RT(8)，E

二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。

设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。

(1)x(P(x)Q(x))P

(2)x(P(x)∨Q(x))T(1)，E

(3)x(P(x)∧Q(x))T(2)，E

(4)P(a)∧Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)Q(a)T(4)，I

(7)x(P(x)(A(x)∨B(x))P

(8)P(a)(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)x(A(x)Q(x))P

(11)A(a)Q(a)T(10)，US

(12)A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。

解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称为由A1、A2和

i1

3A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。

对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，i13即有a∈si，于是Usi。又显然有siU，所以U＝si。

i1i1i1i1rrrr

任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。综上可知，{s1，s2，…，sr}是U的一个划分。

五、（15分）设R是A上的二元关系，则：R是传递的R*RR。

证明(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。

反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。

六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。

当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。

假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。

设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：

若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由数学归纳法知，结论成立。

七、（10分）设函数g：A→B，f：B→C，则：

(1)fg是A到C的函数；

(2)对任意的x∈A，有fg(x)＝f(g(x))。

证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fg。所以Dfg＝A。

对任意的x∈A，若存在y1、y2∈C，使得、∈fg＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。

综上可知，fg是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝fg。又因fg是A到C的函数，则可写为fg(x)＝f(g(x))。

八、（15分）设是的子群，定义R＝{|a、b∈G且a1*b∈H}，则R是G中的－

一个等价关系，且[a]R＝aH。

证明对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－

若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－

若∈R，∈R，则a1*b∈H，b1*c∈H。因为H是G的子群，所以(a1*b)*(b1*c)＝a－－－－

－1*c∈H，故∈R。

综上可得，R是G中的一个等价关系。

对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－

[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH[a]R。所以，[a]R－

＝aH。