离散数学第七章

离散数学第七章计数

离散数学

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

离散数学

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

|Si1

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积S1S2…Sm的元素个数是|Si|i1②若事件E1,E2,…,Em发生分别有e1,e2,…,em种方式，并且诸事件是独立的，则事件E1或E2或··m依次发生有e1e2…em·或E种方式。

离散数学

乘法原理

③如果选取事物O1,O2,…,Om分别有n1,n2,…,nm种方法，并且选取诸事物方法不重叠，则事物O1与O2与…与Om依次选取有n1n2…nm种方法。

离散数学

乘法原理

例7.1.2一个学生要选修两门课，第一门课在上午4小时内任选1小时，第二门课在下午3小时内也可任选1小时，试问该生有多少种可能的时间安排？

离散数学 乘法原理

例7.1.3计数因特网地址。在由计算机的物理网络互连而构成的因特网中，每台计算机的网络连接被分配一个因特网地址。在网际协议版本IPV4中，一个地址是32位的位串，它以网络标识netid开始，后跟随主机标识hotid,该标识把一个计算机认定为某个指定网络成员。

列各组数中，那些能构成无向图的度数列？那些能构成无向简单图的度数列？

（1）1，1，1，2，3

（2）2，2，2，2，2

（3）3，3，3，3

（4）1，2，3，4，5

（5）1，3，3，3

解答：（1），（2），（3），（5）能构成无向图的度数列。

（1），（2），（3）能构成五项简单图的度数列。

设有向简单图D的度数列为2，2，3，3，入度列为0，0，2，3，试求D的出度列。

解：因为 出度=度数-入度，所以出度列为2，2，1，0。

设D是4阶有向简单图，度数列为3，3，3，3。它的入度列（或出度列）能为1，1，

1，1吗？

解：由定理可知，有向图的总入度=总出度。该有向图的总入度=1+1+1+1=4,总出度=2+2+2+2=8,4！=8，所以它的出度列（或入度列）不能为1，1，1，1。

35条边，每个顶点的度数至少为3的图最多有几个顶点？

解：根据握手定理，所有顶点的度数之和为70，假设每个顶点的度数都为3，则

n为小于等于370的最大整数，即：２３

∴ 最多有23个顶点

7.7 设n阶无向简单图G中，δ（G）=n-1，问△（G）应为多少？

解： 假设n阶简单图图n阶无向完全图，在Kn共有2)1(nn条边，各个顶点度数之和为n（n-1）

∴每个顶点的度数为nnn)1(=n-1

∴△（G）=δ（G）=n-1

一个n（n≥２）阶无向简单图Ｇ中，n为奇数，有r个奇度数顶点，问Ｇ的补图G中有几个奇度顶点？

解：在Kn图中，每个顶点的度均为（n-1），n为奇数，在Ｇ中度为奇数的顶点在G中仍然为奇数，

∴共有r个奇度顶点在G中

７.９ 设Ｄ是n阶有向简单图，Ｄ’是Ｄ的子图，已知Ｄ’的边数m’＝n（n-1），问Ｄ的边数m为多少？

解： 在Ｄ’中m’＝n（n-1） 可见Ｄ’为有个n阶有向完全图，则Ｄ＝Ｄ’ 即Ｄ’就是Ｄ本身，

第七章部分课后习题参考答案

7.列出集合A={2,3,4}上的恒等关系I A,全域关系EA,小于或等于关系LA,整除关系DA.

解：IA ={<2，2>,<3,3>,<4,4>}

EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}

LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}

DA={<2,4>}

13.设A={<1,2>,<2,4>,<3,3>}

B={<1,3>,<2,4>,<4,2>}

求AB,AB, domA, domB, dom(AB), ranA, ranB, ran(AB ), fld(A-B).

解：AB={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}

AB={<2,4>}

domA={1,2,3}

domB={1,2,4}

dom(A∨B)={1,2,3,4}

ranA={2,3,4}

ranB={2,3,4}

ran(AB)={4}

A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3}

14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}

求RR, R-1, R{0,1,}, R[{1,2}]

解：RR={<0,2>,<0,3>,<1,3>}

R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}

R{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}

R[{1,2}]=ran(R|{1,2})={2,3}

16．设A={a,b,c,d}，1R，2R为A上的关系，其中

1R=,,,,,aaabbd 2,,,,,,,Radbcbdcb

求23122112,,,RRRRRR。

第七章部分课后习题参考答案

7.列出集合A={2,3,4}上的恒等关系I A,全域关系EA,小于或等于关系LA,整除关系DA.

解：IA ={<2，2>,<3,3>,<4,4>}

EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}

LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,4>}

13.设A={<1,2>,<2,4>,<3,3>}

B={<1,3>,<2,4>,<4,2>}

求AB,AB, domA, domB, dom(AB), ranA, ranB, ran(AB ), fld(A-B).

解：AB={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}

AB={<2,4>}

domA={1,2,3}

domB={1,2,4}

dom(A∨B)={1,2,3,4}

ranA={2,3,4}

ranB={2,3,4} ran(AB)={4}

fld R=dom Rran R

A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3}

14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}

求RR, R-1, R{0,1,}, R[{1,2}]

解：RR={<0,2>,<0,3>,<1,3>}

R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}

R{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}

R[{1,2}]=ran(R{1,2})={2,3}

16．设A={a,b,c,d}，1R，2R为A上的关系，其中

1R=,,,,,aaabbd

2,,,,,,,Radbcbdcb

求23122112,,,RRRRRRoo。