离散数学测验题--图论部分(优选.)

图论练习题一.选择题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) 1618、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。

《离散数学》题库及标准答案《离散数学》题库及答案————————————————————————————————作者：————————————————————————————————日期：《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。

在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。

于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

页眉内容《离散数学》试题及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2），（3），（4），（5），（6）4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）PP⌝P→⌝↔（4）QQ→⌝（2）QP⌝→（3）Q8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( )(3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

离散数学图论答案【篇一：离散数学图论习题】综合练习一、单项选择题1．设l是n阶无向图g上的一条通路，则下面命题为假的是( )． (a) l可以不是简单路径，而是基本路径 (b) l可以既是简单路径,又是基本路径 (c) l可以既不是简单路径，又不是基本路径 (d) l可以是简单路径，而不是基本路径答案：a2．下列定义正确的是( )．(a) 含平行边或环的图称为多重图(b) 不含平行边或环的图称为简单图 (c) 含平行边和环的图称为多重图(d) 不含平行边和环的图称为简单图答案：d3．以下结论正确是 ( )．(a) 仅有一个孤立结点构成的图是零图 (b) 无向完全图kn每个结点的度数是n (c) 有n(n1)个孤立结点构成的图是平凡图(d) 图中的基本回路都是简单回路答案：d4．下列数组中，不能构成无向图的度数列的数组是( )． (a)(1,1,1,2,3) (b) (1,2,3,4,5) (c) (2,2,2,2,2) (d) (1,3,3,3) 答案：b5．下列数组能构成简单图的是( )． (a) (0,1,2,3)(b) (2,3,3,3)(c) (3,3,3,3)(d) (4,2,3,3) 答案：c6．无向完全图k3的不同构的生成子图的个数为（）． (a) 6 (b)5(c) 4 (d) 3 答案：c7．n阶无向完全图kn中的边数为（）．(a)n(n?1)n(n?1)(b) (c) n (d)n(n+1) 22答案：b8．以下命题正确的是( )．(a) n(n?1)阶完全图kn都是欧拉图(b) n(n?1)阶完全图kn都是哈密顿图(c) 连通且满足m=n－1的图v,e(?v?=n,?e?=m)是树 (d) n(n?5)阶完全图kn都是平面图答案：c10．下列结论不正确是( )．(a) 无向连通图g是欧拉图的充分必要条件是g不含奇数度结点(b) 无向连通图g有欧拉路的充分必要条件是g最多有两个奇数度结点 (c) 有向连通图d是欧拉图的充分必要条件是d的每个结点的入度等于出度(d) 有向连通图d有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等1于出度答案：d11．无向完全图k4是（）．（a）欧拉图（b）哈密顿图（c）树答案：b12．有4个结点的非同构的无向树有 ( )个．(a) 2 (b) 3(c) 4(d) 5 答案：a13．设g是有n个结点，m条边的连通图，必须删去g的( )条边，才能确定g的一棵生成树．(a) m?n?1 (b) n?m (c) m?n?1 (d) n?m?1 答案：a14．设g是有6个结点的完全图，从g中删去( )条边，则得到树． (a) 6 (b) 9 (c) 10 (d) 15 答案：c二、填空题1．数组{1，2，3，4，4}是一个能构成无向简单图的度数序列，此命题的真值是 . 答案：02．无向完全图k3的所有非同构生成子图有个．答案：43．设图g??v,e?，其中?v??n,?e??m．则图g是树当且仅当g是连通的，且m?．答案：n－14．连通图g是欧拉图的充分必要条件是答案：图g无奇数度结点 5．连通无向图g有6个顶点9条边，从g中删去g的一棵生成树t．答案：46．无向图g为欧拉图，当且仅当g是连通的，且g中无答案：奇数度7．设图g??v,e?是简单图，若图中每对结点的度数之和，则g一定是哈密顿图．答案：?8．如图1所示带权图中最小生成树的权是．答案：12三、化简解答题1．设无向图g＝v,e，v={v1，v2，v3，v4，v5，v6}， e={( v1，v2), ( v2，v2), ( v4，v5), ( v3，v4), ( v1，v3),( v3，v1), ( v2，v4)}． (1) 画出图g的图形；2图15图22(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，e，其中v＝{a,b,c,d,e}, e={(a,b),(b,c),(c,d), (a,e)}试作出图g的图形，并指出图g是简单图还是多重图？是连通图吗？说明理由.b e解：图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=23如图6．权为1+4+3+9+23=403．一棵树t有两个2度顶点，1个3度顶点；3个4问它有几片树叶？解：设t有n顶点，则有n－1条边．t中有2个 2度顶点，1个3度顶点，3个4度顶点，其余n－2－1-3个1度顶点．五、证明题1．若无向图g中只有两个奇数度结点，则这两个结点一定是连通的．证：用反证法．设g中的两个奇数度结点分别为u和v．假若u和v不连通．即它们之间无任何通路，则g至少有两个连通分支g1，g2，且u和v分别属于g1和g2，于是g1和g2各含有一个奇数度结点．这与握手定理的推论矛盾．因而u和v一定是连通的．3【篇二：离散数学图论练习题】题1、设g是一个哈密尔顿图，则g一定是()。

离散数学特殊图练习题一、基本概念与性质1. 判断下列说法是否正确：（1）完全图是连通图。

（2）树是一个无环的连通图。

（3）平面图一定可以画在一个平面上，使得任意两边都不相交。

2. 填空题：（1）一个有n个顶点的完全图的边数为______。

（2）一个有n个顶点的连通图至少有______条边。

（3）一个有n个顶点的树有______条边。

二、特殊图的判定1. 判断下列图是否为特殊图，并说明理由：（1）一个有5个顶点的图，其中每个顶点的度数分别为4, 4, 3, 3, 2。

（2）一个有6个顶点的图，其中每个顶点的度数都为3。

2. 下列图是否为平面图？请给出证明或反例：（1）K5（完全图K5）。

（2）K3,3（完全二部图K3,3）。

三、特殊图的性质与应用1. 计算下列图的色数：（1）一个有5个顶点的完全图。

（2）一个有6个顶点的环形图。

2. 下列图是否存在哈密顿回路？请给出证明或反例：（1）一个有5个顶点的环形图。

（2）一个有6个顶点的完全二部图。

四、综合题（1）若G为连通图，则G至少有n1条边。

（2）若G为平面图，则G的边数e ≤ 3n 6。

（1）完全图K6。

（2）完全二部图K3,3。

（3）一个有5个顶点的树。

3. 设G是一个有8个顶点的连通图，其中每个顶点的度数都为3。

证明：G至少有一个哈密顿回路。

五、图的同构与子图（1）图G1：顶点集{A, B, C, D}，边集{AB, AC, BC, BD, CD}；图G2：顶点集{P, Q, R, S}，边集{PQ, PR, QR, QS, RS}。

（1）一个有4个顶点的完全图。

（2）一个有5个顶点的星形图。

六、路径与距离（1）一个有6个顶点的环形图。

（2）一个有5个顶点的完全图。

（1）一个有6个顶点的路径图，顶点A和顶点B分别位于路径的两端。

（2）一个有7个顶点的图，顶点A和B不相邻，但通过其他顶点可以到达。

七、欧拉图与哈密顿图（1）一个有5个顶点的环形图。

第4章图论综合练习一、单项选择题1．设L是n阶无向图G上的一条通路，则下面命题为假的是( )．(A) L可以不是简单路径，而是基本路径(B) L可以既是简单路径,又是基本路径(C) L可以既不是简单路径，又不是基本路径(D) L可以是简单路径，而不是基本路径答案：A2．下列定义正确的是( )．(A) 含平行边或环的图称为多重图 (B) 不含平行边或环的图称为简单图(C) 含平行边和环的图称为多重图 (D) 不含平行边和环的图称为简单图答案：D3．以下结论正确是 ( )．(A) 仅有一个孤立结点构成的图是零图(B) 无向完全图K n每个结点的度数是n(C) 有n(n>1)个孤立结点构成的图是平凡图(D) 图中的基本回路都是简单回路答案：D4．下列数组中，不能构成无向图的度数列的数组是( )．(A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3)答案：B5．下列数组能构成简单图的是( )．(A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3)答案：C6．无向完全图K3的不同构的生成子图的个数为（）．(A) 6 (B) 5 (C) 4 (D) 3答案：C7．n阶无向完全图K n中的边数为（）．(A)2)1(+nn(B)2)1(-nn(C) n (D)n(n+1)答案：B8．以下命题正确的是( )．(A) n (n1)阶完全图K n都是欧拉图(B) n(n 1)阶完全图K n都是哈密顿图(C) 连通且满足m=n－1的图<V,E>(V=n,E=m)是树(D) n(n5)阶完全图K n都是平面图答案：C10．下列结论不正确是( )．(A) 无向连通图G是欧拉图的充分必要条件是G不含奇数度结点(B) 无向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点(C) 有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度(D) 有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等于出度 答案：D11．无向完全图K 4是（ ）．（A ）欧拉图 （B ）哈密顿图 （C ）树 答案：B12．有4个结点的非同构的无向树有 ( )个． (A) 2 (B) 3 (C) 4 (D) 5 答案：A13．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树．(A) 1+-n m (B) m n - (C) 1++n m (D) 1+-m n 答案：A14．设G 是有6个结点的完全图，从G 中删去( )条边，则得到树． (A) 6 (B) 9 (C) 10 (D) 15 答案：C二、 填空题1．数组{1，2，3，4，4}是一个能构成无向简单图的度数序列， 此命题的真值是 . 答案：02．无向完全图K 3的所有非同构生成子图有 个． 答案：43．设图G V ,E ，其中V n ,E m ．则图G 是树当且仅当G 是连通的，且m ． 答案：n －14．连通图G 是欧拉图的充分必要条件是 ． 答案：图G 无奇数度结点5．连通无向图G 有6个顶点9条边，从G 中删去 条边才有可能得到G 的一棵生成树T ． 答案：46．无向图G 为欧拉图，当且仅当G 是连通的，且G 中无 结点． 答案：奇数度7．设图>=<E V G ,是简单图，若图中每对结点的度数之和 ，则G 一定是哈密顿图．答案：V ≥8．如图1所示带权图中最小生成树的权是 ．答案：12三、化简解答题1．设无向图G ＝<V ,E >，V ={v 1，v 2，v 3，v 4，v 5，v 6}， E ={( v 1，v 2), ( v 2，v 2), ( v 4，v 5), ( v 3，v 4), ( v 1，v 3),( v 3，v 1), ( v 2，v 4)}． 1 v 2 v 6 v 53 v 4图2•2 23 • 1 • 7 9 2• 8 • 6 图1(1) 画出图G 的图形；(2) 写出结点v 2, v 4，v 6的度数； (3) 判断图G 是简单图还是多重图． 解：(1) 图G 的图形如图5所示．(2) 0)deg(,3)deg(,4)deg(642===v v v ．(3) 图G 是多重图．作图如图2. 2．设图G ＝<V ，E >，其中V ＝{a ,b ,c ,d ,e }, E ={(a ,b ),(b ,c ),(c ,d ), (a ,e )}试作出图G 的图形，并指出图G 是简单图还是多重图？是连通图吗？说明理由. 解：图G 如图8所示．. 图G 中既无环，也无平行边，是简单图． 图G 是连通图．G 中任意两点都连通.所以，图G 有9个结点．作图如图3．四、计算题1．设简单连通无向图G 有12条边，G 中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G 中有多少个结点．试作一个满足该条件的简单无向图．解：设图G 有x 个结点，由握手定理21+22+34+3（x 223）＝122 271821243=-+=x x ＝9 故图G 有9个结点．满足该条件的简单无向图如图4所示2．设图G (如图5表示)是6个结点a ,b ,c , d ,e ,f的图，试求，图G 的最小生成树，并计算它的权．解：构造连通无圈的图，即最小生成树，用克鲁斯克尔算法：第一步： 取ab ＝1；第二步： 取af =4 第三步： 取fe ＝3；第四步： 取ad =9 第五步： 取bc =23如图6．权为1+4+3+9+23=403．一棵树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 至少有两个连通分支G 1，G 2，且u 和v 分别属于G 1和G 2，于是G 1和G 2各含有一个奇数度结点．这与握手定理的推论矛盾．因而u 和v 一定是连通的．a b ec d 图3图4b • 23 1c • • a 4 • f 9 3d • •e 图6b •23 1 15 c • 25 •a 4 • f 28 9 16 3 d • 15 • e 图5。

离散数学考试题及答案一、选择题1. 关于图论的基本概念，以下哪个说法是正确的？A. 无向图中的边无方向性，有向图中的边有方向性。

B. 有向图中的边无方向性，无向图中的边有方向性。

C. 无向图和有向图都是由顶点和边组成的。

D. 无向图和有向图都只由边组成。

答案：A2. “若顶点集合为V，边集合为E，那么图G可以表示为G(V, E)”是关于图的哪个基本概念的描述？A. 图的顶点B. 图的边C. 图的邻接D. 图的表示方法答案：D3. 以下哪个命题是正确的？A. 若集合A和B互相包含，则A和B相等。

B. 若集合A和B相交为空集，则A和B相等。

C. 若集合A和B相等，则A和B互相包含。

D. 若集合A和B相等，则A和B相交为空集。

答案：C二、填空题1. 有一个集合A = {1, 2, 3, 4}，则集合A的幂集的元素个数为__________。

答案：162. 设A = {a, b, c}，B = {c, d, e}，则集合A和B的笛卡尔积为__________。

答案：{(a, c), (a, d), (a, e), (b, c), (b, d), (b, e), (c, c), (c, d), (c, e)}3. 若p为真命题，q、r为假命题，则合取范式(p ∨ q ∨ r)的值为__________。

答案：真三、计算题1. 计算集合A = {1, 2, 3, 4}和集合B = {3, 4, 5, 6}的交集、并集和差集。

答案：交集：{3, 4}并集：{1, 2, 3, 4, 5, 6}差集：{1, 2}2. 计算下列命题的真值：(~p ∨ q) ∧ (p ∨ ~q)，其中p为真命题，q为假命题。

答案：真四、证明题证明：对于任意集合A和B，如果A和B互相包含，则A和B相等。

证明过程：假设A和B互相包含，即A包含于B且B包含于A。

设x为集合A中的任意元素，则x也必然存在于集合B中，即x属于B。

同理，对于集合B中的任意元素y，y也属于集合A。

第12~13章图论部分例题精选例 1 下列各组数中,哪些能构成无向图的度数序列?哪些能构成无向简单图的度数序列?1 1,1,1,2,32 2,2,2,2,23 3,3,3,34 1,2,3,4,5 5 1,3,3,3解根据握手定理,非负整数序列d1,d2,…,dn 能构成无向图的度数序列当且仅当d1+d2+…+dn 为偶数,即由推论知,d1,d2,…,dn中奇度数结点的个数为偶数个。

而1,2,3, 5分别有4个,0个,4个,4个奇度数结点,所以可以构成无向图的度数序列。

而(4)中有3个奇度数结点,因而不能构成无向图的度数序列。

但这些图并不一定是简单无向图。

其中,1,2,3为简单无向图,(5)不是简单无向图。

因为,在(5)中,若存在无向简单图,是v1,v2,v3,v4,是G中四个顶点,其中,degv11, degv23, degv33, degv43,则结点v1 仅能与v2, v3, v4,之一相邻,不妨设v1与v2相邻,则除v2能达到度数3外, v3, v4都不能达到度数3.因为,简单图要求两个结点之间至多一条边相联结,所以, v3和v4外分别至多和v2与v4, v2与v3相邻,即degv3, degv4至多为2,与已知矛盾,因此,5不是无向简单图. 对应的图如6.1所示,其中1,2,3分别对应a,b,c,5对应d例2 下列各无向图中有几个结点?(1)16条边,每个结点的度数均为2;(2)21条边,3个度数为4的结点,其余结点的度数均为3;(3)24条边,每个结点的度数均相同。

解设该图的结点数为n,则由握手定理可知:,由上式可得 n=16,即该图有16个结点;由上式可得 n =13,即该图有13个结点;.①如果k1,则n48;②如果k2,则n24;③如果k3,则n16;④如果k4,则n12;⑤如果k6,则n8; ⑥如果k8,则n6;⑦如果k12,则n4;⑧如果k16,则n3;⑨如果k24,则n2;⑩如果k48,则n1.例3 已知无向简单图G有m条边,各结点的度数均为3.1 若m3n-6,证明G在同构意义下唯一,并求m和n;2 若n6,证明G在同构意义下不唯一.北师大2000年考研试题分析在图论中,对于简单无向图和简单有向图,若涉及到边和结点的问题,握手定理是十分有用的.解 1 由于各结点的度数均为3,现在有n个结点和m条边,所以由握手定理知:.又因为m3n-6,故可得m6,n4.此时所得的无向图如图6-2所示.该图是简单无向图中边最多的图,即为无向完全图K4.对于4个结点的完全图,在同构意义下是唯一的.2 若n6,由握手定理:故m9.此时有n6,m9,且每个结点的度数为3,此时对于简单无向图,6个结点,9条边及每个结点的度数为3的有如图6-3所示的两个非同构的图.因此,n6,m9,度数为3的无向图G在同构意义下是不唯一的.例4 无向图G有21条边,12个3度数结点,其余结点的度数均为2,求G 的阶数n.北大2001年考研试题解由握手定理:从而,n15,即该图有15个结点,则G的阶数n为15 例5 证明若无向图G 是不连通的,则G的补图是连通的.西南交大1999年考研试题证明: 设不连通的无向图GV,E仅有两个不连通的分支.将点集划分为两个子集V1u1,u2,…,ur和V2v1,v2,…,vs.同属一个子集的两结点是连通的即其间有无向通路,分属不同子集的两结点是不连通的.这样的图,以结点数n4为例来证明G的补图V,Ek-E是连通的,其图如图6-4a所示.任取点集V中的两结点,分两种情况讨论:2 ,即这两个结点属于图G的同一个连通分支.不妨假,如图6-4a,假设它们.在另一连通分中任取一,对照图6-4c中的结.显然因为两两均不在同一连通分支内,所以. 按照1的证明可知: 和因此可通过无向路相连通.由此可知,无论1,2都有G的补图是连通的,所以,对任意不连通的图G,其补图都是连通的.例6 已知n阶简单图G中有m条边,各顶点的度数均为3,又2nm+3,试画出满足条件的所有不同构的G.西南交大2000年考研试题解又2nm+3,即m2n-3故3n2m22n-34n-6故n6m2n-32×6-39此时有n6,m9且每个结点的度数为3,则不同构的图有两个,如图6.5所示.。

自考离散数学试题及答案一、选择题（每题2分，共20分）1. 在集合论中，下列哪个符号表示“属于”关系？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 命题逻辑中，下列哪个表达式表示“非”操作？A. ∧B. ∨C. ¬D. →答案：C3. 在下列哪个图论的术语中，表示图中任意两个顶点都相连？A. 无向图B. 有向图C. 完全图D. 二分图答案：C4. 布尔代数中，下列哪个操作是“或”？A. ∧C. ¬D. →答案：B5. 以下哪个是等价关系的属性？A. 自反性B. 对称性C. 反对称性D. 传递性答案：A6. 有限自动机中，状态可以被分为哪两种类型？A. 初始状态和终止状态B. 接受状态和拒绝状态C. 确定状态和非确定状态D. 静态状态和动态状态答案：B7. 在关系数据库中，下列哪个操作用于删除表中的行？A. INSERTB. DELETEC. UPDATED. SELECT答案：B8. 以下哪个是谓词逻辑中的量词？B. ∃C. ∧D. ∨答案：A9. 在命题逻辑中，德摩根定律描述了哪些逻辑运算的对偶性？A. ∧ 和∨B. ¬和→C. ¬和↔D. → 和↔答案：A10. 树的深度优先搜索（DFS）算法通常使用哪种数据结构来实现？A. 队列B. 栈C. 链表D. 哈希表答案：B二、填空题（每题3分，共30分）11. 在集合{1, 2, 3, 4, 5}中，子集的总数是_________。

答案：3212. 如果命题P为真，则命题P → Q的真值表中，Q的值必须为_________。

答案：真13. 在有向图中，一个顶点的入度是指_________。

答案：指向该顶点的边的数量14. 一个关系R(A, B, C)中，如果对于任意两个元组，当它们在属性A上的值相等时，它们在属性B和C上的值也相等，则称R具有_________。

答案：候选键15. 在布尔代数中，表达式(A ∧ B) ∨ (A ∧ ¬B)的结果是_________。

离散数学习题三参考答案第三节图论1.画出所有4个顶点的简单图。

解：本题这考虑连通图的情况。

共有5个不同构的图。

2.在某次宴会上，许多人互相握手，证明奇数次握手的人一定是偶数个。

解：设每个人看成一个顶点，两人握手看成两顶点间的一条边，每人握手的次数就是该顶点的度数，由定理1的推论2马上可得结论。

3.设图G＝（V，E）中有12条边，已知G中3度顶点的有3个，其余顶点的度数均小于3，问G中至少有多少个顶点？为什么？解：如图G不是连通图，那么12条边最多的顶点数是12×2=24；一个顶点的度数是3，则要减去2个顶点数，所以3度顶点的有3个，就要减去2×3-6个顶点；同样一个顶点的度数是2，则要减去1个顶点数；为了使顶点数最小，图必须是连通图，所以顶点数为2的顶点的个数是（12×2-3×3）÷2的整数部分等于7个，有一个顶点的度数是1，所以G中至少有的顶点数是3+7+1=11（个）。

4.n个运动队之间安排一项比赛，已赛完了n+1场，求证：一定存在这样一个队，它已经至少参加了3场比赛。

解：如果每个运动队都只赛了2场，则共赛了2n÷2=n<n+1，所以一定存在这样一个队，它已经至少参加了3场比赛。

5.下图表示用堤埂分割成很多小块的水稻田。

为了用水灌溉需要挖开一些堤埂（不能挖堤埂的交点）。

问最少要挖开多少条堤埂，才能使水浇灌到每小块稻田？第五题解：把每块田看成顶点，相邻的田同一条边连接，这题就是最小生成树问题。

因为有12块田地，所以最少要挖开11条堤埂，才能使水浇灌到每小块稻田。

（见上右图）6在下列图中，求一条欧拉通路。

解：略2，其中m为图的边数，n为图的顶7.证明：若G=〈V，E〉是简单图，则m≤Cn点数。

（7，9一样）解：顶点数相同的情况下，简单图的边数一定小于完全图的边数。

8.设G是一个连通图，不含奇数点，证明：从G中任意去掉一条边，得到的图仍是连通图。

1、一个7阶无向简单图，其结点的最大度数为（）A、5B、6C、7D、82、设G为7阶无向简单图，下列命题成立的是（）A、G的每个结点度数均为3B、G的每个结点度数均为5C、G的每个结点度数均为6D、G的每个结点度数均为73、由4个点3条边构成的无向简单图中，结点的最大度数为（）A、1B、2C、3D、44、(多选题)下列度数列，可以简单图化的是（）A、5,5,4,4,2,1B、5,5,4,1,1C、5,4,4,2,1D、5,4,3,2,2E、4,4,3,3,2,2F、4,3,2,1G、3,3,2,2,1,1H、3,3,3,1I、3,3,1,15、下列可作为4阶无向简单图的结点度数序列是（）A、1,2,3,4B、0,2,2,3C、1,1,2,2D、1,3,3,38、下列关于图的命题正确的是（）A、欧拉图都是哈密顿图B、哈密顿图都是欧拉图C、4阶以上的完全图都是欧拉图D、4阶以上的完全图都是哈密顿图9、下列关于欧拉图的描述正确的是（）A、K4是欧拉图B、K5是欧拉图C、完全图都是欧拉图D、K6是欧拉图13、一棵无向树有5片树叶，3个2度结点，其余都是3度结点，这棵树的结点数是（）A、10B、11C、12D、1314、G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去G的多少条边（）A、m-n+1B、m-nC、m+n+1D、n-m+115、一个n阶图不一定是树的是（）A、无回路的连通图B、无回路且有n-1条边C、n阶连通图D、有n-1条边的连通图16、下列6阶无向树的度数序列，对应不止一棵同构树的是（）A、1,1,1,1,2,4B、1,1,1,2,2,3C、1,1,2,2,2,2D、1,1,1,1,3,31、设5阶简单连通图G所有结点的度数之和为18，则G的结点的最大度数为_____，最小度数为______2、4阶完全图K4是平面图，其面数r为_____，记结点数为n，边数为m，则n-m+r=_______3、一个简单无向连通图，有n个结点，m条边，则边数m的最大值为_________，最小值为_______4、7阶无向简单图G，最多有________条边5、连通平面图G的每个面至少由5条边围成，则G的边数m与顶点数n满足的不等式关系为______________6、连通平面图G共有8个顶点，其平面表示中共有6个面，则边数为______7、如题的9阶无向图，需要添加边使其称为欧拉图，至少需要添加_____________和______________8、一棵n(n>2)阶无向树T，其最大度数⊿(T)的最小值为_____，最大值为________9、一棵7阶树T，其分支点最多有____个，最多有____片树叶10、无向完全图K8，需要删掉______条边才能得到生成树；无向完全图K9，需要删掉______条边才能得到生成树11、无向树有4个3度分支点，2个2度分支点，其余为树叶，则树叶数为______12、设无向树有8片树叶，1个4度分支点，其余都是3度分支点，则该树共有______个结点1、研究4阶完全图K4，判断其是否存在欧拉回路？是否存在哈密顿回路？如果存在，共有多少个非同构的回路？2、9阶无向图G中，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。

离散数学考试试题及答案离散数学考试试题及答案离散数学是计算机科学和数学中的一门重要学科，它研究的是离散的结构和对象。

离散数学的理论和方法在计算机科学、信息科学、通信工程等领域具有广泛的应用。

下面将为大家提供一些离散数学考试试题及答案，希望对大家的学习和复习有所帮助。

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的结果。

《离散数学》图论部分习题《离散数学》图论部分习题1.已知⽆向图G有12条边，6个3度顶点，其余顶点的度数均⼩于3，问G⾄少有⼏个顶点？并画出满⾜条件的⼀个图形. （24-3*6）/2 +6=92.是否存在7阶⽆向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶⽆向简单图G中最⼤度≤63.设d1、d2、…、d n为n个互不相同的正整数. 证明：不存在以d1、d2、…、d n为度序列的⽆向简单图.Max{d1，d2，…，dn}≥n，n阶⽆向简单图G中最⼤度≤n-14.求下图的补图.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.在什么条件下⽆向完全图K n为欧拉图？n为奇数时10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数；桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分⽀上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分⽀上只有⼀个奇度顶点，与握⼿引理⽭盾。

离散数学考试试题及答案一、选择题（每题2分，共20分）1. 在集合论中，以下哪个选项表示“属于”关系？A. ⊆B. ⊂C. ∈D. ⊇答案：C2. 以下哪个命题是真命题？A. p ∧ ¬pB. p ∨ ¬pC. p → ¬pD. ¬(p → q) → p答案：B3. 以下哪个选项是命题逻辑中的德摩根定律？A. ¬(p ∨ q) = ¬p ∧ ¬qB. ¬(p ∧ q) = ¬p ∨ ¬qC. ¬(p → q) = p ∧ ¬qD. ¬(p ∨ q) = ¬p ∨ ¬q答案：A4. 以下哪个选项是命题逻辑中的蕴含等价？A. p → q ≡ ¬p ∨ qB. p → q ≡ ¬q → ¬pC. p → q ≡ p ∨ ¬qD. p → q ≡ ¬p ∧ q答案：A5. 以下哪个选项是关系的性质？A. 反身性B. 对称性C. 传递性D. 所有选项都是答案：D6. 以下哪个选项是图论中的有向图？A. 无向图中的边没有方向B. 有向图中的边有方向C. 混合图中的边既有方向也有无方向D. 所有选项都是答案：B7. 在图论中，以下哪个选项是树的性质？A. 树是无环的B. 树是连通的C. 树是无向图D. 所有选项都是答案：D8. 以下哪个选项是布尔代数的基本运算？A. 与（AND）B. 或（OR）C. 非（NOT）D. 所有选项都是答案：D9. 以下哪个选项是组合数学中的排列？A. 从n个不同元素中取出m个元素的组合B. 从n个不同元素中取出m个元素的排列C. 从n个相同元素中取出m个元素的组合D. 从n个相同元素中取出m个元素的排列答案：B10. 以下哪个选项是集合论中的幂集？A. 一个集合的所有子集的集合B. 一个集合的所有真子集的集合C. 一个集合的所有超集的集合D. 一个集合的所有子集的个数答案：A二、简答题（每题10分，共30分）1. 简述命题逻辑中的等价命题是什么？答案：等价命题是指两个命题在所有可能的真值赋值下都具有相同真值的命题。

《离散数学》测试题答案测试题――离散数学一、选择题1、G是一棵根树，则（）。

A、G 一定是连通的B、G 一定是强连通的C、G只有一个顶点的出度为OD、G只有一个顶点的入度为12、下面哪个语句不是命题（）。

A、中国将成功举办2008年奥运会B、一亿年前地球发生了大灾难C、我说的不是真话D、哈密顿图是连通的3、设R是实数集合，在上定义二元运算*: a, b∈R, a*b=a+b-ab,则下面的论断中正确的是（）。

A、0是*的零元B、1是*的幺元C、0是*的幺元D、*没有等幂兀4、下面说法中正确的是（）。

A、所有可数集合都是等势的B、任何集合都有与其等势的真子集C、有些无限集合没有可数子集D、有理数集合是不可数集合5、无向完全图K3的不同构的生成子图有（）个。

A. 6B.5C. 4D. 36、下面哪一种图不一定是无向树？A、无回路的连通图B、有n个顶点n-1条边的连通图C、每对顶点间都有通路的图D、连通但删去一条边则不连通的图7、设集合A= {{1,2,3},{4,5},{6,7,8}},则下列各式为真的是（）。

A. 1 A B?{{4,5}} =AC. {1,2,3} AD. 二三A8、在有界格中，若一个元素有补元，则补元（）。

A、必惟一B、不惟一C、不一定惟一D、可能惟一9、设集合A={1,2,3,…,10},下面定义的哪种运算关于集合A是不封闭的？（）A、x*y=max{x,y}B、x*y=mi n{x,y}C、x*y=GCD（x,y）,即x,y的取大公约数D、x*y=LCM（x,y），即x,y的最小公倍数C.D.刁0 1 I10.集合X 中的关系 R 其矩阵是M = 1 1 0 ,则关于R 的论述中正确的是（）。

'1 1 JA 、R 是对称的B 、R 是反对称的C 、R 是反自反的D 、R 中有7个元素11. 下列各组数中，哪个可以构成无向图的度数列（）。

A.1，1，1，2，2B.2，2，2，2，3C.1，2，2，4，6D.2，3，3，312.是定义在Z 上的二元运算，一x,y ? Z,x ” y = xy ? X - y ,则“的幺元和零元分别是（）o A.不存在，0 B.0，1C.1 ,不存在D.不存在，不存在13.设f : N > N,N 为自然数，且H若X 为奇数f （X^ I-若X 为偶数2则f （0）和f （｛0｝）分别是（）。

离散数学（图）选择题您的姓名： [填空题] *_________________________________1. 每个图中结点度的总和等于边数的( )倍。

[单选题] *A.1B.2(正确答案)C.3D.42.有向图G是强连通图，当且仅当() [单选题] *A.图G中至少有一条通路B.图G中有通过每个顶点至少一次的通路C.图G中至少有一条回路D.图G中有通过每个顶点至少一次的回路(正确答案)3.有向图G=<V,E>，其中V={a,b,c,d,e,f}，E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是()。

[单选题] *A.弱连通图(正确答案)B.单向连通图C.强连通图D.不连通图[单选题] *A.B.C.D.(正确答案)5.无向图是欧拉图，则( )。

[单选题] *A.该无向图是连通图(正确答案)B.该无向图没有奇度顶点C.A和B同时成立D.以上全错5.无向图是欧拉图，则( )。

[单选题] *A.该无向图是连通图B.该无向图没有奇度顶点C.A和B同时成立(正确答案)D.以上全错6. 无向树简称()。

[单选题] *A.树(正确答案)B.森林C.结点D.以上全部错误7.设G是有n个结点，m条边的连通图，必须删去G的()条边，才能确定G的一棵生成树。

[单选题] *A. m-nB. m-n+1(正确答案)C. m+n+1D. n-m+18. 一个顶点入度为0，其余顶点入度为1的有向树称为()。

[单选题] *A.根树(正确答案)B.环C.孤立点D.分支点9. 图中没有边关联的顶点称为()。

[单选题] *A.孤立点(正确答案)B.顶点C.元素D.以上全部错误10. 无向图中，如果关联一对顶点的无向边多于1条，则这些边称为( )。

[单选题] *A.集合B.平行边(正确答案)C.序偶D.度11. 在一个图既有有向边又有无向边，该图是( )。