(1.5.5)--ch3—第五讲离散数学离散数学.pdf
离离 散散 数数 学学 Discrete MathematicsDiscrete Mathematics 3-8 关系的闭包运算关系的闭包运算(Closure Operations)定义定义3.8.1 设非空集合设非空集合A上的二元关系上的二元关系R,若有若有A 上的另一个上的另一个 是自反的是自反的(对称的对称的,传递的传递的);R RR RR 则称关系则称关系 为为R的的自反自反(对称的对称的,传递的传递的)闭包闭包.R 分别记作分别记作:r(R),s(R),t(R).R 满足满足:二元二元关系关系 (1)(2)(3)对对A上任何包含上任何包含R的自反的自反(对称的对称的,传递的传递的)关系关系 R 都有都有 定理定理3.8.2 设设 R 是集合是集合 X 上的二元关系上的二元关系,IX 是集合是集合X上的上的 恒等关系恒等关系,则则 r(R)=RIX s(R)=RRc 23+1()=iit RRRRRR 例例1.设设A=a,b,c,R为为A上的二元关系上的二元关系,且且 解解:r(R)=RIA =,s(R)=RRc=,试求试求r(R),s(R)和和t(R).R=,R2=R R R3=R2 R iit RR1()=,=,R2=R R=,R3=R2 R=,=RR2R3=,R4=R3 R=,=R R5=R4 R=,=R2 R6=R5 R=,=R3 iit RR1()定理定理3.8.5 设设A是含有是含有n个元素的集合个元素的集合,R是是 A上的二元关系上的二元关系,则存在一个正整数则存在一个正整数kn，使得，使得 t(R)=RR2R3Rk 例例2.设设A=a,b,c,d,R为为A上的二元关系上的二元关系,且且 试求试求t(R).R=,解解:因为因为|A|=4,所以所以k4.R2=R R=,R3=R2 R=,=,t(R)=RR2R3 R4 R4=R3 R=,R=,R2=R R=,R3=R2 R=,利用关系矩阵求关系的闭包利用关系矩阵求关系的闭包 r(R)=RIX s(R)=RRc t(R)=RR2R3Rk 相应的关系矩阵有相应的关系矩阵有 Xr RRIMME()cTs RRRRRMMMMM()kt RRRRMMMM2()其中其中代表代表逻辑加逻辑加 例例7 设设 A=a,b,c,d,R=,求求 t(R).0100101000010000RM 2010001001010101010100101000100010000000000000000RM 解解 3101001000101010110101010000000010000000000000000RM 4010101001010101010100101000000010000000000000000RM t RRRRRMMMMM234()t(R)=,1111111100010000(1)置新矩阵置新矩阵 A:=M(4)i加加1;(5)如果如果in,则转到步骤则转到步骤(3),否则停止否则停止.当有限集当有限集 X 的元素较多时的元素较多时,对关系对关系R的传递闭包进行的传递闭包进行 矩阵运算很繁琐矩阵运算很繁琐,Warshall(沃舍尔沃舍尔)在在1962年提出了年提出了R+的的 一个有效算法一个有效算法:(2)置置 i:=1 则对则对k=1,2,n(3)对所有对所有 j,如果如果 A j,i=1;A j,k:=A j,k +A i,k )()().a rs Rsr R 定理定理3-8.6 设设R是集合是集合X上的二元关系，则上的二元关系，则 )()().b rt Rtr R)()().c ts Rst R 3-9 集合的划分与覆盖集合的划分与覆盖 定义定义3.9.1 设有非空集合设有非空集合A,S=S1,S2,Sm,其中其中 Si A,Si (i=1,2,m)且且 1,miiSA 称称 S 是集合是集合 A 的的覆盖覆盖.定义定义3.9.2 设有非空集合设有非空集合A,S=S1,S2,Sm,其中其中Si A,Si (i=1,2,m),若若(1)()ijSSij miiSA1(2)则称则称S是集合是集合A 的一个的一个划分划分，每个每个Si称为这个划分的一个分块称为这个划分的一个分块.定义定义3.9.1 若把一个集合若把一个集合A分成若干个叫做分块的分成若干个叫做分块的非空子集非空子集,使得使得A中的每个元素至少属于一个分块中的每个元素至少属于一个分块,那么这些分块的全体那么这些分块的全体构成的集合叫做构成的集合叫做A的一个的一个覆盖覆盖.如果如果A中的每个元素属于且仅属于一个分块中的每个元素属于且仅属于一个分块,那么这些分那么这些分块的全体构成的集合叫做块的全体构成的集合叫做A的一个的一个划分划分(或或分划分划).例例.设设A=a,b,c,d,判断下列子集族是否为判断下列子集族是否为A的划分或覆盖的划分或覆盖.(1)a,b,c,c,d (2)a,b,d (3),a,b,c,d (4)a,b,c,d (5)a,a,b,c,d (6)a,a ,b,c,d 不是不是A的划分的划分,但是但是A的覆盖的覆盖 既不是既不是A的划分的划分,也不是也不是A的覆盖的覆盖 既不是既不是A的划分的划分,也不是也不是A的覆盖的覆盖 既是既是A的划分的划分,也是也是A的覆盖的覆盖 不是不是A的划分的划分,但是但是A的覆盖的覆盖 既不是既不是A的划分的划分,也不是也不是A的覆盖的覆盖(7)a,b,c,d 既是既是A的划分的划分,也是也是A的覆盖的覆盖(8)a,b,c,d 既是既是A的划分的划分,也是也是A的覆盖的覆盖(6)S=a|x A称为称为A的的最大划分最大划分.说明说明:(1)若若S 是是 A的划分的划分,则则S 也一定是也一定是 A 的覆盖的覆盖.反之不成立反之不成立.(2)任意给定集合任意给定集合A的划分或覆盖的划分或覆盖不唯一不唯一.(3)给定了集合给定了集合 A 的划分或覆盖的划分或覆盖,则则 A 便唯一确定便唯一确定.(4)覆盖中各子集可重叠覆盖中各子集可重叠,划分则不然划分则不然.(5)以非空集以非空集 A为元素的集合为元素的集合S=A称为称为A的的最小划分最小划分.定理定理3.9.1 若若 A1,A2,Ar 与与 B1,B2,Bs 是同一集合是同一集合 A 的两种划分的两种划分,则交叉划分亦是原集合的一种划分则交叉划分亦是原集合的一种划分.定义定义3.9.3 若若 A1,A2,Ar 与与 B1,B2,Bs 是同一集合是同一集合A的的 两种划分两种划分,若对于每一个若对于每一个Aj 均有均有Bk使使Aj Bk,则则 A1,A2,Ar 称为是称为是 B1,B2,Bs 的的加细加细.定义定义3.9.3 若若 A1,A2,Ar 与与 B1,B2,Bs 是同一集合是同一集合A 的两种划分的两种划分,两种划分的两种划分的交叉划分交叉划分.定理定理3-9.2 任何两种划分的交叉划分任何两种划分的交叉划分,都是原来各划分的都是原来各划分的 一种一种加细加细.则其中所有则其中所有Ai Bj 组成的组成的集合集合,称为原来称为原来
