下载文档原格式
哈尔滨工业大学集合论与图论计算机学院XX 年秋季一、 解答下列问题，要求只给出答案（每题2分，共16分）1.设A B 、为集合，试求一个集合X ，合得A X B ∆=。
（ A B ∆ ）2.设{}1,2,3,4A =，{}1,2B =，试求从A 到B 的满射的个数。
（42214-=）3.设{}1,2,,10A =，试求A 上反自反二无关系的个数。
（29022n n -=）4.设{}12,,,p A u u u =，()112q p p ≤-。
试求以V 为顶点集具有条边的无向图的个数。
（ ⎝⎛-2/)1(p p q ） 5.设T 是一个有P 个顶点的正则二元树，试求下的叶子数，其中P 是奇数。
（12P +） 6.正整数m 和n 为什么值时,Km n 为欧拉图？（m n 和为偶数）7.设(),G V E =为无向图，,V P E P ==。
如果G 是边通图，那么G 至少有几个生成树？ （3个）8. 具有p 个顶点q 条边的平面连通图中，p 和q 应满足什么样的关系式？(36q p ≤-)二、以下各题要求只给出答案（每题2分，共14分）１.设{}()()(){},,,,,,,,,X a b c d R a b b c c a ==，试求R 的传递闭包。
（()()()()()()()()(),,,,,,,,,,a a b b c c a b b c c a a c b a c b ，，，，，，，）2.将置换（123456789791652348）分解为循环置换的乘积，然后分解成对换的乘积()()()()()()()()()173298465171329282426=。
3.设0000010110100000010000000A ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦12345110000210110310100410110500001⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦ 如果A 4.设{}{}0,1,,,,,,,B E a b c x y z ==。
08信安专业离散数学期中考试试题1.设A, B, C, D为4个集合. 已知A⊆B且C⊆D.证明:A∪C⊆B∪D; A∩C⊆B∩D . (15分)2.化简以下公式: A∪((B―A)―B) (10分)3.设R是非空集合A上的二元关系.证明:R∪R-1是包含R的最小的对称的二元关系. (15分)4.设A={1,2,…,20},R={<x,y>|x,y∈A∧x≡y(mod 5)}.证明:R为A上的等价关系. 并求商集A/R. (15分)5.给出下列偏序集的哈斯图,并指出A的最大元,最小元,极大元和极小元. A={a,b,c,d,e},≢A= I A∪{<a,b>,<a,c>, <a,d>,<a,e>,<b,e>,<c,e>,<d,e>} (15分)6.设g:A→B, f:B→C.已知g f是单射且g是满射,证明:f是单射. (10分)7.设S={0,1}A, 其中A={a1,a2,…,a n}.证明:P(A)与S等势.(10分)8.证明:任何一组人中都存在两个人,他们在组内认识的人数恰好相等(假设,若a认识b,则a与b互相认识). (10分)期中考试试题解答1.证明: ∀x,x∈A∪C x∈A∩C⇔x∈A∨x∈C ⇔x∈A∧x∈C⇒x∈B∨x∈D (A⊆B,C⊆D) ⇒x∈B∧x∈D (A⊆B,C⊆D) ⇔x∈B∪D ⇔x∈B∩D∴A∪C⊆B∪D ∴A∩C⊆B∩D2.解:A∪((B―A)―B)=A∪((B∩∽A)∩∽B)=A∪(∽A∩(B∩∽B))=A∪(∽A∩φ)=A∪ф=A .3.证明:首先证R∪R-1是对称关系. ∀<x,y>,<x,y>∈R∪R-1⇔<x,y>∈R∨<x,y>∈R-1⇔<y,x>∈R-1∨<y,x>∈R⇔<y,x>∈R-1∪R⇔<y,x>∈R∪R-1∴ R∪R-1是对称关系.再证任何包含R的对称关系一定包含R∪R-1.设R⊆R’且R’是对称关系.∀<x,y>,<x,y>∈R∪R-1⇔<x,y>∈R∨<x,y>∈R-1⇔<x,y>∈R∨<y,x>∈R⇒<x,y>∈R’∨<y,x>∈R’⇒<x,y>∈R’∨<x,y>∈R’(因为R’是对称关系)⇒<x,y>∈R’.从而R∪R-1⊆R’.4.证明: 设A={1,2,…,20},R={<x,y>|x,y∈A∧x≡y (mod 5)}∀x∈A, x=5k+i,0≢i≢4, ∴x≡x (mod 5), 即xRx;∀x,y∈A,若xRy,即x≡y(mod 5),故有x=5k+i且y=5m+i, 所以有y≡x (mod 5),即有yRx.∀x,y,z∈A,若xRy且yRz,则有x≡y(mod 5)和y≡z(mod 5),即有x=5k+i,y=5m+i且z=5n+i(0≢i≢4),从而x≡z (mod 5) 故有xRz.因为我们证明了G有自反性,对称性和传递性,所以R是等价关系.A/R={{1,6,11,16},{2,7,12,17},{3,8,13,18},{4,9,14,19},{5,10,15,20}}5. 解:哈斯图见附图(第5题答案).A 的最大元和极大元是e, 最小元和极小元是a.6. 证明:已知g f 是单射且是g 满射.反证法.假设f 不是单射,故存在b 1,b 2∈B,b 1≠b 2,且 f(b 1)=f(b 2)=c.由g 是满射知,存在a 1,a 2∈A,使得g(a 1)=b 1, g(a 2)=b 2. 由于g 是函数且b 1≠b 2,故a 1≠a 2.但是现在有 g f(a 1)=f(g(a 1))=f(b 1)=c=f(b 2)=f(g(a 2))=g f(a 2), 这与g f 是单射函数矛盾.7. 证明:设S={0,1}A ,A={a 1,a 2,…,a n }.P(A)={B|B ⊆A }. 定义特征函数ϕB :A →{0,1},⎩⎨⎧∉∈=Bx B x x B ,0,1)(ϕ 则存在双射f:P(A)→{0,1}A ,使得f(B)=B ϕ.因为∀B ∈P(A),∃唯一的g=B ϕ∈{0,1}A ,使得f(B)=B ϕ.故 f 是P(A)到{0,1}A 的函数.∀B 1,B 2∈P(A),若B 1≠B 2,则f(B 1)=1B ϕ≠2B ϕ=f(B 2),故f 是单射.∀g ∈{0,1}A ,∃B={x|x ∈A ∧g(x)=1}∈P(A),使得f(B)=g= B ϕ,从而f 是满射.综上所述,f是P(A)到{0,1}A的双射. 故P(A)与{0,1}A等势.8.证明:设一组A中有n个人A={a1,a1,…,a n}(n≣2),我们用ϕ(a i)表示a i认识的人数.情形1:A中每个人至少认识同组中的一个人.这时,1≢ϕ(a i)≢n―1, i=1,2,…,n.即ϕ是A到{1,2,…, n―1}的函数.然而|A|=n,|{1,2,…,n―1}|=n―1,由鸽笼原理,存在1≢s<t≢n,使得ϕ(a s)=ϕ(a t).情形2:A中有一个人a i不认识A中其他任何人,即ϕ(a i)=0.这时,a i以外的每一个人至多认识A中n―2个人.所以0≢ϕ(a j)≢n―2,j=1,2,…,n. 即ϕ是A到{0,1,…,n―2}的函数.然而|A|=n,|{0,1,…,n―2}|=n―1,由鸽笼原理,存在1≢s<t≢n,使得ϕ(a s)=ϕ(a t).综上所述,在两种情况下,A中都有两个人,他们在组内认识的人数恰好相等.。
第四章 无穷集合及其基数习题136P 1.设A 为由序列12,,,,n a a a的所有项组成的集合，则是否市可数的？为什么？解：因为序列是可以重复的，故若A 是由有限个数组成的集合，则A 是有限的集合；若A 是由无限个数组成的集合，则A 是可数的。
故本题A 是至多可数的。
2.证明：直线上互不相交的开区间的全体所构成的集合至多可数。
证：在每个开区间中取一个有理数，则这些有理数构成的集合是整个有理数集合Q 的子集，因此是至多可数的。
3.证明：单调函数的不连续点的集合至多可数。
证：设A 是所有不连续点的集合，f 是一个单调函数，则00,x A x ∀∈对应着一个区间0((0),(0))f x f x -+，于是由上题便得到证明。
4.任一可数集A 的所有有限子集构成的集族是可数集合。
证：设1212{,,,,},{,,,},n i i ik A a a a B a a a ==则B A ⊆且B k =<∞。
令{,}B B A B B =⊆<∞，设:{0,1}A ϕ→，则ϕ是Ａ的子集的特征函数。
,()B B ϕ∀∈B =｛0，1的有穷序列｝，即i a A ∀∈， 若i a B ∈，则对应1；若i a B ∉则对应0。
于是,()B B ϕ∀∈B 就对应着一个由0，1组成的有限序列0，1，1，0，…，0，1。
此序列对应着一个二进制小数，而此小数是有理数。
于是，可数集A 的所有有限子集B 对应着有理数的一个子集。
又121212,,,,B B B B B B ∀∈B ≠对应的小数也不同，故ϕ是单射。
而可数集Ａ的所有有限子集B 是无穷的，故B 是可数的。
5．判断下列命题之真伪：(1)若:f X Y →且f 是满射，则只要X 是可数的，那么Y 是至多可数的；(2)若:f X Y →且f 是单射，那么只要Y 是可数的，则X 也是可数的；(3)可数集在任一映射下的像也是可数的； 答案：对，错，错。
7．设Ａ是有限集，Ｂ是可数集，证明：{|:}A B f f A B =→是可数的。
第六章图的根本概念P206习题1.画出具有4个顶点的所有无向图(同构的只算一个).11个2.画出具有3个顶点的所有有向图(同构的只算一个)o16个3.画出具有4个、6个、8个顶点的三次图.略4.某次宴会上,许多人互相握手.证实：握过奇数次手的人数为偶数(注意,0是偶数)o把实际问题转化为图论问题,然后用握手定理的推论.P209习题1.设u与v是图G的两个不同顶点.假设u与v间有两条不同的通道(迹),那么G 中是否有圈假设u与v间有两条不同的通道,G中无圈假设u与v间有两条不同的迹,G中有圈2.证实：一个连通的(p , q)图中q?p-1.数学归纳法3.设G是一个(p, q)图,且q (p 1)(p 2)/2,那么G是连通的.征2用反征法口假咬囹G是小庄逋叼,那么图G至少狂仕两?逢逋分支.尸⑵⑼)和&二仇必)时,G 的最大可能边数勺二名+公式T)'2 +p式1)/2 ,其中曲三户一］,1 < < p-1 ?所以〞(pZp-W2,与题设矛盾n所以假设.是简单图,那么仃是连通的.6.在一个有n个人的宴会上,每个人至少有m个朋友(2&m< n).试证：有不少于m+1个人,使得他们按某种方法坐在一张圆桌旁, 每人的左、右均是他的朋友. 证实：把实际问题转化为图论问题,就和下面的题一样了.8.设G是图.证实：假设5 (G) >2,那么G包含长至少是6(G)+1的圈.这两个题和这个题一样的证实方法.例3设行=(匕均是无向图,证实：假设久⑴之出,那么行包含长至少为中+ 1的|口1路, iiF：设上是G中最长的路, £:v t P2L v…a由于WE—d次置之所以必自Z上的m个顶点工门,,…,叫(2 = «o,VQ与耳邻接,干是马巧…%巧便是G中的一个回路,且长至少为2去晨假设上上不存在陋个顶点与耳邻接,那么在最长路L外必有一个顶点与巧邻接,于是有更长路矛盾.P216习题1.证实：假设图G不是连通图,那么GC是连通图.由于G不连通,故G至少有两个分支对于G,中任意两个顶点把和v ：(1)假设"匕匕,¥曰匕,那么仃与野不在G中邻接.由补图的定义可知：N与F必在T中邻接；(2)假设以廿三艮(或匕),取WE匕(或昨),那么廿与w, w与在G都不邻接,故"与1#, w与廿在G'必邻接.于是ww窜就是G'中的一条踏.综上可知,由于对G『中任意两个加点〞和% .和y之间都有路连接,故G, 连通.2.证实：每一个自补图有4n或4n+1个顶点.(3)由于每个自补图G的对应的完全图的边数必为偶数,即q-p(p-1)/2为偶数.而当p二123时,图G无自补图,只有p之4时,图G才有自补图;于是「可写成如下形式,4/4〃+ L4叱2刈】+3,其中〃为正整数；代入〞风p -1)2中,只有加也十1才能使&为偶数r故每个自补图必有4“成4"】个顶点.例4证实：在一个连通图中,两条最长的路有一个公共的顶点口证】设乙与乙是图中的两条最长的路r 4飞打4 J上上：叫的力—但设心与心没有公共顶点*由于<7是连通的,所以心与上上之间必TT一条路尸连接且|尸岸1 0令尸与4上的匕连接,与&上的2连接,那么假设,之J*那么路先岭次〃产产1%比4长,矛盾：假设,,J f那么路修/…%7VM.I…/比4长,矛盾.故假设不成立,即两条最长的路必有公共顶点,P228习题1.给出一个10个顶点的非哈密顿图的例子,使得每一对不邻接的顶点u和v,均有：degu+degv> 9.下列图中任意一对不邻接的顶点u和v ,均有：degu+degv> 9 .2.试求Kp中不同的哈密顿圈的个数.〔p-1〕!/2 4.完全偶图Km n为哈密顿图的充分必要条件是什么?〔2〕=＞假设|匕＜|匕,有〔1〕可知区门不是哈密顿图；假设IRWI/I,同理有K〞不是哈密顿图.故&◎是哈密顿图时只有14 1=1/ I,即一-*U假设加二〃,那么匕扇即斗廛gv=|1I/2+|炉］,2二/卜由定理知：?明,是哈密顿图二10.证实具有奇数顶点的偶图不是哈密顿图.证：〔1〕设G是,个具有奇数顶点的偶图,那么G的顶点集了有•个二划分, 即展的匕｝H有因周匕I,不妨设| - K彩|,那么有印〔0—=1七忸匕I,由哈密顿图的必要条件可知：G不是哈密顿图.。
集合论与图论JK211009——在线考试复习资料2021版一、单选题1.设G是简单有向图,可达矩阵P(G)刻画下列关系中的是()A.点与边B.边与点C.点与点D.边与边答案：C2.A.6B.5C.4D.3答案：B3.图中满足以下哪个条件?()A.有欧拉回路和哈密尔顿回路B.有欧拉回路,但无哈密尔顿回路C.无欧拉回路,但有哈密尔顿回路D.既无欧拉回路,又无哈密尔顿回路答案：D4.A.B.C.D.答案：B5.下面不能成为图的度数序列是()A.(1,2,3,4)B.(1,2,3,6)C.(1,3,5,7)D.(1,3,4,9)答案：D6.设简单无向图G有15条边,有3个4度结点,有4个3度结点,其余结点的度数均为2,那么G的结点总数为()A.9B.10C.11D.12答案：B7.如图所示,以下说法正确的是()A.e是割点B.{a,e}是点割集C.{b,e}是点割集D.{d}是点割集答案：A8.图G和G1的结点以及边分别存在一一对应关系,此对应关系是两图同构的()A.充分条件B.必要条件C.充要条件D.既不充分也非必要条件答案：B9.设顶点集为V={a,b,c,d,e},下列几个无向图是简单图的有()A.G1=(V,E1),E1={(a,b),(b,c),(c,b),(a,e)}B.G2=(V,E2),E2={(a,b),(b,c),(c,a),(a,d),(d,e)}C.G3=(V,E3),E3={(a,b),(b,c),(c,d),(e,e)}D.G4=(V,E4),E4={(a,a),(a,b),(c,c),(c,e)}答案：B10.若R是集合A上的等价关系,则下面哪个不一定满足()A.B.R2=RC.t(R)=RD.R-1=R答案：A11.A.B.C.D.答案：A12.A.B.C.D.答案：A13.下列哪个关系矩阵具有反自反性?()A.B.C.D.答案：A14.设集合A={1,2,3,4},A上的等价关系R={<1,3>,<3,1>,<2,4>,<4,2>}∪I A,则对应于R的A划分是()A.B.C.D.答案：B15.设集合A={1,2,3,4}上的二元关系,R={<1,1>,<2,2>,<2,3>,<4,4>},S={<1,1>,<2,2>,<2,3>,<3,2>,<4,4>},则S是R的()A.自反闭包B.传递闭包C.对称闭包D..不是任何闭包答案：C16.哈密尔顿回路是()A.只是简单回路B.是基本回路,但不是简单回路C.既是基本回路也是简单回路D.既非基本回路也非简单回路答案：C17.设A={1,2,3,4,5,6,7,8},R是A上的整除关系,B={2,4,6},则集合的最大元、最小元、上界、下界依次为()A.8、2、8、2B.无、2、无、2C.6、2、6、2D.8、1、6、1答案：B18.下列各组数中不能构成无向图的度数序列的是()A.(1,1,2,3,5)B.(1,3,1,3,2)C.(1,2,3,4,5)D.(1,2,3,4,6)答案：C19.A.自反的B.对称的C.传递且对称的D.反自反且传递的答案：B20.图中满足以下哪个条件?()A.有欧拉回路和哈密尔顿回路B.有欧拉回路,但无哈密尔顿回路C.无欧拉回路,但有哈密尔顿回路D.既无欧拉回路,又无哈密尔顿回路答案：B21.设A={a,{a}},下列命题错误的是()A.B.C.D.答案：A22.设G1、G2、G3、G4都是(4,3)的简单无向图,则它们之间至少有几个是同构的?()A.2个B.3个C.4个D.可能都不同构答案：B23.若集合A的元素个数为4,则其幂集的元素个数为()A.1个B.4个C.8个D.16个答案：D24.设结点集V={a,b,c,d},则下列与V构成强连通图的边集的是()A.E1={<a,d>,<b,a>,<b,d>,<c,b>,<d,c>}B.E2={<a,d>,<b,a>,<b,c>,<b,d>,<d,c>}C.E3={<a,c>,<b,a>,<b,c>,<d,a>,<d,c>}D.E4={<a,b>,<a,c>,<a,d>,<b,d>,<c,d>}答案：A25.在0()之间写上正确的符号。
例：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；f5是双射(单射,满射)；f6不是单射,不是满射。
7、证明：在52个正整数中，必有两个整数，使得这两个整数之和或差能被100整除。
离散数学考试试题及答案离散数学考试试题及答案离散数学是计算机科学和数学中的一门重要学科，它研究的是离散的结构和对象。
离散数学的理论和方法在计算机科学、信息科学、通信工程等领域具有广泛的应用。
下面将为大家提供一些离散数学考试试题及答案，希望对大家的学习和复习有所帮助。
1. 集合论题目(1) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A∪B的结果。
答案：A∪B={1,2,3,4,5,6,7}(2) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A∩B的结果。
答案：A∩B={3,4,5}(3) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A-B的结果。
答案：A-B={1,2}2. 图论题目(1) 给定一个无向图G，顶点集为V={A,B,C,D,E}，边集为E={(A,B),(A,C),(B,D),(C,D),(D,E)}，求该图的邻接矩阵。
答案：邻接矩阵为：A B C D EA 0 1 1 0 0B 1 0 0 1 0C 1 0 0 1 0D 0 1 1 0 1E 0 0 0 1 0(2) 给定一个有向图G，顶点集为V={A,B,C,D,E}，边集为E={(A,B),(B,C),(C,D),(D,E),(E,A)}，求该图的邻接表。
答案：邻接表为：A ->B ->C ->D ->E -> AB -> CC -> DD -> EE -> A3. 命题逻辑题目(1) 判断以下命题是否为永真式：(p∨q)∧(¬p∨r)∧(¬q∨¬r)。
答案：是永真式。
(2) 给定命题p：如果天晴，那么我去游泳；命题q：我没有去游泳。
请判断以下命题的真假：(¬p∨q)∧(p∨¬q)。
答案：是真命题。
4. 关系代数题目(1) 给定关系R(A,B,C)和S(B,C,D)，求R⋈S的结果。
