当前位置：文档之家 › 离散数学作业5[答案]

离散数学作业5[答案]

  • 格式：pdf
  • 大小：273.49 KB
  • 文档页数：5

1 / 5
一、填空题
1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结
点，则G的边数是15 ．
2．设给定图G(如右由图所示)，则图G的点割集是
{f，c} ．
3．设G是一个图，结点集合为V，边集合为E，则
G的结点度数等于边数的两倍．
4．无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数．
5．设G=是具有n个结点的简单图，若在G中每一对结点度数之和
大于等于n-1 ，则在G中存在一条汉密尔顿路．
6．若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空
子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|
与W满足的关系式为W|S|．
7．设完全图K
n有n个结点(n2)，m条边，当n为奇数时，Kn
中

存在欧拉回路．
8．结点数v与边数e满足e=v-1 关系的无向连通图就是
树．
9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去
4 条边后使之变成树．
10．设正则5叉树的树叶数为17，则分支数为i = 4 ．

二、判断说明题（判断下列各题，并说明理由．）
1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．
不正确，图G是无向图，当且仅当G是连通，且所有结点度数均为偶数，
这里不能确定图G是否是连通的。

2．如下图所示的图G存在一条欧拉回路．

错误．
因为图G为中包含度数为奇数的结点．

3．如下图所示的图G不是欧拉图而是汉密尔顿图．

G
2 / 5

解：错，既不是欧拉图也不是汉密尔顿图，欧拉图要求所有结点度数均为
偶数，这里结点bd各有三个节点；汉密尔顿图要求每一对结点度数之和大于等
于总结点数，这里不满足。

4．设G是一个有7个结点16条边的连通图，则G为平面图．
错，没有提到面

5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．
对，由欧拉定理得到：结点-边+面=2 ，即为连通平面图，这里6-11+7=2

三、计算题
1．设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，
(v3,v5)，(v4,v5) }，试
(1) 给出G的图形表示；(2) 写出其邻接矩阵；
(3) 求出每个结点的度数；(4) 画出其补图的图形．

解：（1）G的图形如图十二

（2）邻接矩阵：
图十二

01100
10110
11011
01100
00100

（3）v
1，v2，v3，v4，v5
结点的度数依次为1，2，4，3，2

（4）补图如图十三：
3 / 5

2．图G=，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e),
(c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试
（1）画出G的图形；（2）写出G的邻接矩阵；
（3）求出G权最小的生成树及其权值．

解：（1）G的图形表示如图十四：

图十四
（2）邻接矩阵：

01111
10110
11001
11001
10110

（3）粗线表示最小的生成树，如图十五

如图十五
最小的生成树的权为1+1+2+3=7：

3．已知带权图G如右图所示．
(1) 求图G的最小生成树；(2)计算该生成树的权值．
4 / 5

4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优
二叉树的权．

四、证明题
1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的
补图G中的奇数度顶点个数相等．

2．设连通图G有k个奇数度的结点，证明在图G中至少要添加
2

k
条边才能

使其成为欧拉图．

证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．
5 / 5

又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度
结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数
变为偶数，成为欧拉图．

故最少要加2k条边到图G才能使其成为欧拉图．

合集下载

离散数学习题答案

离散数学习题答案

离散数学习题答案习题一及答案：（P14-15）14、将下列命题符号化：（5）李辛与李末是兄弟解：设p ：李辛与李末是兄弟，则命题符号化的结果是p（6）王强与刘威都学过法语解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是p q ∧（9）只有天下大雨，他才乘班车上班解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p →（11）下雪路滑，他迟到了解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→15、设p ：2+3=5.q ：大熊猫产在中国.r ：太阳从西方升起.求下列复合命题的真值：（4）()(())p q r p q r ∧∧⌝↔⌝∨⌝→解：p=1，q=1，r=0， ()(110)1p q r ∧∧⌝⇔∧∧⌝⇔，(())((11)0)(00)1p q r ⌝∨⌝→⇔⌝∨⌝→⇔→⇔()(())111p q r p q r ∴∧∧⌝↔⌝∨⌝→⇔↔⇔19、用真值表判断下列公式的类型：（2）()p p q →⌝→⌝解：列出公式的真值表，如下所示：20、求下列公式的成真赋值：（4）()p q q ⌝∨→解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10p q q ⌝∨⇔⎧⎨⇔⎩⇒00p q ⇔⎧⎨⇔⎩ 所以公式的成真赋值有：01，10，11。

习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）()()p q q r ⌝→∧∧解：原式()p q q r ⇔∨∧∧q r ⇔∧()p p q r ⇔⌝∨∧∧()()p q r p q r ⇔⌝∧∧∨∧∧37m m ⇔∨，此即公式的主析取范式，所以成真赋值为011，111。

6、求下列公式的主合取范式，并求成假赋值：（2）()()p q p r ∧∨⌝∨解：原式()()p p r p q r ⇔∨⌝∨∧⌝∨∨()p q r ⇔⌝∨∨4M ⇔，此即公式的主合取范式， 所以成假赋值为100。

《离散数学》作业参考答案

《离散数学》作业参考答案

Q→(P R) (P Q R) (P Q R) (P Q R) (P Q R) （ P Q R) ( P Q R) ( P Q R）（主析取范式）
7 (P→Q) (P→R) ( P Q) ( P R) (合取范式) ( P Q (R R) ( P ( Q Q) R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R)(主合取范式)
（P ( Q Q)） （( P P) Q） (P Q) （P Q） （ P Q） （P Q） (P Q) （P Q） （ P Q）（主析取范式） 2．Q→( P R) Q P R（主合取范式） （Q→( P R)） （ P Q R） （ P Q R） （ P Q R） （ P Q R） （P Q R）
E
（6）
(8)
E
前提
(9) E E
（7），（8）
8 、A→(C B)，B→ A，D→ C A→ D.
证明：
（1） A
附加前提
(2) A→(C B) 前提
(3) C B
（1），（2）
(4) B→ A
前提
(5) B
（1），（4）
(6) C
（3），（5）
(7) D→ C
前提
(8) D
( P (Q Q)) (( P P) Q) ( P Q) ( P Q) ( P Q) (P Q) ( P Q) ( P Q) (P Q)（主析取范式） 4． (P→Q) (R P) ( P Q) (R P) (P Q) (R P)（析取范式） (P Q (R R)) (P ( Q Q) R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R)（主析取范式） ( (P→Q) (R P)) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R)
(完整版)《离散数学》同步练习答案

(完整版)《离散数学》同步练习答案

华南理工大学网络教育学院《离散数学》练习题参考答案第一章命题逻辑一填空题（1)设：p：派小王去开会。

q：派小李去开会.则命题：“派小王或小李中的一人去开会" 可符号化为：（p q) (p q）。

（2）设A,B都是命题公式，A B，则A B的真值是T。

（3）设:p：刘平聪明。

q：刘平用功。

在命题逻辑中，命题：“刘平不但不聪明，而且不用功”可符号化为：p q .（4）设A , B 代表任意的命题公式，则蕴涵等值式为A B A B。

（5）设，p：径一事;q：长一智。

在命题逻辑中,命题:“不径一事，不长一智。

" 可符号化为： p q 。

（6）设A , B 代表任意的命题公式，则德摩根律为（A B）Û A B）。

（7）设，p：选小王当班长;q：选小李当班长.则命题：“选小王或小李中的一人当班长。

”可符号化为: （p q）（p q） .（8）设，P：他聪明；Q：他用功。

在命题逻辑中，命题:“他既聪明又用功。

" 可符号化为：P Q .（9）对于命题公式A,B,当且仅当 A B 是重言式时，称“A蕴含B”，并记为A B。

（10)设:P：我们划船.Q:我们跑步.在命题逻辑中，命题:“我们不能既划船又跑步.”可符号化为：（P Q) 。

（11）设P，Q是命题公式,德·摩根律为：（P Q）P Q) 。

（12）设P:你努力.Q：你失败。

在命题逻辑中，命题：“除非你努力，否则你将失败。

”可符号化为：P Q .（13）设p：小王是100米赛跑冠军。

q:小王是400米赛跑冠军。

在命题逻辑中，命题：“小王是100米或400米赛跑冠军.”可符号化为：p q。

（14）设A，C为两个命题公式，当且仅当A C为一重言式时,称C可由A逻辑地推出。

二．判断题1.设A，B是命题公式，则蕴涵等值式为A B A B。

（）2.命题公式p q r是析取范式。

( √ )3.陈述句“x + y > 5”是命题。

全版离散数学 练习题及答案.ppt

全版离散数学 练习题及答案.ppt


课件
例3 对任意两个集合A, B,试证 A (A B) A B
证明 对于任意的x
x A (A B)
x {x x A x ( A B)} x {x x A (x A B)} x {x x A (x A x B)} x {x x A (x A x B)} x {x x A x B}
课件
例10 求图的最小生成树
A 1B34 Nhomakorabea5
2 E
6
1A 2
B
E
4
6
C7 D
C
D
课件
例11
• 无向树T有7片树叶, 3个3度顶点,其余的 都是4度顶点，则T有几个4度顶点？
• 解:设T有x个4度顶点 顶点度数之和： 7+3*3+4x 由树的性质可得总边数： 7+3+x-1 由握手原理可得： 7+3*3+4x=2(7+3+x-1)
求g f
g f { 1,b , 2,b , 3,b }
课件
例12 求复合函数
X {1,2,3}, Y {p, q}, Z {a,b} f { 1, p , 2, p , 3, q } g { p,b , q,b }
求g f
g f { 1,b , 2,b , 3,b }
课件
例: 求幺元、零元、逆元
x A B 因为 x 是任意的,所以有
x ((x A (A B)) (x A B)) 的真值为T,
因此 A ( A B)课件 A B
例4 判断关系的性质
R1 { a, a , a,b , b,b , c,c }
a
1 1 0
M R 1 0 1 0
0 0 1