集合论与图论 离散数学 模拟题1
一．列式题。用谓词表示法表示如下集合：
1．所有偶数组成的集合A
A={x| x∈Z ∧x mod 2 =0}.
2．所有奇数组成的集合B
B={x| x∈Z ∧x mod 2 =1}.
3．10的整倍数组成的集合A
A={x| x∈Z ∧x mod 10 =0}.
4．5的整倍数组成的集合B
A={x| x∈Z ∧x mod 5 =0}.
5．方程x2-1=0的所有实数解的集合B。
B={x|x∈R ∧x2-1=0}
6．小于5的非负整数组成的集合A：A={x | x ∈N ∧x < 5 }.
二．判断题
1．（ F ）包含三个元素的集合A表示成：A=（1，2，3）。
2．（ F ）集合A ={1，2，3}与集合B ={2，3，1}是两个不同的集合。
3．（T ）R=Φ是一个二元关系。
4．（T ）设A= {1, 2, 3}，R= {<1, 1>, <2, 2>, <3, 3>, <1, 2>}，则R是A上自反的关系。5．（T ）设A= {1, 2, 3}，R= {<1, 1>, <1, 2>, <2, 1>}，则R是A上对称的关系。6．（T ）设A= {1, 2, 3}，R= {<1, 2>,<1, 3>}，则R是A上反对称的关系。
7．（T ）设A= {1, 2, 3}，R= {<1, 1>,<2, 2>}，则R是A上传递的关系。
8．（ F ）设A= {1, 2, 3}，R= {<1, 2>,<2, 3>}，则R是A上传递的关系。
9．（T ）R是R的子集。
10．（T ）设f：A→B是双射，则称f-1：B→A是它的反函数。这个反函数也是双射的。
三．计算题
1．求集合A={1, 2, 3} 的所有子集？
答：A的0元子集，只有一个Φ，
A的1元子集，即单元集，有三：{1}、{2}、{3}；
A的2元子集有三：{1，2}、{2，3}、{1，3}；
A的3元子集就是它本身{1,2,3} ，因为A就是三元集。
2．写出集合A={0,1,2,3}的幂集P(A)?
答：P(A)={Φ, {0}, {1}, {2}, {3},
{0,1},{0,2},{0,3}, {1,2}, {1,3}, {2,3},
{0,1,2,}, {0,1,3,} {0,2,3,}, {1,2,3},A }
3．设A={a,b,c},B={a},C={b,d},求A∪B, A∪C, A∩B,B∩C, A-B,B-A,A-C,B-C?
答：A∪B={a，b，c}，A∪C={a，b，c，d}，A∩B={a}，B∩C=Φ，A-B={b，c}，B-A=Φ，A-C={a,c}，B-C=B。
4．A={a，b，c}，B={b，d}，求A⊕B？
答：A⊕B={a，c，d}。
5．设E={a，b，c ，d}，A={a，b，c}，求~A？
答：~A={d}。
6．已知A={1,2}，求P(A) ? A？
答：P(A)={Φ,{1}, {2},{1,2}}，
P(A) ? A = {<Φ, 1>, <Φ, 2>,<{1}, 1>, <{1}, 2>,<{2}, 1>, <{2}, 2>,<{1,2}, 1>, <{1,2}, 2>,} 7．A={1,2,3,4},R={<1,1>, <1,2>, <2,3>, <2,4>, <4,2>}。求R的关系矩阵？
答：R的关系矩阵为：
8．关系R = {<1, 2>, <1, 3>, <2, 4>, <4, 3>},求关系R的定义域、值域和域？
答：R的定义域dom R = { 1，2，4 }，值域ran R= { 2，3，4 }，域fld R= { 1，2，3，4}。9．设A= {1, 2, .., 8},A上的关系R= {
解：对于元素1，有：1R1, 1R4, 1R7。所以，[1] = {1, 4, 7}。
对于元素2，有：2R2, 2R5, 2R8。所以，[2] = {2, 5, 8}。
对于元素3，有：3R3, 3R6。所以，[3] = {3, 6}。
对于元素4，有：4R4, 4R1, 4R7。所以，[4]= {4, 1, 7}= [1]。
对于元素5，有：5R5, 5R2, 5R8。所以，[5]= {5, 2, 8}= [2]。
对于元素6，有：6R6, 6R3。所以，[6]={6, 3}= [3]。
对于元素7，有：7R4, 7R1, 7R7。所以，[7]= {4, 1, 7}= [1] =[4]。
对于元素8，有：8R5, 8R2, 8R8。所以，[8]= {5, 2, 8}= [2] = [5]。
四．简答题。
1．判断以下关系的性质
对称的。但不是自反的，也不是传递的。
反自反的，反对称的。同时又是传递的。
反对称的，自反的，但不是传递的。五．证明题
?
?
?
?
?
?
?
?
?
?
?
?
=
1
1
1
1
1
R
M
1．设A= {1, 2, .., 8}, A 上的关系R= {
求证：R 是A 上的等价关系。
证明：因为对于所有的x ∈A ，有
x ≡ x (mod3) ，所以关系R 是自反的。
同时对于所有的x,y ∈A ，若x ≡ y (mod3) ，则有y ≡ x (mod3)，所以关系R 是对称的。 对于所有的x, y, z ∈ A ，若x ≡ y (mod3)， y ≡z (mod3)，则有 x ≡ z (mod3)，所以关系R 是传递的。
2．求证： 证明：
六．有穷集合计数题
1．某班有学生25人，其中会打篮球的有14人，会打排球的有12人，会打网球的有6人，有6人既会打篮球又会打排球，有5人既会打篮球又会打网球，还有2人三种球都会打。又已知6个会打网球的学生都会打另外一种球类（篮球或排球）。
问：什么球都不会打的学生有几人？
解：设A 、B 、C 分别表示会打排球、网球、篮球的学生的集合。则根据题意可画出文氏图：
假设：会打排球和网球，但不会打篮球的学生有x 人，只会打排球或篮球的学生分别有y 人和z 人，什么球都不会打的学生有k 人。
则由文氏图可知：x+2+3+0=6 ，y+x+2+4=12，z+4+2+3=14。
解得：x=1，y=5，z=5，k=5。
答：什么球都不会打的学生有五人。
七．化简题
解：根据吸收律，原式 2 x 0 y z
4 3 k A
B C
)))((())()((A C B A B A C B A --.
~)~()
~()~(~)()(A B A B A B A B A A A
B A A B A -=====-= φB
A B B A =-)(B A B B A B A E B A B B B A B
B A B B A =-∴====-)()()(~)()~()(
八．画图题
1．已知G = < V, E >,其中V = {v1, v2, v3, v4, v5 }, E = { (v1, v2), (v1, v2), (v1, v3), (v3, v2), (v3, v3), (v3, v4) }，画出图G.
2．画出4阶3条边的所有非同构的无向简单图.
答：4阶3条边的非同构的无向简单图有三个，其图如下：
九．判断下列各图是否是欧拉图？是否是哈密尔顿图？
答：1是欧拉图。1和4 是哈密尔顿图。
v1
v2
v3
v4
e1 e2
e3
e4
e5
e6
离散数学图论与系中有图题目
离散数学图论与系中有图题目
————————————————————————————————作者：————————————————————————————————日期：
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1)
离散数学图论练习题
图论练习题 一.选择题 1、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图(2) 树(3) 平面图(4)连通图 2、下面给出的集合中，哪一个是前缀码？() (1) {0，10，110，101111}(2) {01，001，000，1} (3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011} 3、一个图的哈密尔顿路是一条通过图中()的路。 4、设G是一棵树，则G 的生成树有( )棵。 (1) 0(2) 1(3) 2(4) 不能确定 5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 6、一棵无向树的顶点数n与边数m关系是()。 7、一个图的欧拉回路是一条通过图中( )的回路。 8、有n个结点的树，其结点度数之和是()。 9、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 10、n个结点的有向完全图边数是( )，每个结点的度数是( )。 11、一个无向图有生成树的充分必要条件是( )。 12、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 13、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 14、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 15、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设T是一棵树，则T是一个连通且( )图。 17、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 18、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12
离散数学期末试题及答案完整版
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).
离散数学测验题--图论部分(优选.)
离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝
离散数学图论部分综合练习
1 离散数学图论部分综合练习 1.设图G ＝
【浙江工商大学】《离散数学》期末考试题(B)
《离散数学》期末考试题(B) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为 ( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( )
离散数学图论部分综合练习
离散数学图论部分综合练习 1 ．设图G ＝
离散数学(图论部分)1-4章习题课
离散数学（图论部分）1-4章习题课 1. 证明：在10个人中，或有3人互相认识，或有4人互不认识。 证：设x为10人中之任意某人，则在余下9人中：(1) x至少认识其中4人，或(2) x至多认识其中3人（即至少不认识其中6人），两者必居其一。 (1) 若此x认识的4人互不相识，命题得证；否则，互相认识的2人加上x 构成互相认识的3人，命题得证。 (2) 若此x不认识的6人中有3人互相认识，命题得证；否则，由 Ramsey(3,3)=6知，此6人中至少有3人互不认识，此3人加上x为互 不认识的4人，命题得证。 2. 设(a) V={a,b,c,d}，A={
离散数学期末考试试题及答案
离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ
（2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={
离散数学图论复习
离散数学11春图论部分综合练习辅导 大家好！本学期的第二次教学辅导活动现在开始，本次活动主要是针对第二单元图论的重点学习内容进行辅导，方式同样是通过讲解一些典型的综合练习作业题目，帮助大家进一步理解和掌握图论的基本概念和方法． 图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法．教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等． 本次综合练习主要是复习这一单元的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题．这样的安排也是为了让同学们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习． 下面是本学期第4，5次形考作业中的部分题目． 一、单项选择题 单项选择题主要是第4次形考作业的部分题目． 第4次作业同样也是由10个单项选择题组成，每小题10分，满分100分．在每次作业在关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家要多练几次，争取好成绩．需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目． 1．设图G ＝
离散数学期末考试试题及答案
离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P
离散数学图论部分经典试题及答案
离散数学图论部分综合练习 一、单项选择题 1.设图G 的邻接矩阵为 ??? ???? ? ????? ???01010 1001000001 1100100110 则G 的边数为( ). A.6 B.5 C.4 D.3 2.已知图G 的邻接矩阵为 , 则G 有( ). A.5点,8边 B.6点,7边 C.6点,8边 D.5点,7边 3.设图G ＝
图三 7.设有向图(a )、(b )、(c )与(d )如图四所示,则下列结论成立的就是 ( ). 图四 A.(a )就是强连通的 B.(b )就是强连通的 C.(c )就是强连通的 D.(d )就是强连通的 应该填写:D 8.设完全图K n 有n 个结点(n ≥2),m 条边,当( )时,K n 中存在欧拉回路. A.m 为奇数 B.n 为偶数 C.n 为奇数 D.m 为偶数 9.设G 就是连通平面图,有v 个结点,e 条边,r 个面,则r = ( ). A.e －v ＋2 B.v ＋e －2 C.e －v －2 D.e ＋v ＋2 10.无向图G 存在欧拉通路,当且仅当( ). A.G 中所有结点的度数全为偶数 B.G 中至多有两个奇数度结点 C.G 连通且所有结点的度数全为偶数 D.G 连通且至多有两个奇数度结点 11.设G 就是有n 个结点,m 条边的连通图,必须删去G 的( )条边,才能确定G 的一棵生成树. A.1m n -+ B.m n - C.1m n ++ D.1n m -+ 12.无向简单图G 就是棵树,当且仅当( ). A.G 连通且边数比结点数少1 B.G 连通且结点数比边数少1 C.G 的边数比结点数少1 D.G 中没有回路. 二、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数就是 . 2.设给定图G (如图四所示),则图G 的点割 集就是 . 3.若图G=
《离散数学》期末考试试题
《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。
离散数学-期末考试卷-A卷
离散数学-期末考试卷-A卷
东莞理工学院城市学院（本科）试卷（A卷） 2013-2014学年第一学期 开课单位：计算机与信息科学系，考试形式：闭卷，允许带入场 科目：离散数学，班级：软工本2012-1、2、3 姓名：学号： 题序一二三四总分 得分 A评 卷人 一、单项选择题（每小题2分，共20分） 在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。 1. 下述不是命题的是( ) A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 2. 命题公式P→(P∨Q∨R)是( ) A. 永假的 B. 永真的 C. 可满足的
D. 析取范式 3. 命题公式﹁B→﹁A等价于( ) A. ﹁A∨﹁ B B. ﹁(A∨B) C. ﹁A∧﹁ B D. A→B 4．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A．?P∧Q B．P∧?Q C．P→?Q D．P∨?Q 5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）A．?x(A(x))∧B(x) B．??x( A(x)→?B(x) ) C．??x( A(x)∧B(X)) D．??x( A(x)∧?B(x) ) 6. 设有A={a,b,c}上的关系R={
7. 设A={1,2,3,4,5,6},B={a,b,c,d,e}，以下哪一个关系是从A到B的满射函数( ) A. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>} B. f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>} C. f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>} D. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>} 8．设简单图G所有结点的度数之和为10，则G一定有（） A．3条边B．4条边C．5条边 D．6条边 9．下列不．一定是树的是（） A．每对结点之间都有通路的图 B．有n个结点，n-1条边的连通图 C．无回路的连通图D．连通但删去一条边则不连通的图 10．下列各图中既是欧拉图，又是哈密顿图的是（）
电大离散数学作业5答案(图论部分)
离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {f} ． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 ． 5．设G=
离散数学图论习题
第4章图论 综合练习 一、单项选择题 1．设L是n阶无向图G上的一条通路，则下面命题为假的是( )． (A) L可以不是简单路径，而是基本路径 (B) L可以既是简单路径,又是基本路径 (C) L可以既不是简单路径，又不是基本路径 (D) L可以是简单路径，而不是基本路径 答案：A 2．下列定义正确的是( )． (A) 含平行边或环的图称为多重图 (B) 不含平行边或环的图称为简单图 (C) 含平行边和环的图称为多重图 (D) 不含平行边和环的图称为简单图 答案：D 3．以下结论正确是 ( )． (A) 仅有一个孤立结点构成的图是零图 (B) 无向完全图K n每个结点的度数是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阶无向完全图K n中的边数为（）． (A) 2)1 (+ n n (B) 2)1 (- n n (C) n (D)n(n+1) 答案：B 8．以下命题正确的是( )． (A) n (n1)阶完全图K n都是欧拉图 (B) n(n 1)阶完全图K n都是哈密顿图 (C) 连通且满足m=n－1的图
离散数学之图论
第四篇图论 自从1736年欧拉（L.Euler）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题。如迷宫问题、匿门博奕问题、棋盘上马的路线问题、四色问题和哈密顿环球旅行问题等，曾经吸引了众多的学者。图论中许多的概论和定理的建立都与解决这些问题有关。 1847年克希霍夫（Kirchhoff）第一次把图论用于电路网络的拓扑分析，开创了图论面向实际应用的成功先例。此后，随着实际的需要和科学技术的发展，在近半个世纪内，图论得到了迅猛的发展，已经成了数学领域中最繁茂的分支学科之一。尤其在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。 图论研究的课题和包含的内容十分广泛，专门著作很多，很难在一本教科书中概括它的全貌。作为离散数学的一个重要内容，本书主要围绕与计算机科学有关的图论知识介绍一些基本的图论概论、定理和研究内容，同时也介绍一些与实际应用有关的基本图类和算法，为应用、研究和进一步学习提供基础。
第4-1章无向图和有向图 学习要求：仔细领会和掌握图论的基本概论、术语和符号，对于图论研究的一些最基本的课题，如道路问题、连通性问题和着色的问题等，应掌握主要的定理内容和证明方法以及基本的构造方法，以便为下一章研究提供理论工具。学习本章要用到集合和线性代数矩阵运算的知识，特别是集合数和矩阵秩的概念。 §4-1-1 图的基本概念 图是用于描述现实世界中离散客体之间关系的有用工具。在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a指向点b的有向线段来代表客体a和b之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V和有向线的集合E构成的二元组（V，E）来描述。同样的方法也可以用来描述其它的问题。当我们考察全球航运时，可以用点来代表城市，用线来表示两城市间有航线通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道；当研究物质的化学结构时，可以用点来表示其中的化学元素，而用线来表示元素之间的化学键。在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连。从图形的这种表示方式中可以抽象出图的数学概念来。 一、图 定义4-1-1.1一个（无向）图G是一个二元组（V（G），E（G）），其中V （G）是一个有限的非空集合，其元素称为结点；E（G）是一个以不同结点的无序对为元素，并且不含重复元素的集合，其元素称为边。 我们称V（G）和E（G）分别是G的结点集和边集。在不致引起混淆的地方，常常把V（G）和E（G）分别简
离散数学期末考试题
《离散数学》复习题 一、单项选择题（每小题2分，共20分） 1、下列命题中是命题的是（ ） A 、 7>+y x B 、雪是黑色的 C 、严禁吸烟 D 、我正在说谎 2下列命题联结词集合中,哪个不是极小全功能集( )。 A 、{,}刭 B 、{,}刳 C 、{}- D 、{,}佼 3、下列公式中哪个不是简单析取式（ ）。 A 、p B 、p q ∨ C 、()p q ?∨ D 、p q ?∨? 4、设个体域{,}A c d =，公式()()x P x x S x ?∧?在A 中消去量词后应为（ ） A ()()P x S x ∧ B (()())(()( P c P d S c S d ∧∧∨ C ()()P c S d ∧ D ()() () (P c P d S c S d ∧ ∧∨ 5、下列是命题公式p ∧(q ∨┓r)的成真指派的是( ) A.110，111，100 B.110，101，011 C.所有指派 D.无 6、下列命题中（ ）是正确的。 A. 若图G 有n 个顶点，则G 的各顶点的度和为2n; B. 无向树中任意两点之间均相互可达； C. 若有向图G 是弱连通的，则它必定也是单向连通； D. 若无向带权图G 是连通的，则其最小生成树存在且唯一。
7、正整数集合Z +的以下四个划分中，划分块最多的是（ ） A ．1π={{x }︱x ∈Z + } B ．2π= {Z + } C. 3π={12,S S },1S 为素数集，21S Z S + =- D ．3π={12,S S ,3S },i S 为Z +中元素除以3的余数 8、给定下列各图： ⑴G 1=
离散数学图论与关系中有图题目
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8 个结点的三次正则图 (2) (1) (3) (2) (1)