集合论与图论复习题
- 格式:doc
- 大小:256.00 KB
- 文档页数:4
哈尔滨工业大学集合论与图论计算机学院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分)1.设{}()()(){},,,,,,,,,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 ==。
集合与图论习题第一章习题.画出具有个顶点地所有无向图(同构地只算一个)..画出具有个顶点地所有有向图(同构地只算一个)..画出具有个、个、个顶点地三次图..某次宴会上,许多人互相握手.证明:握过奇数次手地人数为偶数(注意,是偶数)..证明:哥尼斯堡七桥问题无解..设与是图地两个不同顶点.若与间有两条不同地通道(迹),则中是否有回路?.证明:一个连通地(,)图中≥..设是一个(,)图,δ()≥[],试证是连通地..证明:在一个连通图中,两条最长地路有一个公共地顶点..在一个有个人地宴会上,每个人至少有个朋友(≤≤).试证:有不少于个人,使得他们按某种方法坐在一张圆桌旁,每人地左、右均是他地朋友.b5E2R。
.一个图是连通地,当且仅当将划分成两个非空子集和时,总有一条联结地一个顶点与地一个顶点地边..设是图.证明:若δ()≥ ,则包含长至少是δ()地回路..设是一个(,)图,证明:()≥,则中有回路;()若≥,则包含两个边不重地回路..证明:若图不是连通图,则是连通图..设是个(,)图,试证:()δ()·δ()≤[()]([()]),若≡,,( )() δ()·δ()≤[()]·[()],若≡( ).证明:每一个自补图有或个顶点..构造一个有个顶点而没有三角形地三次图,其中≥..给出一个个顶点地非哈密顿图地例子,使得每一对不邻接地顶点和,均有≥.试求中不同地哈密顿回路地个数..试证:图四中地图不是哈密顿图..完全偶图,为哈密顿图地充分必要条件是什么?.菱形面体地表面上有无哈密顿回路?.设是一个(≥)个顶点地图.和是地两个不邻接地顶点,并且≥.证明:是哈密顿图当且仅当是哈密顿图..设是一个有个顶点地图.证明:若>δ(),则有长至少为δ()地路..证明具有奇数顶点地偶图不是哈密顿图..证明:若为奇数,则中有()个两两无公共边地哈密顿回路..中国邮路问题:一个邮递员从邮局出发投递信件,然后返回邮局.若他必须至少一次走过他所管辖范围内地每条街道,那么如何选择投递路线,以便走尽可能少地路程.这个问题是我国数学家管梅谷于年首先提出地,国外称之为中国邮路问题.p1Ean。
本试卷满分90分(计算机科学与技术学院07级)10分,每小题各1 分)B ,则A 等于什么?2. 设X 为集合,R 为X 上的偏序关系,计算U R ,等于什么?i 1(R )3. 把置换123456789分解成循环置换的乘积。
436987251((149) (2367) (58))4. 什么是无穷集合?(凡能与自身的一个真子集对等的集称为无穷集合)5 .设T 是一棵树,p 2,贝U p 个顶点的树T 至多有多少个割点?(p -2 )6. 设D 是一个有p 个顶点q 条弧的有向图,若D 是连通的,则q 至 少是多大? ( p -17. 设V {1,2, , n},则以V 为顶点集的无向图共有多少个?8.设V {1,2, , n},则以V 为顶点集的有向图共有多少个? 2p(p1))哈工大2008年秋季学期注 意 行 为 规 范一、填空(本题满分1.设A,B 是集合,若A B遵 守 考场纪 律(2 P (P 1)/29.每个有3个支的不连通图,若每个顶点的度均大于或等于2,则该图至少有多少个圈?( 3 )10.设T是一个正则二元树,它有n。
个叶子,则T有多少条弧?(2(n0-1 ))二、判断对错(本题满分10分,每小题各1分)1.设A,B是两个集合,则A B且A B不可能同时成立。
(错)2.在集合{1,2, ,10}上可以定义210个二元运算。
(错)3 . 设f:X Y , 若是可逆的。
(错)是一个集合,则上的自反和反自反的二元关系个数相同。
(对)5.设为一个有限字母表,上所有字(包括空字)之集记为。
则不是可数集。
(错)6.设G是一个(p,q)图,若q p,则G中必有圈。
(对)7.若G是一个(p,p)连通图,则G至多有p个生成树。
(对)8.设r 2,G是r正则图且顶点连通度为1,贝U (G) r。
(对)9.把平面分成p个区域,每两个区域都相邻,则p最大为5。
(错)10.有向图的每一条弧必在某个强支中。
习题集(一) 一、填空1.设}7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且(N :自然数集,E + 正偶数) 则 =⋃B A 。
2.A ,B ,C 表示三个集合,文图中阴影部分的集合表达式为 。
6.设A={1,2,3,4},A 上关系图为则 R 2 = 。
7.设A={a ,b ,c ,d},其上偏序关系R 的哈斯图为则 R= 。
8.图的补图为 。
二、选择2、下列集合中相等的有( )A .{4,3}Φ⋃;B .{Φ,3,4};C .{4,Φ,3,3};D . {3,4}。
3、设A={1,2,3},则A上的二元关系有()个。
A.23 ;B.32 ;C.332⨯;D.223⨯。
4、设R,S是集合A上的关系,则下列说法正确的是()R 是自反的;A.若R,S 是自反的,则SR 是反自反的;B.若R,S 是反自反的,则SR 是对称的;C.若R,S 是对称的,则SR 是传递的。
D.若R,S 是传递的,则S5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下t st spR=∈=则P(A)/ R=()<>A∧s(||||})(,{t|,A.A ;B.P(A) ;C.{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}};D.{{Φ},{2},{2,3},{{2,3,4}},{A}}6、设A={Φ,{1},{1,3},{1,2,3}}则A上包含关系“⊆”的哈斯图为()7、下列函数是双射的为()A.f : I→E , f (x) = 2x ;B.f : N→N⨯N, f (n) = <n , n+1> ;C.f : R→I , f (x) = [x] ;D.f :I→N, f (x) = | x | 。
(注:I—整数集,E—偶数集,N—自然数集,R—实数集)8、图中从v1到v3长度为3 的通路有()条。
A.0;B.1;C.2;D.3。
哈尔滨工业大学(威海)继续教育学院年春季学期集合与图论本科试题考试形式:开卷答题时间:90 分钟本卷面成绩站课程成绩100 %(所有答案必须写在答题纸上、标清题号)一、填空题(每空2分,计20分)1. 集合{0}的所有子集是______________。
2. 设A={1,2,3,{1,2},{3}},B={2,{1},{2,3}},则B- A=__________。
3. 有偏序集(N,≤),即自然数集N上的小于等于关系,N的子集A={2,3,6,8}的下确界和上确界分别是______、_______。
4. 设A={1,2,3,4,5,6},R={<1,5>,<2,3>,<2,6>,<3,2>,<3,6>,<5,1>, <6,2>,<6,3>}∪I A,则[1]=_____________,[2]=_______________。
5. n个顶点的有向完全图边数是______,每个顶点的度数是_____。
6. 设图G1=<V1, E1>和G2=<V2, E2>,若____________,则G2是G1的真子图;若____________,则G2是G1的生成子图。
二、简答题(每题 10 分,计 40 分)1. 设A是一个非空集合,问(1)A上是否存在一个既是等价关系又是偏序关系的关系?若不存在,请说明理由;若存在,请给出一个实例。
(2) A上是否存在一个既是自反的又是反自反的关系?若不存在,请说明理由;若存在,请给出一个实例。
2. 是否存在每个顶点的度数≥3且只有7条边的简单平面连通图?请说明理由。
3. 某公司来了9名新员工,工作时间不能互相交谈,为了尽快互相了解,他们决定利用每天吃午饭时间相互交谈,于是,每天吃午饭时他们围在一张圆桌旁坐下,他们是这样安排的,每一次每人的左右邻均与以前的人不同,问这样的安排法能坚持多久?4. 有向图D如图所示,(1) 给出D的邻接矩阵A;(2) D中长度为1, 2, 3, 4的通路各有多少条?其中回路分别为多少条?(3) D中长度小于或等于4的通路为多少条?其中有多少条回路?三、计算题(每题 10 分,计 20 分)1. 设A ={a, b, c, d},R 是A 上的二元关系,且R ={<a, b>, <b, a>, <b, c>, <c, d>},求r(R)、s(R)和t(R)。
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中都有两个人,他们在组内认识的人数恰好相等.。
秋季学期《集合论与图论》试题本试题满分90,平时作业分满分10分。
一、(10分,每小题1分)判断下列各命题真伪(真命题打“√”号,假命题打“×”号):1.从{1,2,3}到{4,5}共有9个不同的映射。
()2.从{1,2,3}到{4,5}共有5个不同的满射。
()3.从{4,5}到{1,2,3}共3个不同的单射。
()4.集合{1,2,…,10}上共有2100个不同的二元关系。
()5.如果A为可数集,则2A也是可数集合。
()6.欧拉图中没有割点。
()7.有向图的每一条弧必在某个强支中。
()8.P为正整数,Kp的顶点连通度为P-1。
()9.(P,P)连通图至少有2个生成树。
()10.每个有2个支的不连通图,若每个顶点的度均大于或等于2,则该图至少有2个圈。
()二、(20分,每小题2分)计算题。
对每一小题给出计算结果:1.{1,2,…,n}上有多少个反自反且对称的二元关系?()2.把置换123456789579413826⎛⎫⎪⎝⎭分解成循环置换的乘积。
()3.计算下面两个图G1和G2的色数。
()G1:G2:(答:G1的色数为,G2的色数为)4.设X为集合,R为X上的偏序关系,计算1iiR∞=等于什么。
()5.求下面的有向图D的邻接矩阵和可达矩阵。
D=-------------------:()6.一个有向图D=(V,A)满足什么条件是V到V的一个映射的图?()7.P个顶点的无向连通图G的邻接矩阵中至少有多少个1?()8.设X为n 个元素的集合,X上有多少个二元运算?()9.9个学生,每个学生向其他学生中的3个学生各送一张贺年卡。
确定能否使每个学生收到的卡均来自其送过卡的相同人?为什么?()10.某次会议有100人参加,每人可以是诚实的,也可能是虚伪的。
已经知道下面两项事实:(1)这100人中至少有一人是诚实的;(2)任两人中至少有一人是虚伪的。
问这100人中有多少人是诚实的?()三、(12分,每小题6分)1.设A、B、C和D都为非空集合。
集合论与图论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={2,a ,{3},4},B={Φ,4,{a},3},则A ⊕B= ;
⑵ 设A={2,3,4},则P (A )= ; ⑶ 设A={{2},{2,4}},则
A — A=
;
⑷ 设<x ,y+5>=<y+1,2x>,则x ,y= ;
⑸ 设A={0,1},B={1,2}则A ⨯B= ; ⑹ 设A={a ,b ,c ,d},则A 上所有 个二元关系; ⑺ 设A={a ,b ,c ,d},则I A = ; ⑻ 设R={<x ,y>∣x ,y ∈N ∧x+3y=12},则domR=
;
ranR= ;R R= ;R ↾{2,3,4,6}= ;R[{3}]= ;
⑼
112R R -⋃()= 112R R -⋂()= ; ⑽ A 上的等价关系是同时具有 性质的关系; ⑾ A 上的偏序关系是同时具有 性质的关系;
⑿ A 上的关系R 自反,反自反,对称,反对称、传递的充要条件是 ; ⒀ 设A={x ∣x 是单词“mathematics ”中的字母},则cardP (A )= ; ⒁ 已知A 、B 都是可数集,则card (A B )= ;card (A ⨯B )= ⒂ Z 、Q 、R 分别是整数集、有理数集、实数集,用 或者≈
将
A 是英文字母
的集合,B={x ∣x ∈Z 且2∣x},C=Q ,D={<x ,y>∣x ,y ∈R ,x+y=1},E=P (R )则A B C D E .
⒃ 根据自然数的集合定义,3 6= ,2 5= ;3-6= ,2-5= ; ⒄ 握手定理的内容是 ; ⒅ 设21,R R 是集合{}4,3,2,1=A 上的二元关系,其中{
}4
,2,2,11,11=R ,{
}2
,3,4,2,3,24,12=
R ,则21
R R
∙= ;
⒆ 设{}d c b a ,,,=A ,21,R R 是A 上的二元关系,=1R {d
d c b b b a
a ,,,,,,,
=
2R {
},,,,,,,,,a a b b b c c c d d
,则2R 是1R 的 闭包;
⒇设A={1,2,3,4},R 是A 上的二元关系,其关系矩阵为
⎪⎪⎪⎪⎪⎭
⎫
⎝
⎛=00
1100000011001
R
M
试求(1)R 的关系表达式;(2)Dom (R )和Ran (R ).
(21) 无向简单图是指 ;
(22) 度数列为(2,2,2,2,3,3,4,4)的一个简单图为 ;
(23) G 是n (n ≥1,n 奇数)阶无向简单图,G 与G 奇度顶点的个数 ; (24) 6阶3-正则图有 种不同构情况;
(25) G 是无向简单不连通图,则G 一定 ; (26) G 是二部图⇔G 中不含 ;
(27) G 是欧拉图⇔ ;
(28) 无向连通图含有欧拉回路的充分必要条件是_____________________.
(29)设G 是n 个结点的简单图,若G 中每对结点的度数之和__________,则G 一定是哈密顿图. 2、单项选择题
⑴ 在图E V G ,=中,结点总度数与边数的关系是( )
(A )()E i 2deg =υ; (B )()E i =υdeg ; (C )()E v
2deg =∑∈υυ; (D )()E v
=∑∈υυdeg
⑵ 设G 是n 个结点的无向完全图,则图G 的边数为( ); (A )()1-n n ; (B )()1+n n ; (C )
()2
1-n n ; (D )
()2
1+n n
⑶ 设E V G ,=为无向简单图,()G n V ∆=,为图G 中结点的最大度数,则有 (A )()n G <∆; (B )()n G ≤∆; (C )()n G >∆; (D )()n G ≥∆ ⑷ 图G 与G '的结点和边分别存在一一对应关系是G ≌G '(同构)的( ). (A )充分条件;(B )必要条件;(C )充分必要条件;(D )既非充分也非必要条件. ⑸ 无向图G 是欧拉图,当且仅当( )
(A )G 的所有结点的度数为偶数 (B ) G 的所有结点的度数为奇数 (C) G 连通且所有结点的度数为偶数 (D ) G 连通且所有结点的度数为奇数 3、 解答题
⑴ 一个班50的学生,在第一次考试中有26人得5分,在第二次考试中有21人得5分,两次都没得5分的有17人,那么两次考试都得5分的有多少人?
⑵ 写出集合A={1,3}到B={a}的所有二元关系. ⑶ A={0,1,2,3},R 是A 上的关系, R={<0,0>,<0,3>,<2,0>,<2,1>,<2,3>,<3,2>}
给出R 的关系矩阵和关系图,求出关系闭包r (R ),s (R ),t (R ). ⑷ 设R 为N ⨯N 上二元关系,∀<a ,b>,<c ,d>∈N ⨯N ,<a ,b> R <c ,d>⇔b=d
ⅰ)证明R 是等价关系;ⅱ)求商集N ⨯N/R. ⑸ 设A={1,2,3,4},R 为A ⨯A 上二元关系,∀<a ,b>,<c ,d>∈A ⨯A ,<a ,b> R <c ,d>⇔a+b=c+d ⅰ)证明R 是等价关系;ⅱ)求R 导出的划分.
⑹ A={1,2,3,4,5,6,7,8,9,10,11,12},≤为整除关系,画出哈斯图,
在偏序集<A , ≤>中求最大元、最小元、极大元、极小元,对于集合B ={3,4,5,6,7}求出B 的上界、下界、上确界、下确界.
⑺ 设<A , R >和<B ,S>是偏序集,在A ⨯B 上定义关系T 如下:
∀<a ,b>,<c ,d>∈A ⨯B , <a ,b> T <c ,d>aRc ∧bSd
证明T 是A ⨯B 的偏序关系. ⑻ 证明(0,1)≈[0,1]
⑼ 设集合A ,B ,C ,D 满足A ≈C ,B ≈D ,证明A ⨯B ≈C ⨯D ⑽ 设n 阶图G 中有m 条边,证明:δ(G )≤
2m n
∆(G )
⑾ 9阶无向图G 中,每个顶点的度数不是5就是6,证明G 中至少有5个6度顶点或至少有6个5度顶点. 证明 设5度顶点有m 个,则6度顶点有9-m 个,设m<6,且9-m<5。
则4<m<6,所以m=5,所以度数总和5⨯5+6⨯(9-5)=49,与握手定理矛盾
⑿ 设G 是n 阶自补图,证明:n =4k 或n =4k+1.
⒀ 设G 是n 阶n+1条边的无向图,证明G 中存在顶点v ,使得d (v )≥3.
⒁ 设G 是6阶无向简单图,证明G 或G 中存在3个顶点彼此相邻.(6个人中或者三人互相认识或者互相不认识)
证明 将6个人看作6个点,如果某两人互相认识,那么这两点相邻.
由此可以构成6阶无向简单图G 。
所以该问题证明变成G 中有3—圈或者G 有3—圈
()()i i d v d v =5G G + , ( i=1,2, ,6)()()11d v d v =5G G ∴+,
()()11d v d v G G ,中至少有一个大于等于3,
不妨设()1d v G ≥3,设v 2v 3v 4与v 1 相邻. 若v 2v 3v 4 某两点相邻,则这两点与v 1 构成3—圈.
若v 2v 3v 4 任两点都不相邻,则v 2v 3v 4 是G 中的3—圈.
⒂ 判别下面三幅图是否可以一笔画出?是欧拉图吗?若是,试写出一个回路。
解 ()()()是欧拉图
;通路,如一笔画出,一条欧拉存在欧拉通路,可以
;不能一笔画出c F EDBEFCABCD b a
142431321υυυυυυυυυd g h c e f b a 一个欧拉回路为
⒃ 指出下面各图是否哈密顿图,有无哈密顿通路,回路?
解 (a )是哈密顿图;
(b )只有哈密顿通路,不是哈密顿图,图中,,υu 有{}()3,1=-υu G P >{}2,=υu ; (c )不是哈密顿图,不存在哈密顿通路. 教材中的练习题:
P 14 15(3), 19(1),(2) 22, 24 P 38 5(3), 7(1)、(2), 17(1) P 53 14(1) ,15(1),16(2)
P65 5(1),(3), 6(1),(2) 11(1),(2),(3) P79 2(1),(4), 8(1),12、(1)、(2), 24,25 P131~135
14,20,22, 31,43(2), 46(1),47,48
P164 30,34,37
P292~295 6, 8, 24,25,29,35,39,44,50。