离散数学第2版答案pdf第七章

离散数学

第七章 计数

离散数学

7.1 基本计数原理1.加法原理 2.乘法原理

离散数学

加法原理加法原理又称为和计数原理，也称和规则，存在三种表 述形式，其本质是说，整体等于其部分之和。 ① 若集合X是不相交非空子集S1,S2,…,Sm的并，则 |X|= m

| Si 1

i

|

② 若E1,E2,…,Em是彼此互斥事件，并且E1发生有e1 种方式，E2发生有e2种方式，…,Em发生有em种方式， 则E1或E2或…或Em发生有e1+e2+…+em种方式。 应该指出的是，事件E1和E2互斥是说，E1和E2发生但两 者不能同时发生。

离散数学

③ 如果选择事物O1有n1种方法，选择事物O2 有n2种方法，…,选择事物Om有nm种方法， 并且选择诸事物方法不重叠，则选取O1或O2 或…或Om有n1+n2+…+nm种方法。

离散数学

加法原理

例7.1.1 一个学生想选修一门数学课或一门生 物学课，但不能同时选修两门课。如果该生对 5门数学课和3门生物学课具有选课条件，试问 该生有多少方式来选修课程？

离散数学

乘法原理

乘法原理又称有序计数原理，也称积规则，类 似加法原理，也有三种表述形式。 ① 若S1,S2,…,Sm是非空集合，则笛卡尔 m 积S1 S2 … Sm的元

离散数学

第七章 计数

离散数学

7.1 基本计数原理1.加法原理 2.乘法原理

离散数学

加法原理加法原理又称为和计数原理，也称和规则，存在三种表 述形式，其本质是说，整体等于其部分之和。 ① 若集合X是不相交非空子集S1,S2,…,Sm的并，则 |X|= m

| Si 1

i

|

② 若E1,E2,…,Em是彼此互斥事件，并且E1发生有e1 种方式，E2发生有e2种方式，…,Em发生有em种方式， 则E1或E2或…或Em发生有e1+e2+…+em种方式。 应该指出的是，事件E1和E2互斥是说，E1和E2发生但两 者不能同时发生。

离散数学

③ 如果选择事物O1有n1种方法，选择事物O2 有n2种方法，…,选择事物Om有nm种方法， 并且选择诸事物方法不重叠，则选取O1或O2 或…或Om有n1+n2+…+nm种方法。

离散数学

加法原理

例7.1.1 一个学生想选修一门数学课或一门生 物学课，但不能同时选修两门课。如果该生对 5门数学课和3门生物学课具有选课条件，试问 该生有多少方式来选修课程？

离散数学

乘法原理

乘法原理又称有序计数原理，也称积规则，类 似加法原理，也有三种表述形式。 ① 若S1,S2,…,Sm是非空集合，则笛卡尔 m 积S1 S2 … Sm的元

离散数学第七章检测题

一、 单项选择题（每小题2分，共20分）

1．下图中是哈密尔顿图的是( 2

)

2．下面给出的四个图中，哪个不是汉密尔顿图（ （4） ）．

3．下列是欧拉图的是( 2

)

4. 下列各图不是欧拉图的是（ 4 ）

5．设A(G

)是有向图G ,E的邻接矩阵，其第i列中“1”的数目为（ ）。 (C) (1)．结点vi的度数； (2)．结点vi的出度； (3)．结点vi的入度； (4)．结点vj的度数。 6．无向图G中有16条边，且每个结点的度数均为2，则结点数是( 2 )

(1)．8 (2)．16 (3)．4 (4)．32 7．设Ｇ＝ V,E 为无向图， 7,E 23，则Ｇ一定是（ （4） ）．

(1)．完全图； (2)．零图； (3)．简单图； (4)．多重图． 8．若具有n个结点的完全图是欧拉图，则n为( 2 ). (1)．偶数；(2)．奇数； (3)． 9； (4)． 10．

9．无向图G是欧拉图，当且仅当（ ）． (1)

(1)．G连通且所有结点的度数为偶数； (2)．G的所有结点的度数为偶

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

离散数学大连理工大学软件学院陈志奎教授办公室：综合楼411,Tel: 87571525实验室：教学楼A318/A323,Tel:87571620/24 Mobile: 13478461921 Email: zkchen@http://www.77cn.com.cn zkchen00@http://www.77cn.com.cn

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

第七章图论

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

7.4图的矩阵表示一、邻接矩阵 V, E,定义：设 G=ψ 是一个简单有向图，其中的=结点集合V{v1, v2, vn},并且假定各结点已经有了从结点v1到vn的次序。试定义一个n×n的矩阵A,使得其中的元素

ai j={01

当 vi, v j ∈E当 vi, v j E

(1)

则称这样的矩阵A是图G的邻接矩阵。

3/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极

离散数学第2版答案

【篇一：离散数学课后习题答案_屈婉玲(高等教育出版

社)】

txt>16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)? 0∨(0∧1) ?0

（2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0.

（3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1） ? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1

17．判断下面一段论述是否为真：“?是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: ?是无理数 1 q: 3是无理数 0 r: 2是无理数 1 s: 6能被2整除 1 t: 6能被4整除 0

命题符号化为： p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。

19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q)

（6）((p→q) ∧(q→r)) →(p→r) 答： （4）

p q p→q ?q?p?q→?p (p→q)→(?q→?p) 0 01 1

1 / 13

图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图

多重集合: 元素可以重复出现的集合 无序积: A &B ={(x ,y ) | x ∈A ∧y ∈B } 定义 无向图G =, 其中 (1) 顶点集V ≠?，元素称为顶点

(2) 边集E 为V &V 的多重子集，其元素称为无向边，简称边.

例如, G =如图所示, 其中V ={v 1, v 2, …,v 5}, E ={(v 1,v 1), (v 1,v 2),

(v 2,v 3), (v 2,v 3), (v 2,v 5), (v 1,v 5), (v 4,v 5)} ,

定义 有向图D =, 其中

(1) V 同无向图的顶点集, 元素也称为顶点

(2) 边集E 为V ?V 的多重子集，其元素称为有向边，简称边.

用无向边代替D 的所有有向边所得到的无向图称作D 的基图，右图是有向图，试写出它的V 和E

注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的

通常用G 表示无向图, D 表示有向图, 也常用G 泛指 无向图和有向图, 用e k 表示无向边或有向边.

V (G ), E (G ), V (D ), E (D ): G 和D 的顶点集, 边集. n 阶图:

1 / 13

图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图

多重集合: 元素可以重复出现的集合 无序积: A &B ={(x ,y ) | x ∈A ∧y ∈B } 定义 无向图G =, 其中 (1) 顶点集V ≠?，元素称为顶点

(2) 边集E 为V &V 的多重子集，其元素称为无向边，简称边.

例如, G =如图所示, 其中V ={v 1, v 2, …,v 5}, E ={(v 1,v 1), (v 1,v 2),

(v 2,v 3), (v 2,v 3), (v 2,v 5), (v 1,v 5), (v 4,v 5)} ,

定义 有向图D =, 其中

(1) V 同无向图的顶点集, 元素也称为顶点

(2) 边集E 为V ?V 的多重子集，其元素称为有向边，简称边.

用无向边代替D 的所有有向边所得到的无向图称作D 的基图，右图是有向图，试写出它的V 和E

注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的

通常用G 表示无向图, D 表示有向图, 也常用G 泛指 无向图和有向图, 用e k 表示无向边或有向边.

V (G ), E (G ), V (D ), E (D ): G 和D 的顶点集, 边集. n 阶图:

习题9

1. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。

证明：（1）先证结论：

因为G是简单图，所以G的结点度上限 max(d(v)) ≤ n-1, G图的总点度上限为 max(Σ(d(v)) ≤ n﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G是完全图 因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。 G是完全图 =〉 因为G是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数 。■

2. 设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）≥3。

证明：反证法，假设,则G的总点度上限为max(Σ(d(u)) ≤2 n，根据握手定理，图边的上限为max(m) ≤ 2n/2=n。与题设m = n+1，矛盾。因此，G中存在顶点u，d（u）≥3。■

3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）

习题 2.1

1．将下列命题符号化。

(1) 4不是奇数。

解：设A(x)：x是奇数。a：4。

“4不是奇数。”符号化为：¬A(a)

(2) 2是偶数且是质数。

解：设A(x)：x是偶数。B(x)：x是质数。a：2。

“2是偶数且是质数。”符号化为：A(a)∧B(a)

(3) 老王是山东人或河北人。

解：设A(x)：x是山东人。B(x)：x是河北人。a：老王。

“老王是山东人或河北人。”符号化为：A(a)B(a)

(4) 2与3都是偶数。

解：设A(x)：x是偶数。a：2，b：3。

“2与3都是偶数。”符号化为：A(a)∧A(b)

(5) 5大于3。

解：设G(x,y)：x大于y。a：5。b：3。

“5大于3。”符号化为：G(a,b)

(6) 若m是奇数，则2m不是奇数。

解：设A(x)：x是奇数。a：m。b：2m。

“若m是奇数，则2m不是奇数。”符号化为：A(a)→A(b)

(7) 直线A平行于直线B当且仅当直线A不相交于直线B。

解：设C(x,y)：直线x平行于直线y。设D(x,y)：直线x相交于直线y。a：直线A。b：直线B。

“直线A平行于直线B当且仅当直线A不相交于直线B。”符号化为：C(a,b) ¬D(x,y)

(8) 小王既聪明又用功，但身体不

第10章 图

第10章习题答案

1.解 (1)设G有m条边，由握手定理得2m＝?d(v)＝2＋2＋3＋3＋4＝14，所以G的边数7条。

v?V(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得?d(v)＝2m＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，

v?V其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。

2.证明 设v1、v2、?、vn表示任给的n个人，以v1、v2、?、vn为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G。由握手定理知

?d(v)＝3n必为偶数，从而n必为偶数。

kk?1n3. 解 由于非负整数列d＝(d1，d2，…，dn)是可图化的当且仅当?di≡0(mod 2)，所以(1)、(2)、

i?1n(3)、(5)能构成无向图的度数列。

(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。

(5)是不可简单图化的。若不然，存在无向图G以为1，3，3，3度数列，不妨设G中结点为v1、v2、

v3、v4，且d(v1)＝1，d(v2)＝d(v3)＝d