离散数学(第12讲)(免费阅读).pptVIP

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * 主要内容 1、关系的闭包 2、Warshall算法（用矩阵计算传递闭包） 3、闭包运算的性质 * 计算机学院 * §4.4 关系的闭包 设R是A上的关系，我们希望R具有某些有用的性质，比如自反性、对称性、传递性等。如果R不具有这些性质，可以通过在R中添加一些有序对来改造R，得到新关系R′，使R′具有上述性质，但又不希望R′与R相差太多，即添加的有序对要尽可能的少，满足这些要求的R′就称为R的闭包。 * 计算机学院 * ※定义4.7　设R是定义在A上的二元关系，若存在A上的关系R′满足： R′是自反的(或对称的、或可传递的)， R? R′， 对A上任何其它满足1）和2）的关系R〞，都有： R′? R〞。（表明R′的最小性） 则称R′为R的自反闭包(或对称闭包、或传递闭包)，分别记为r(R)(s(R)或t(R))。 * 计算机学院 * 例4-4.1 设集合A＝{a,b,c},R＝{a,b,b,b,b,c}是定义在A上的二元关系，求r(R),s(R),t(R),并画出R，r(R),s(R),t(R)的关系图和求出相应的关系矩阵。 解： r(R)＝{a,b,b,b,b,c,a,a,c,c}； s(R)＝{a,b,b,b,b,c,b,a,c,b}； t(R)＝{a,b,b,b,b,c,a,c}。 * 计算机学院 * 例4-4.1（续） * 计算机学院 * 利用关系图和关系矩阵求闭包 求一个关系的自反闭包，即将图中的所有无环的节点加上环；关系矩阵中对角线上的值rij全变为“1”。 求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条方向相反的另一条边；关系矩阵中则为：若有rij＝1(i≠j)，则令rji＝1(若rji≠1),即 。 求一个关系的传递闭包，则在图中，对任意节点a,b,c,若a到b有一条边，同时b到c也有一条边，则从a到c必增加一条边(当a到c无边时)；在关系矩阵中，若rij＝1，rjk＝1,则令rik＝1(若rik≠1)。 * 计算机学院 * 定理4.5 证明　3）可采用二种方法，一种是证明是传递闭包（按定义证明）；一种是直接证明 t(R)＝。 设R是集合A上的二元关系，则： r(R)＝R∪IA。 s(R)＝R∪R-1。 t(R)＝。 * 计算机学院 * 方法一、设R1＝ (1)显然R? =R1 。 (2)对任意a,b,c∈A，若a,b∈R1，b,c∈R1, (3)设R2是任何一个关系，且有R?R2?A×A，R2是传递的。对任意a,b∈R1，存在Rj(1≤j＜?)，使得a,b∈Rj，所以存在c1,c2,c3,…,cj-1∈A，使得： 则由R1＝，必存在Rj,Rk(1≤j,k＜?)，使得a,b∈Rj，b,c∈Rk，即a,c∈Rj+k(1≤j+k＜?), ∵Rj+k?R1,所以 a,c∈＝R1，即R1是传递的。 为什么？ * 计算机学院 * a,c1∈R,c1,c2∈R,c2,c3∈R,....,cj-1,b∈R。 因R?R2，所以 a,c1∈R2,c1,c2∈R2,c2,c3∈R2,…,cj-1,b∈R2。 由R2是传递的，有： a,c2∈R2,c2,c3∈R2,c3,c4∈R2,…,cj-1,b∈R2。 一直下去，最终有：a,b∈R2。 所以，R1?R2。 由(1),(2),(3)知：R1是R的传递闭包，即t(R)＝。 * 计算机学院 * 方法二、设t(R)是R的传递闭包，证明t(R)＝。 (1)证明t(R)?， ∵ 是可传递的，同时R? ∴ 由传递闭包的定义知： t(R)? 。 (2)证明?t(R)。只需证对任意的i∈N+,有Ri?t(R)。 当i＝1时，因R?t(R),所以结论成立。 设i＝k时，有Rk?t(R)结论成立。 当i＝k+1时，对任意a,b∈Rk+1，则存在c∈A，使得a,c∈Rk，c,b∈R由归纳假设有：a,c∈t(R)，c,b∈t(R)，由t(R)可传递，所以a,b∈t(R)， 即有：Rk+1?t(R)。 * 计算机学院 * 由(1)、(2)知：t(R)＝ 。■ 由归纳法知，对任意有的i∈N+,有Ri?t(R)。所以 ?t(R)。 * 计算机学院 * 定理4.6 设A是n个元素的集合，R是集合A上的二元关系，则?正整数k，k≤n，使t(R)＝ 。 这个定理为我们计算ｔ(Ｒ)减少了很多不必要的