离散数学(图论部分)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={
(b) V={a,b,c,d,e}，E={(a,b),(a,c),(b,c),(d,e)}
画出上述图的图解。
解：略。
3. 试找出K3的全部子图，并指出哪些是生成子图。
解：K3共有17个子图。其他略。
4. 证明：在至少有2人的团体中，总存在2个人，他们在这个团体中恰有相同数
目的朋友。
解：在n个人的团体中，各人可能有的朋友数目为0, 1, 2, 3, …, n-1，共n个数，但其中0和n-1 不能共存，故n个人事实上可能的朋友数目只有n-1个。
由鸽巢原理，命题得证。
5.某次宴会上许多人互相握手。证明：必有偶数个人握了奇数次手。
证：以人为顶点，握手关系为邻接关系构造一个无向图。由图的性质，奇数度的顶点必为偶数个，即握了奇数次手的人数必为偶数。
6. 证明：Ramsey(3,4)=9。（提示：题1的推广）
证：在9个人中，不可能每个人都恰好认识其他的3个人（即图的9个顶点不
可能每个顶点的度都为3，否则违反图的奇数度的顶点必为偶数个的性质）。设x不会恰好认识其他的3个人（即deg(x)≠3），则在余下8人中：：(1) x至少认识其中4人，或(2) x至多认识其中2人（即至少不认识其中6人），两者必居其一。由题1的过程，命题得证。
7. 证明：图G=(V, E)，n=|V|，m=|E|。若m>1
2
(n-1)(n-2)，则G连通证：利用反证法。设G可分解为不连通的非空的两部分G1= (V1, E1 )、G2 = (V2, E2 )，并设n1=|V1|≠0，m1=|E1|，n2=|V2|≠0，m2=|E2|
则n=n1+n2，m=m1+m2
若G1为完全图，则m1=1
2n1(n1-1)，故m1≤1
2
n1(n1-1)
若G2为完全图，则m2=1
2n2(n2-1)，故m2≤1
2
n2(n2-1)
故：m= m1+m2
≤1 2n1(n1-1)+1
2
n2(n2-1)
=1
2
(n-1)(n-2)+(n1-1)(n1-n+1) 又：1≤n1≤n-1
故：(n1-1)(n1-n+1)≤0
即：m≤1
2(n-1)(n-2) 与条件m>1
2
(n-1)(n-2) 矛盾。
8. 证明：图G = ( V, E )，n=|V|，m=|E|。若G连通，则m≥(n-1)
证一：对n做归纳。
n=2时，m=1≥n-1成立
设n=k时，命题成立。
当n=K+1时，
由于G连通，任意顶点的度≥1；
(1) 若任意顶点的度≥2，则2m=∑deg(vi) ≥2n，此时m≥n>n-1，命题成
立。
(2) 否则，若有某顶点u的度为1，从图中去掉该顶点以及其关联边，得
到的新图
G1 = (V1, E1) 仍然连通，且n1=|V1|= n-1=K，m1=|E1|= m-1
由归纳假设，对图G1有m1≥(n1-1)
即m-1≥(n-1-1) 或m≥(n-1)
由归纳原理，命题得证。
证二：由于G连通，设T= ( V, E' ) 是G的一棵生成树，则|E'|=n-1，而m≥|E'|，故。
9. 证明：n个人中，若任何2人合在一起认识其他n-2个人，则他们可以排成一
排，使除首尾2人外，其余的人都和相邻的人认识。
证：以人为顶点，认识关系为邻接关系构造一个无向图，问题转化为讨论满足条件的图中Hamilton道路的存在性。
从图中任取2个顶点x和y，记deg(x,y) 为{x,y} 与其他顶点的邻接边数目。由题意，有deg(x,y)≥n-2，这里的n-2由除了x和y外的n-2顶点中每个顶点贡献一条与x或y邻接的边得到。
(1) 若x与y认识，则
deg(x)+deg(y) = deg(x,y)+2 ≥ n-2+2 = n > n-1
(2) 若x与y不认识，设x认识z，z≠y，由题意x与z合在一起认识包括y
的其他n-2个人，所以只能z也认识y，即在图中，顶点z与x和y同
时邻接。由之前deg(x,y) ≥ n-2的讨论可得：
deg(x,y) ≥ n-2+1 = n-1，
故deg(x)+deg(y) = deg(x,y) ≥ n-1
综上，对任意顶点x和y，有deg(x)+deg(y) ≥n-1，由Hamilton道路存
在的充分条件知图中存在一条Hamilton 道路，命题得证。
10. 用Warshall 算法求下图的道路矩阵：
解：见课件的举例。
11. 若树中恰有2个顶点的度为1，则此树为一条链。
证：设 T= (V, E) 为一棵树，n=|V|，m=|E|，则 m=n -1
故：deg()22(1)i i v V
v m n ∈==-∑ 且 deg (v i ) ≠0 (i =1..n)
不妨设 deg (v 1)= deg (v n )=1，
则 1
2deg()2(1)22(2)n i
i v n n -==--=-∑且 deg (v i ) >1 (i =2..n -1) 所以只能 deg (v i ) =2 (i =2..n -1)
即此树为从v 1到v n 的一条路。
12. 若树中有一顶点的度为k ，则树中至少有 k 个度为1的点。
证：设 T= (V, E) 为一棵树，n=|V|，m=|E|，则 m=n -1
故： 1deg()22(1)n i
i v m n ===-∑ 且 deg (v i
) ≠0 (i =1..n) 不妨设 deg (v n ) =k ，则 1
1deg()2(1)n i
i v n k -==--∑ 设树中有p 个度为1的顶点：deg (v n -1) = deg (v n -2)= deg (v n-p )=1
则
1
1deg()2(1)n p i i v p n k --=+=--∑ 或 1
1deg()2(1)n p i
i v n k p --==---∑ 对余下的n -p -1个顶点，每个顶点的度至少为2，即
1
1d e g ()2(1)
n p i
i v n p --=≥--∑ 所以 2(n -1)-k -p ≥ 2(n -p -1)
解不等式得：p ≥ k
13. 设连通图G=(V, E)，T=(V, E(T))和T'=(V, E(T'))是G的两棵不同生成树且
e∈E(T)-E(T')，则存在一条边e'∈E(T')-E(T)，使得T-e+e' 和T'-e'+e都是G的生成树。
证：从T中去掉边e，则T被分成不连通的两部分，设其顶点集分别为V1和V2。在T'中必存在连接V1和V2的边，记为e'∈E(T')。
∵e∈E(T)-E(T') 即e?E(T')
∴e'≠ e
又：若e'∈E(T)，则e不是T中割边，与T是一棵树矛盾。
∴e'?E(T) 即e'∈E(T')-E(T)
考察T+e'，e和e' 在其中唯一的回路上，因此T-e+e' 构成G的一棵生成树。
同理，考察T'+e，可知T'-e'+e也构成G的一棵生成树。
14. 设图G=(V, E)，定义δ(G)=min{deg(v), v∈V}为G的最小度（类似可以定义
?(G)=max{deg(v), v∈V}为G的最大度）。若G是简单图，δ(G) ≥ k，T是一棵含k条边的树，则在G中存在与T同构的子图。（提示：对k作归纳。）证：对k作归纳。
易知k=1时结论成立。
设k=p时结论成立。
当k=p+1时，
G是简单图，δ(G)≥p+1。设树T含p+1条边（p+2个顶点），v0是T的
一个叶子结点，u是v0的邻接点，其余顶点编号为v1~v p。记e=(u, v0)，
T0=T-e，则G和T0符合归纳假设的条件，G中存在与T0同构的子图
T0'。将T0'的p+1个顶点与T0的顶点对应，编号为u', v1'~v p'。
考察顶点u'，由于deg(u')≥p+1，可见u'至少与除了v1'~v p'之外的一
个点邻接。将该点编号为v0'，记e'=(u', v0')，构造的T'=T0'+e'与T同
V 1 V 2 V 3 V 4 V 5 构。
由归纳原理，命题得证。
15. 证明：n 阶图连通当且仅当r(B)=n -1
证：必要性：课件定理[3-2-3]的证明。
充分性：设此时G 的连通分支数为k ，则经行列互换，关联矩阵B 可写成一个对角分块阵：
120...00...000...k B B B B ??????=??????
，r(B)=r(B 1)+ r(B 2)+ … r(B k )
设 第i 个连通子图的阶为n i , i=1..k 。由必要性：r(B i )=n i -1。
故 11()(1)k k i i i i r B n n k n k ===-=-=-∑∑
由条件 r(B)=n -1，故 k=1。 即图是连通的。
16. 求下图生成树的数目：
解：构造关联矩阵B 划出B k ，应用Binet-Cauchy 定理得到生成树的数目|BB k T |=24
17. 试画出12硬币3次求伪的判断树。
解：略。
18. 证明：对2元正则树，m=2n 0-2，其中m 为边数，n 0为树叶数。 证：树有 m=n -1
二元树有 n 0 = n 2+1
二元正则树有顶点数 n = n 0+n 2
故： n = n 0+n 2 = n 0+(n 0-1)= 2n 0-1
m=n -1=2n 0-2
19. 有字符串 “state seat act tea cat set a cat” ，求其最短二进制编码。
解：统计字频，建立huffman 树，构造相应的huffman 编码。过程见课件举例。
20. 旅行商问题：用分支定界法、最近邻法、最近插入法、最远插入法求解：
423352294526384930342742354131∞?? ?∞ ? ?∞ ?∞ ? ?∞ ? ?∞??
解：精确解=194
最近邻法解=205
最近插入法解=203
最远插入法解=229
21. 求下图各点到v8的最短路径（提示：利用Dijkstra 算法）
解：将原图有向边反向得到新图，利用Dijkstra 算法求新图中V8
到各点的最
短路径。
22. 求PERT图中各点的缓冲时间。
解：略。见课件举例。
离散数学 第1章 习题解答
习题 1. 下列句子中，哪些是命题哪些不是命题如果是命题，指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗 ⑶不存在最大素数。 ⑷21+3＜5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以。 ⑾只有6是偶数，3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。 解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷，所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题； ⑵p：天气冷；q：我穿羽绒服； ⑶p：天在下雨；q：湿度很高； ⑷p：刘英上山；q：李进上山； ⑸p：王强学过法语；q：刘威学过法语； ⑹p：你看电影；q：我看电影； ⑺p：我看电视；q：我外出；r：我睡觉； ⑻p：天下大雨；q：他乘班车上班。 3. 将下列命题符号化。 ⑴他一面吃饭，一面听音乐。 ⑵3是素数或2是素数。 ⑶若地球上没有树木，则人类不能生存。
⑷8是偶数的充分必要条件是8能被3整除。 ⑸停机的原因在于语法错误或程序错误。 ⑹四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺如果a和b是偶数，则a+b是偶数。 解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q ⑵p：3是素数；q：2是素数；原命题符号化为：p∨q ⑶p：地球上有树木；q：人类能生存；原命题符号化为：p→q ⑷p：8是偶数；q：8能被3整除；原命题符号化为：pq ⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p ⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：pq。 ⑺p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p∧q→r 4. 将下列命题符号化，并指出各复合命题的真值。 ⑴如果3+3=6，则雪是白的。 ⑵如果3+3≠6，则雪是白的。 ⑶如果3+3=6，则雪不是白的。 ⑷如果3+3≠6，则雪不是白的。 ⑸3是无理数当且仅当加拿大位于亚洲。 ⑹2+3=5的充要条件是3是无理数。(假定是10进制) ⑺若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。 ⑻当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设p：3＋3＝6。q：雪是白的。 ⑴原命题符号化为：p→q；该命题是真命题。 ⑵原命题符号化为：p→q；该命题是真命题。 ⑶原命题符号化为：p→q；该命题是假命题。 ⑷原命题符号化为：p→q；该命题是真命题。 ⑸p：3是无理数；q：加拿大位于亚洲；原命题符号化为：pq；该命题是假命题。 ⑹p：2+3＝5；q：3是无理数；原命题符号化为：pq；该命题是真命题。 ⑺p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：pq；该命题是真命题。 ⑻p：王小红心情愉快；q：王小红唱歌；原命题符号化为：pq；该命题是真命题。 习题
离散数学图论与系中有图题目
离散数学图论与系中有图题目
————————————————————————————————作者：————————————————————————————————日期：
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。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章习题答案
#include
N=N/2; } while(!Empty(S)) { Pop(S,&e); printf("%d ",e); } } void main() { int n; printf("请输入待转换的值n：\n"); scanf ("%d",&n); conversion(n); }习题 1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？ (1)离散数学是计算机专业的一门必修课。 (2)李梅能歌善舞。 (3)这朵花真美丽！ (4)３＋２＞６。 (5)只要我有时间，我就来看你。 (6)x＝５。 (7)尽管他有病，但他仍坚持工作。 (8)太阳系外有宇宙人。 (9)小王和小张是同桌。 (10)不存在最大的素数。 解在上述10个句子中，(3)是感叹句，因此它不是命题。(6)虽然是陈述句，但它没有确定的值，因此它也不是命题。其余语句都是可判断真假的陈述句，所以都是命题。其中：(1)、(4) 、(8) 、(9) 、是简单命题，、(2) 、(5) 、(7)、(10) 是复合命题。 2.判断下列各式是否是命题公式，为什么？ (1)(P→(P∨Q))。 (2)(?P→Q)→(Q→P)))。 (3)((?P→Q)→(Q→P))。 (4)(Q→R∧S)。 (5)(P∨QR)→S。 (6)((R→(Q→R)→(P→Q))。 解 (1)是命题公式。 (2)不是命题公式，因为括号不配对。 (3)是命题公式。 (4)是命题公式。
离散数学测验题--图论部分(优选.)
离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝
图论习题课
一、填空题 1、对下列图，试填下表（是??类图的打〝√ 〞，否则打〝?〞）。 ① ② ③ 2、若图G=
6、极大可平面图的每一个面的次数都是_________． 7、5阶完全图的边连通度是． 8、图G是2-色的当且仅当G是． 二、选择题 1、下列无向图可能不是偶图的是( ) (A) 非平凡的树(B)无奇圈的非平凡图(C) n(1) n 方体图(D) 平面图 2、关于平面图，下列说法错误的是( ) (A) 简单连通平面图中至少有一个度数不超过5的顶点； (B)极大外平面图的内部面是三角形，外部面也是三角形； (C) 存在一种方法，总可以把平面图的任意一个内部面转化为外部面； (D) 平面图的对偶图也是平面图。 3、已知图G的邻接矩阵为 ，则G有（）． A．5点，8边B．6点，7边C．6点，8边D．5点，7边 4、设图G＝
A．deg(V)=2∣E∣B．deg(V)=∣E∣ C． E v V v 2 ) deg(= ∑ ∈D． E v V v = ∑ ∈ ) deg( 5、设完全图K n有n个结点(n≥2)，m条边，当（）时，K n中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数 6、设G是连通平面图，有v个结点，e条边，r个面，则r= ( )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 7、下列定义正确的是( )． A含平行边或环的图称为多重B不含平行边或环的图称为简单图 C含平行边和环的图称为多重D不含平行边和环的图称为简单图 8、以下结论正确是( )． A仅有一个孤立结点构成的图是零图B无向完全图Kn每个结点的度数是n C有n(n>1)个孤立结点构成的图是平凡图D图中的基本回路都是简单回路 9、下列数组能构成简单图的是( )． (A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3) 10、n阶无向完全图Kn中的边数为（）．
离散数学图论练习题
图论练习题 一.选择题 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
离散数学(图论部分)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={
离散数学答案(尹宝林版)第一章习题解答
第一章 命题逻辑 习题与解答 ⒈ 判断下列语句是否为命题，并讨论命题的真值。 ⑴ 2x - 3 = 0。 ⑵ 前进！ ⑶ 如果8 + 7 > 20，则三角形有四条边。 ⑷ 请勿吸烟！ ⑸ 你喜欢鲁迅的作品吗？ ⑹ 如果太阳从西方升起，你就可以长生不老。 ⑺ 如果太阳从东方升起，你就可以长生不老。 解 ⑶,⑹,⑺表达命题，其中⑶,⑹表达真命题，⑺表达假命题。 ⒉ 将下列命题符号化： ⑴ 逻辑不是枯燥无味的。 ⑵ 我看见的既不是小张也不是老李。 ⑶ 他生于1963年或1964年。 ⑷ 只有不怕困难，才能战胜困难。 ⑸ 只要上街，我就去书店。 ⑹ 如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐。 ⑺ 如果林芳在家里，那么他不是在做作业就是在看电视。 ⑻ 三角形三条边相等是三个角相等的充分条件。 ⑼ 我进城的必要条件是我有时间。 ⑽ 他唱歌的充分必要条件是心情愉快。 ⑾ 小王总是在图书馆看书，除非他病了或者图书馆不开门。 解 ⑴ p ：逻辑是枯燥无味的。 “逻辑不是枯燥无味的”符号化为 ?p 。 ⑵ p ：我看见的是小张。q ：我看见的是老李。 “我看见的既不是小张也不是老李”符号化为q p ?∧?。 ⑶ p ：他生于1963年。q ：他生于1964年。 “他生于1963年或1964年”符号化为p ⊕ q 。 ⑷ p ：害怕困难。q ：战胜困难。 “只有不怕困难，才能战胜困难”符号化为q → ? p 。 ⑸ p ：我上街。q ：我去书店。 “只要上街，我就去书店”符号化为p → q 。 ⑹ p ：小杨晚上做完了作业。q ：小杨晚上没有其它事情。 r ：小杨晚上看电视。s ：小杨晚上听音乐。 “如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐”符号化为s r q p ∨→∧。 ⑺ p ：林芳在家里。q ：林芳做作业。r ：林芳看电视。 “如果林芳在家里，那么他不是在做作业就是在看电视”符号化为r q p ∨→。 ⑻ p ：三角形三条边相等。q ：三角形三个角相等。
离散数学第二版邓辉文编著第一章第二节习题答案
离散数学第二版邓辉文编著第一章第二节习题答案 1.2 映射的有关概念 习题1.2 1. 分别计算?1. 5?，?-1?，?-1. 5?，? 1. 5?，?-1?，?-1. 5?. 解?1. 5?=2，?-1?=-1，?-1. 5?=-1，?1. 5?=1，?-1?=-1，?-1. 5?=-2. 2. 下列映射中，那些是双射? 说明理由. (1)f :Z →Z , f (x ) =3x . (2)f :Z →N , f (x ) =|x |+1. (3)f :R →R , f (x ) =x 3+1. (4)f :N ?N →N , f (x 1, x 2) =x 1+x 2+1. (5)f :N →N ?N , f (x ) =(x , x +1). 解 (1)对于任意对x 1, x 2∈Z ，若f (x 1) =f (x 2) ，则3x 1=3x 2，于是x 1=x 2，所以f 是单射. 由于对任意x ∈Z ，f (x ) ≠2∈Z ，因此f 不是满射，进而f 不是双射. (2)由于2, -2∈Z 且f (2) =f (-2) =3，因此f 不是单射. 又由于0∈N ，而任意x ∈Z 均有f (x ) =|x |+1≠0，于是f 不是满射. 显然，f 不是双射. (3)对于任意对x 1, x 2∈R ，若f (x 1) =f (x 2) ，则x 1+1=x 2+1，于是x 1=x 2，所以f 是单射. 对于任意y ∈R ，取x =(y -1) ，这时 1??3f (x ) =x +1=?(y -1) 3?+1=(y -1) +1=y ， ??33313 所以f 是满射. 进而f 是双射.
电大离散数学作业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=
屈婉玲版离散数学课后习题答案【1】
第一章部分课后习题参考答案 16设p、q的真值为0; r、s的真值为1,求下列各命题公式的真值。 (1) p V (q A r) 0V (0 A 1) 0 (2) (p? r )A (「q V s) (0? 1)A (1 V 1) 0A 1 0. (3) ( p A q A r) ? (p A q A「r) (1 A 1 A 1) ? (0 A 0A 0) 0 (4) ( r A s)—(p A q) (0A 1)—(1 A 0) 0—0 1 17 .判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则' 2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: 是无理数1 q: 3是无理数0 s: 6能被2整除1 r: 2是无理数 t: 6能被4整除0 命题符号化为：p A (q—r) A (t—s)的真值为1,所以这一段的论述为真 19.用真值表判断下列公式的类型： (4) (p—q) —( q—p) (5) (p A r) ( p A q) (6) ((p—q) A (q—r)) —(p—r) 答：(4) p q p—q q p q—p (p—q)—( q—p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式//最后一列全为 1 (5) 公式类型为可满足式(方法如上例) 〃最后一列至少有一个1 (6) 公式类型为永真式(方法如上例)// 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出 成真赋值.
⑴(p A q—q) (2) (p-(p V q))V (p-r) (3) (p V q)-(p A r) 答：⑵(p-(p V q))V (p-r) (p V (p V q))V ( p V r) p V p V q V r 1 所以公式类型为永真式 ⑶P q r p V q p A r (p V q)—(p A r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p - q) A (p -r) (p -(q A r)) ⑷(p A q) V ( p A q) (p V q) A (p A q) 证明(2) (p —q) A (p —r) (p V q) A ( p V r) p V (q A r)) p—(q A r) (4) (p A q) V ( p A q) (p V ( p A q)) A ( q V ( p A q) (p V p) A (p V q) A ( q V p) A ( q V q) 1 A (p V q) A (p A q) A 1 (p V q) A (p A q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)( p—q) —( q V p) ⑵(p —q) A q A r (3)(p V (q A r)) —(p V q V r) 解： (1)主析取范式 (p—q) —( q p) (p q) ( q p) (p q) ( q p) (p q) ( q p) ( q p) (p q) (p q)
离散数学图论习题
第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的图
离散数学第二版邓辉文编著第一章第二节习题答案
1.2 映射的有关概念 习题1.2 1. 分别计算??5.1，??1-，??5.1-，??5.1，??1-，??5.1-. 解 ??25.1=，??11-=-，??15.1-=-，??15.1=，??11-=-，??25.1-=-. 2.下列映射中，那些是双射? 说明理由. (1).3)(,Z Z :x x f f =→ (2).1||)(,N Z :+=→x x f f (3).1)(,R R :3+=→x x f f (4).1),(,N N N :2121++=→?x x x x f f (5)).1,()(,N N N :+=?→x x x f f 解 (1)对于任意对∈21,x x Z ，若)()(21x f x f =，则2133x x =，于是21x x =，所以f 是单射. 由于对任意∈x Z ，∈≠2)(x f Z ，因此f 不是满射，进而f 不是双射. (2)由于∈-2,2Z 且3)2()2(=-=f f ，因此f 不是单射. 又由于∈0N ，而任意∈x Z 均有01||)(≠+=x x f ，于是f 不是满射. 显然，f 不是双射. (3)对于任意对∈21,x x R ，若)()(21x f x f =，则113231+=+x x ，于是21x x =，所以f 是单射. 对于任意∈y R ，取3 1)1(-=y x ，这时 y y y x x f =+-=+??????-=+=1)1(1)1(1)(3313， 所以f 是满射. 进而f 是双射. (4)由于∈)1,2(),2,1(N ?N 且)1,2()2,1(≠，而4)1,2()2,1(==f f ，因此f 不是单射. 又由于∈0N ，而任意∈),(21x x N ?N 均有01),(2121≠++=x x x x f ，于是f 不是满射. 显然，f 就不是双射. (5)由于∈21,x x N ，若)()(21x f x f =，则)1,()1,(2211+=+x x x x ，于是21x x =，因此f 是单射. 又由于∈)0,0(N ?N ，而任意∈x N 均有)0,0()1,()(≠+=x x x f ，于是f 不是满射. 因为f 不是满射，所以f 不是双射.
离散数学图论与关系中有图题目
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。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)
离散数学及其使用图论部分课后习题答案
作业答案：图论部分 P165:习题九 1、给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形 表示。 （1），， 111,G V E =<>112345{,,,,}V v v v v v =11223343345{(,),(,),(,),(,),(,)} E v v v v v v v v v v =（2），，222,G V E =<>21V V =11223344551{(,),(,),(,),(,),(,)} E v v v v v v v v v v =（3）13331,,,D V E V V =<>=31223324551{,,,,,,,,,} E v v v v v v v v v v =<><><><><>（4）24441,,,D V E V V =<>=31225523443{,,,,,,,,,} E v v v v v v v v v v =<><><><><>解答：（1 ） （2 ） 10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样的图。 （1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个奇度顶点
。 14、设G 是阶无向简单图，是它的补图，已知，求 (2)n n ≥G 12(),()G k G k δ?==， 。 ()G ?()G δ解答：；。 2()1G n k ?=--1()1G n k δ=--15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。 解答： （c ）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1 （d ）同构，同构函数为 12()3 45 x a x b f x x c x d x e =??=??==??=?=??16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。 解答： （1）三条边一共提供6度；所以点度序列可能是 ①3，3，0，0，0，0；②3，2，1，0，0，0；③3，1，1，1，0，0；④2，2，2，0，0， 0；⑤2，2，1，1，0，0；⑥2，1，1，1，1，0；⑦1，1，1，1，1，1； 由于是简单图，①②两种情形不可能 图形如下：
离散数学图论部分经典试题及答案
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则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 的点割 ? ? ? ? ? c a b e d ? f 图四
离散数学测验题——图论答案
离散数学测验题——图论 1. (40分)下图1为某市地图，其中11个结点表示该市的所有城镇，结点间的边代表在城镇间可能建造的铁路线，边上的数字代表修造该段铁路的花费。 图 1 (1)试问如何建造铁路使得总开销最小并可连接所有城镇？（分别利用Kruskal 算法和Prim算法求解，并写明求解过程。要求从a点开始。）（20分） a) Kruskal算法求最小生成树： 根据权值将各边由小到大排序后，根据Kruskal算法得到如下最小生成树的求解过程：
最小生成树的求解过程如下：
(2)若该市的城镇j 将修建一旅游景点，同时拉动i 和k 两地的经济，因此修造j 到i 和k 的直接铁路线，尽管花费很高但仍十分必要。请求出加入此限制条件后（即边ij和jk要被选入）图1的最小生成树，并写明求解过程。（20分） a) 利用Kruskal算法求包含边ij和边j k的最小生成树： 根据权值将除去边ij和边jk的其它边由小到大排序后，根据Kruskal算法（不能形成圈）得到 如下最小生成树的求解过程：
b) 利用Prime算法求包含边ik和边j k的最小生成树： 将已经添加到生成树的集合设为{i, j, k}，再根据Prime算法，逐步在已经添加至生成树的顶 点集与未添加到生成树的顶点集之间找具有最小权值的边添加到生成树中，求解过程如下： 条？请写明计算过程。
图2 此有向图的邻接矩阵为???? ??? ??=01100011 0101 1000A ，则根据矩阵乘法可知 ??????? ??=??????? ?????????? ? ?=011 2110010110110 01 1000110101100001100011010110002A ?????? ? ??=??????? ?????????? ??=?=2112012112110112 011211001011011001100011010110002 3A A A ?????? ? ??=??????? ?????????? ? ?=?=2332 12131233211221 12 01211211011201100011010110003 4A A A ，将4A 中各元素记为(4) ,i j a 则所有4长的路的条数即为4 A 中所有元素之和，即4 (4) ,,1 i j i j a =∑=32（条），其中长度为4的回路的条数是4A 的所有对角线元素之和，即9条。 （注：对邻接矩阵A 的k 次方（一般的矩阵乘法）后，k A 中的任一元素() ,k i j a 表示从v i 到v j 的长度为k 的路的条数。） 3.（20分）用Dijstra 算法求图3中结点v 1到其它所有结点的最短路径及距离，并填写下表。
离散数学第一章命题逻辑知识点总结
数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为0 q：2 + 5 = 7，则q 的真值为1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q. ∧称作合取联结词，并规定p∧q为真当且仅当p与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题. 说明:
离散数学图论部分综合练习
离散数学 图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??????? ?????????010******* 000011100000100 则G 的边数为( )． A ．5 B ．6 C ．3 D ．4 2．下列数组中，能构成无向图的度数列的数组是( ) ． A ．(1, 1, 2, 3) B ．(1, 2, 3, 4, 5) C ．(2, 2, 2, 2) D ．(1, 3, 3) 3．设图G ＝
A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 8．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 9．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 10．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（ ）． A ．8 B ．5 C ．4 D ．3 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ． 2．设给定图G (如由图所示)，则图G 的点割集 是 ． 3．两个图同构的必要条件是它们的结点数相等、边数 相等以及 ． 4．设G=