《离散数学课件-第4章-5.ppt》由会员分享，可在线阅读，更多相关《离散数学课件-第4章-5.ppt（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、12023/1/27离散数学Discrete Mathematics&学习内容学习内容4.14.1集合的基本知识集合的基本知识集合的基本知识集合的基本知识4.2 序偶与笛卡尔积序偶与笛卡尔积4.3 4.3 关系及其性质关系及其性质关系及其性质关系及其性质4.4 n4.4 n元关系及其应用元关系及其应用元关系及其应用元关系及其应用4.5 4.5 关系的闭包关系的闭包关系的闭包关系的闭包4.6 4.6 等价关系等价关系4.7 偏序偏序&关系的关系的闭包包v关系的闭包是通过关系的复合和求逆构成关系的闭包是通过关系的复合和求逆构成的一个新的关系。的一个新的关系。v这里要介绍关系的自反闭包、对称闭包和这
2、里要介绍关系的自反闭包、对称闭包和传递闭包。传递闭包。2。31。2。32。32。32。3123123123这三个关系图分别是这三个关系图分别是R R的的自反、对称、传递闭包。自反、对称、传递闭包。一、关系的闭包一、关系的闭包1.定义：定义：给定给定 A中关系中关系R,若若A上另一个关系上另一个关系R，满足：满足：R R；R是自反的是自反的(对称的、传递的对称的、传递的)；R是是“最小的最小的”，即对于任何，即对于任何A上自反上自反(对称、传递对称、传递)的的 关系关系R,如果如果R R,就有就有R R。则称则称R是是R的的自反自反(对称、传递对称、传递)闭包。闭包。记作记作r(R)、s(R)、
3、t(R)(reflexive、symmetric、transitive)2.计算方法计算方法 1.给定给定 A中关系中关系R,则则 r(R)=R IA。proof：令令R=RR=RI IA A,显然显然RR是自反的和是自反的和R R R R，下面证明，下面证明RR是是“最小的最小的”：如果有：如果有A A上自反关系上自反关系R“R“且且R R R”,R”,又又I IA A R“,R“,所以所以 RRI IA A R”,R”,即即R R“R“。所以。所以RR就是就是R R的自反闭包。的自反闭包。即即r(Rr(R)=R)=RI IA A。2.给定给定 A中关系中关系R,则则 s(R)=R RC。证
4、明方法与证明方法与1 1类似。类似。【example】正整数集合上的关系正整数集合上的关系R=(a,b)|ab的对称闭包是的对称闭包是多少？多少？Solution：R的对称闭包是关系的对称闭包是关系 R RC=(a,b)|ab (b,a)|ab=(a,b)|ab二、有向图的路径二、有向图的路径 使用有向图表示关系有助于构造关系的传递闭包使用有向图表示关系有助于构造关系的传递闭包 。为此引入。为此引入一些需要用到的术语。一些需要用到的术语。通过沿有向图的边通过沿有向图的边(按照这条边的箭头指示的相同方向按照这条边的箭头指示的相同方向)移动有移动有向图就得到一条有向图中的向图就得到一条有向图中的路
5、径路径。定义定义1：在有向图在有向图G中从中从a到到b的一条的一条路径路径是是G G中一条或多条中一条或多条边的序列边的序列(x(x0 0,x,x1 1),(x),(x1 1,x,x2 2),(x),(x2 2,x,x3 3),),(x,(xn-1n-1,x xn n),),其中其中x x0 0=a,=a,x xn n=b.=b.即一个边的序列，其中一天的终点和路径中下一条边即一个边的序列，其中一天的终点和路径中下一条边的起点相同。这条路径记为的起点相同。这条路径记为x x0 0,x,x1 1,x,xn-1n-1,x xn n,长度为长度为n n。在同一定点开始和结束的路径叫做。在同一定点开始
6、和结束的路径叫做回路或圈回路或圈。注：注：有向图的一条路径可以多次通过一个顶点。此外，有有向图的一条路径可以多次通过一个顶点。此外，有向图的一条边也可以多次出现在一条路径中。向图的一条边也可以多次出现在一条路径中。【example】下面哪些路径是图下面哪些路径是图9的有向图中的路径：的有向图中的路径：a，b，e，d；a，e，c，d，b；b，a，c，b，a，a，b；d，c；c，b，a；e，b，a，b，a，b，e这些路径的长度是多少？这个列表中的哪些路径是回路？这些路径的长度是多少？这个列表中的哪些路径是回路？Solution：因为因为(a，b)、(b，e)和和(e，d)都是边，都是边，a,b,e
7、,d是长为是长为3的路径的路径 因为因为(c，d)不是边，不是边，a,e,c,d,b不是路径。不是路径。因为因为(b，a)，(a，c)，(c,b)，(b,a)，(a,a)和和(a,b)都是边，都是边，b，a，c，b，a，a，b是长为是长为6的路径。的路径。我们也看到，因为我们也看到，因为(d,c)是边，是边，d,c是长为是长为1的路径。的路径。还有由于还有由于(c,b)和和(b,a)是边，是边，c,b,a是长为是长为2的路径。的路径。(e,b)，(b，a)，(a，b)，(b，a)，(a，b)，(b，e)都是边都是边，因此，因此e，b，a，b，a，b，e是长为是长为6的路径。的路径。两条路径两条
8、路径b，a，c，b，a，a，b和和e，b，a，b，a，b，e是回路，因为它们在同一顶点开始和结束。是回路，因为它们在同一顶点开始和结束。路径路径a，b，e，d；c，b，a；d，c不是回路不是回路把有向图的定义推广到关系可知，如果存在一个元素的把有向图的定义推广到关系可知，如果存在一个元素的 序序列列a,x1,x2,xn-1,b 具有具有(a,x1)R,(x1,x2)R,(xn-1,xn)R,那么在那么在R中存在一条从中存在一条从a到到b的路径。的路径。从关系中的路径定义可以得到定理从关系中的路径定义可以得到定理1 1。定理定理1：设：设R是集合是集合A上的关系。从上的关系。从a到到b存在一条长
9、为存在一条长为1的路径，的路径，当且仅当（当且仅当（a，b）Rn。Proof：使用数学归纳法证明。使用数学归纳法证明。根据定义，从根据定义，从a到到b存在一条长为存在一条长为1的路径，当且仅当的路径，当且仅当（a，b）R。因此当。因此当n=1时定理为真。时定理为真。假定对于正整数假定对于正整数n定理为真，这是归纳假设。从定理为真，这是归纳假设。从a到到b存存在一条长为在一条长为n+1的路径，当且仅当存在元素的路径，当且仅当存在元素c A使得从使得从a到到c存在一条长为存在一条长为1的路径，即的路径，即(a,c)R,以及一条从以及一条从c到到b的长为的长为n的路径，即的路径，即(c,b)Rn.因
10、此由归纳假设，从因此由归纳假设，从a到到b存在一条长为存在一条长为n+1的路径，当的路径，当且仅当存在一个元素且仅当存在一个元素c，使得，使得(a,c)R和和(c,b)Rn。但是。但是存在这样一个元素，当且仅当存在这样一个元素，当且仅当(a,b)Rn+1。因此，从因此，从a到到b存在一条长为存在一条长为n+1的路径，当且仅当的路径，当且仅当(a,b)Rn+1。定理得证。定理得证。三、传递闭包三、传递闭包定义定义2：设设R是集合是集合A上的关系。上的关系。连通性关系连通性关系R*由对由对(a,b)构成构成，使得在，使得在R中从顶点中从顶点a到到b之间存在一条至少长为之间存在一条至少长为1的路径。
11、的路径。因为因为Rn由对由对(a,b)构成，使得存在一条从构成，使得存在一条从a到到b的长度为的长度为n的的路径，从而路径，从而R*是所有集合是所有集合Rn的并。的并。换句话说，换句话说，许多模型都用到连通性关系。许多模型都用到连通性关系。【example】设设R是世界上所有人的集合上的关系，如果是世界上所有人的集合上的关系，如果a认识认识b，那么，那么R包含包含(a,b).Rn是什么？其中是什么？其中n是大于是大于2的正整数。的正整数。R*是什是什么？么？Solution：如果存在如果存在c使得使得(a,c)R且且(c,b)R即存在即存在c使得使得a认识认识c，c认识认识b，那么关系，那么关
12、系R2包含包含(a,b).类似地如存在类似地如存在x1,x2,xn-1使得使得a认识认识x1,x1认识认识x2,xn-1认识认识b，那么，那么Rn包含对包含对(a,b).如果存在从如果存在从a开始至开始至b终止的序列，使得序列中的每个人都认终止的序列，使得序列中的每个人都认识序列中的下一个人，那么识序列中的下一个人，那么R*包含对包含对(a,b).【example】设设R是纽约市所有地铁站集合的关系。如果可以从是纽约市所有地铁站集合的关系。如果可以从a站不换车旅行到站不换车旅行到b站，那么站，那么R包含对包含对(a,b),当当n是正整数时，是正整数时，Rn是什么？是什么？R*是什么？是什么？S
13、olution:如果换如果换n-1次车就可以从次车就可以从a站旅行到站旅行到b站，关系站，关系Rn就包含就包含(a,b)。从。从a站旅行到站旅行到b站，如果需要可以换车任意多次，关系站，如果需要可以换车任意多次，关系R*就由就由这种有序对这种有序对(a,b)组成。组成。【example】设设R是美国所有州的集合上的关系，如果是美国所有州的集合上的关系，如果a州和州和b州州有公共的边界，那么有公共的边界，那么R包含包含(a,b).Rn是什么？其中是什么？其中n是正整数。是正整数。R*有时什么？有时什么？solution：关系关系Rn由对由对(a,b)构成，可以从构成，可以从a州恰好跨越州恰好跨越
14、n次州界到达次州界到达b州州。R*由对由对(a,b)构成，可以从构成，可以从a州跨越任意多次边界到达州跨越任意多次边界到达b州。那州。那些包含与美国大陆不相连的州的有序对是不在些包含与美国大陆不相连的州的有序对是不在R*中的。中的。定理定理2可可证明一个关系的明一个关系的传递闭包包t(R)和相关的和相关的连通性关系通性关系是等同的。是等同的。如果如果(a,b)R*和和(b,c)R*，那么在，那么在R中存在从中存在从a到到b和从和从b到到c的路的路径。我们从径。我们从a到到b的路径开始，并且沿着从的路径开始，并且沿着从b到到c的路径就得到一条从的路径就得到一条从a到到c的路径，因此，的路径，因此
15、，(a,c)R*。这就得出。这就得出R*是传递的。是传递的。现在假设现在假设S是包含是包含R的传递关系，因为的传递关系，因为S是传递的，是传递的，Sn也是传递的，并也是传递的，并且且Sn S.此外，因为此外，因为和和Sk S，因此，因此S*S.现在注意到如果现在注意到如果R S,那么那么R*S*,这是由于任何这是由于任何R中的路径也是中的路径也是S中中的路径。从而的路径。从而R*S*S.于是，任何包含于是，任何包含R的传递关系也一定包含的传递关系也一定包含R*.因此，因此，R*是是R的传递闭包。的传递闭包。已经知道传递闭包等于连通性关系，下面考虑这个关系的计已经知道传递闭包等于连通性关系，下面
16、考虑这个关系的计算问题。算问题。通过引理通过引理1 1我们知道在一个有限的有向图中为了计算这种关系我们知道在一个有限的有向图中为了计算这种关系 只需要检测包含不超过只需要检测包含不超过n n条边的路径就足够了，这里条边的路径就足够了，这里n n是集合是集合中的元素个数。中的元素个数。242023/1/27引理引理1：设设A是是n元素集合，元素集合，R是是A上的关系。如果上的关系。如果R中存在一条从中存在一条从a到到b的长至少为的长至少为1的路径，那么存在一的路径，那么存在一条长度不超过条长度不超过n的这种路径。的这种路径。此外，当此外，当a b时，如果在时，如果在R中存在一条从中存在一条从a到
17、到b的的路径，那么存在一条长度不超过路径，那么存在一条长度不超过n-1的这种路径。的这种路径。Proof：假设假设R中存在一条从中存在一条从a到到b的路径。令的路径。令m是这种路径的最是这种路径的最短长度。假设短长度。假设x0,x1,xm-1,xm是一条这样的路径，其中是一条这样的路径，其中x0=a,xm=b.假设假设a=b和和mn，使得，使得n+1 m.有鸽巢原理，因为有鸽巢原理，因为A中有中有n个个顶点，在顶点，在m个顶点个顶点x0,x1,x2,xm-1中至少有两个是相同的。中至少有两个是相同的。ax1xi-1xi=xjxj-1。.。xj-2xi+1xi+2xj+1xj+2.xm-1xm=
18、b 假设假设xi=xj满足满足0 ij m-1。那么这条路径包含一条从。那么这条路径包含一条从xi到到xi自身的回路。可以把这条回路从由自身的回路。可以把这条回路从由a到到b的路径中删除，上下的的路径中删除，上下的路径，即路径，即x0,x1,.,xi,xj+1,xm-1,xm是从是从a到到b的更短的路径。的更短的路径。因此，最短长度的这种路径的长度一定小于等于因此，最短长度的这种路径的长度一定小于等于n。由引理由引理1，我们看出，我们看出R的传递闭包是的传递闭包是R,R2,R3,Rn的并。这是的并。这是由于在由于在R*的两个顶点之间存在一条路径，当且仅当对某个正整的两个顶点之间存在一条路径，当
19、且仅当对某个正整数数i（i n）在）在Ri的这些顶点之间存在一条路径。因为的这些顶点之间存在一条路径。因为R*=R R2 R3 Rn并且表示关系的并的并且表示关系的并的0-1矩阵式这些关系的矩阵式这些关系的0-1矩阵的联合。矩阵的联合。因此传递闭包的因此传递闭包的0-1矩阵是矩阵是R的的0-1矩阵的前矩阵的前n次幂的次幂的0-1矩阵矩阵的联合。的联合。定理定理3：设设MR是是n元素集合上的关系元素集合上的关系R的的0-1矩阵。矩阵。那么传递闭包那么传递闭包R*的的0-1矩阵是矩阵是其中，其中，表示矩阵的对应元素进行析取运算表示矩阵的对应元素进行析取运算。29【example】求关系求关系R的传
20、递闭包的的传递闭包的0-1矩阵，其中矩阵，其中Solution：由定理由定理3，R*的的0-1矩阵是矩阵是因为因为所以所以30定理定理3可以作为计算关系可以作为计算关系R*的矩阵的算法基础。的矩阵的算法基础。为求出这个矩阵，要连续计算为求出这个矩阵，要连续计算M MR R的布尔幂，知道第的布尔幂，知道第n n次幂为止次幂为止。当计算每次幂时就构成这个幂与所有较小的幂的联合。当做。当计算每次幂时就构成这个幂与所有较小的幂的联合。当做到第到第n n次幂时，就得到关系次幂时，就得到关系R*R*的矩阵。这个过程见算法的矩阵。这个过程见算法1.1.【example】设设A=1,2,3，定义，定义A上的二
21、元关系上的二元关系R为：为：R=1,2,2,3,3,1 试用关系矩阵求传递闭包试用关系矩阵求传递闭包 R*(即即t(R)。solution：用关系矩阵求用关系矩阵求R*的方法如下：的方法如下：33 我们可以容易的求出用算法我们可以容易的求出用算法1确定关系的传递闭包所使用的位运算确定关系的传递闭包所使用的位运算次数。计算布尔幂次数。计算布尔幂 需找到需找到n-1个个nxn的的0-1矩阵的布矩阵的布尔积。每个布尔积可以使用尔积。每个布尔积可以使用n2(2n-1)次位运算求得。因此，计算这些次位运算求得。因此，计算这些乘积使用乘积使用n2(2n-1)(n-1)次位运算。次位运算。为从为从n个个MR
22、的布尔幂求的布尔幂求M R*,需要求需要求n-1个个0-1矩阵的联合。计算每一矩阵的联合。计算每一个联合使用个联合使用n2次位运算。因此，在这部分计算中使用次位运算。因此，在这部分计算中使用(n-1)n2次位运算次位运算 所以，当使用算法所以，当使用算法1时，用时，用n2(2n-1)(n-1)+(n-1)n2=2n3(n-1)=0(n4)次位运算就可以求出次位运算就可以求出n元素集合上关系的传递闭包的矩阵。元素集合上关系的传递闭包的矩阵。下面我们将要描述一个更有效的求传递闭包的算法。下面我们将要描述一个更有效的求传递闭包的算法。四、沃舍尔算法四、沃舍尔算法假设假设R是是n元素集合上的关系，设元
23、素集合上的关系，设 是这是这n个元素的任个元素的任意排列。沃舍尔算法中用到一条路径的内点的概念。意排列。沃舍尔算法中用到一条路径的内点的概念。内点：内点：如果如果 是一条路径，它的内点是是一条路径，它的内点是 即除了第一和最后一个顶点之外在路径中即除了第一和最后一个顶点之外在路径中 的所有顶点。的所有顶点。沃舍尔算法的基础沃舍尔算法的基础是构造一系列是构造一系列0-10-1矩阵。这些矩阵是矩阵。这些矩阵是 其中其中 是这个关系的是这个关系的0-10-1矩阵，且矩阵，且 如果存在一条从如果存在一条从v vi i到到v vj j的路径使得这条路径的的路径使得这条路径的 所有内点都在集合所有内点都在
24、集合 之中，那么之中，那么 。否。否 则为则为0.0.注意注意 ，因为，因为 的第的第(i,ji,j)项是项是1 1，当且仅当存在一，当且仅当存在一条从条从v vi i到到v vj j的路径，且全部内点都在集合的路径，且全部内点都在集合 之中。之中。下面的例子可以说明下面的例子可以说明Wk表示什么表示什么.【example】设设R是一个关系，它的有向图如图所示，设是一个关系，它的有向图如图所示，设a,b,c,d是集合元素的排列。求矩阵是集合元素的排列。求矩阵W0,W1,W2,W3,W4.矩阵矩阵W4是是R的传递闭包。的传递闭包。Solution：令令v1=a,v2=b,v3=c,v4=d.W0
25、是这个关系的矩阵，于是是这个关系的矩阵，于是 如果存在一条如果存在一条vi到到vj的且只有的且只有v1=a作为内点的路径，作为内点的路径，W1的的(i,j)项有项有1.注意因为所有长为注意因为所有长为1的路径没有内点，所以仍旧使用这些的路径没有内点，所以仍旧使用这些路径。此外存在一条从路径。此外存在一条从a到到b的路径，即的路径，即b,a,d.因此因此 如果存在一条如果存在一条vi到到vj的且只有的且只有v1=a和和v2=b作为内点的路径，作为内点的路径，W2的的(i,j)项有项有1.因为没有边以因为没有边以b作为终点，当我们允许作为终点，当我们允许b作为内点时不会得作为内点时不会得到新的路径
26、。因此到新的路径。因此W2=W1.若存在一条若存在一条vi到到vj的只有的只有v1=a,v2=b和和v3=c作为内点的路径，则作为内点的路径，则W3的的(i,j)项有项有1.我们现在有从我们现在有从d到到a的路径，即的路径，即d,c,a和从和从d到到d的路径的路径d,c,d.因此因此 最后，如果存在一条从最后，如果存在一条从vi到到vj的路径，并且以的路径，并且以v1=a,v2=b,v3=c以及以及v4=d作为内点，那么作为内点，那么W4的的(i,j)项为项为1.因为这些是图的全部顶因为这些是图的全部顶点，此项为点，此项为1，当且仅当存在一条从，当且仅当存在一条从vi到到vj的路径。的路径。因
27、此因此 这个最后的矩阵就是传递闭包的矩阵。这个最后的矩阵就是传递闭包的矩阵。沃舍尔算法通过有效地计算沃舍尔算法通过有效地计算W0=WR,W1,W2,Wn=WR*来计算来计算WR*不难看出可以直接从不难看出可以直接从Wk-1计算计算Wk:存在一条从存在一条从vi到到vj的只以的只以v1,v2,vk中的顶点作为内点的路径，当且中的顶点作为内点的路径，当且仅当要么存在一条从仅当要么存在一条从vi到到vj的且内点时表中前的且内点时表中前k-1个顶点的路径，要么存个顶点的路径，要么存在从在从vi到到vk的路径和从的路径和从vk到到vj的路径，而这些路径的内点仅在表中的前的路径，而这些路径的内点仅在表中的
28、前k-1个顶点中。个顶点中。这就是说，要么在这就是说，要么在vk被允许作为内点之前从被允许作为内点之前从vi到到vj已经存在一条路径已经存在一条路径，要么允许，要么允许vk作为内点产生一条从作为内点产生一条从vi到到vk然后从然后从vk到到vj的路径。的路径。这两种情况如下图表示。这两种情况如下图表示。第一种类型的路径存在，当且仅当第一种类型的路径存在，当且仅当 ，且第二种类型的路径，且第二种类型的路径存在，当且仅当存在，当且仅当 和和 都为都为1.于是于是 是是1，当且仅当或者，当且仅当或者 或者或者 和和 都是都是1.这样就得到引理这样就得到引理2.引理引理2 2 设设 是是0-1矩阵，它
29、在矩阵，它在(i，j)位置有位置有1，当且仅，当且仅当存在一条从当存在一条从vi到到vj的路径，其内点取自集合的路径，其内点取自集合 v1，v2，vk，那么那么其中其中i,j和和k是不超过是不超过n的正整数。的正整数。引理引理2提供了有效计算矩阵提供了有效计算矩阵Wk(k=1,2,n)的手段。我们使用的手段。我们使用引理引理2把沃舍尔算法的伪码在算法中给出。把沃舍尔算法的伪码在算法中给出。沃舍尔算法的计算复杂度沃舍尔算法的计算复杂度 很容易以位运算次数计算沃舍尔算法的计算复杂度。很容易以位运算次数计算沃舍尔算法的计算复杂度。使用引理使用引理2，从项，从项 ，和和 找到项找到项需要需要2次位运算
30、。为从次位运算。为从Wk-1求出求出Wk的所有的所有n2个项需要个项需要2n2次位次位运算。因为沃舍尔算法从运算。因为沃舍尔算法从W0=WR开始，计算开始，计算n个个0-1矩阵的序矩阵的序列列W1,W2,Wn=WR*,使用的位运算总次数是使用的位运算总次数是n*2n2=2n3.五、闭包关系的性质五、闭包关系的性质1.R是是A上关系，则上关系，则 R是自反的，当且仅当是自反的，当且仅当 r(R)=R.R是对称的，当且仅当是对称的，当且仅当 s(R)=R.R是传递的，当且仅当是传递的，当且仅当 t(R)=R.2.R是是A上关系，则上关系，则 R是自反的，则是自反的，则s(R)和和t(R)也自反。也
31、自反。R是对称的，则是对称的，则r(R)和和t(R)也对称。也对称。R是传递的，则是传递的，则r(R)也传递。也传递。下面给出一些证明。下面给出一些证明。proof:因为因为R自反自反,由定理由定理5得得r(R)=R,即即 R IA=R,r(s(R)=s(R)IA =(R RC)IA =(R IA)RC =r(R)RC =R RC =s(R)s(R)自反自反 类似可以证明类似可以证明t(Rt(R)也自反。也自反。Proof .证明证明t(R)对称对称:(t(R)C=(R R2.Rn.)C =RC(R2)C .(Rn)C.=RC(RC)2 .(RC)n.=R R2.Rn.(R对称，对称，RC=R
32、)=t(R)所以所以t(R)也对称。也对称。类似可以证明类似可以证明r(R)也对称。也对称。Proof：.证明证明r(R)传递传递:先用归纳法证明下面结论先用归纳法证明下面结论:(R IA)i=IA R R2.Ri i=1时时 R IA=IA R 结论成立。结论成立。假设假设ik 时结论成立，即时结论成立，即 (R IA)k=IA R R2.Rk当当i=k+1时时 (R IA)k+1=(R IA)k (R IA)=(IA R R2.Rk）(IA R)=(IA R R2.Rk)(R R2.Rk+1)=IA R R2.Rk Rk+1所以结论成立所以结论成立.t(r(R)=t(R IA)=(R IA
33、)(R IA)2(R IA)3.=(IA R)(IA R R2)(IA R R2 R3).=IA R R2 R3.=IA t(R)=IA R (R传递传递t(R)=R)=r(R)所以所以r(R)也传递。也传递。3.设设R1、R2是是A上关系，如果上关系，如果R1 R2，则，则 r(R1)r(R2)s(R1)s(R2)t(R1)t(R2)二元关系的闭包仍然是二元关系，还可以求它的闭包。二元关系的闭包仍然是二元关系，还可以求它的闭包。例如，例如，R是是A上的二元关系上的二元关系,r(R)是它的自反闭包，还可以求是它的自反闭包，还可以求r(R)的的对称闭包。对称闭包。r(R)的对称闭包记为的对称闭包
34、记为s(r(R)，简记为，简记为sr(R)，读做，读做R的自反的自反闭包的对称闭包。类似的，闭包的对称闭包。类似的，R的对称闭包的自反闭包的对称闭包的自反闭包r(s(R)简记为简记为rs(R)，R的对称闭包的传递闭包的对称闭包的传递闭包t(s(R)，简记为，简记为ts(R)，可得到性质可得到性质4.4.设设R是是A上关系，则上关系，则 sr(R)=rs(R)tr(R)=rt(R)st(R)ts(R)Proof：sr(R)=r(R)(r(R)c =(R IA)(R IA)c =(R IA)(Rc IAc)=R IA Rc IA =(R Rc)IA =s(R)IA=rs(R)的证明用前边证明的结论
35、：的证明用前边证明的结论：(R IA)k=IA R R2.Rk可证，这里从略。可证，这里从略。因因 R s(R)由定理由定理7得得 t(R)ts(R)st(R)sts(R)因因s(R)对称，有定理对称，有定理6得得ts(R)也对称，也对称，由定理由定理5得得sts(R)=ts(R)所以有所以有st(R)ts(R)证明完毕。证明完毕。【example】设设R是集合是集合0，1，2，3上的关系，上的关系，R包含有包含有序对（序对（0，1），（），（1，1），（），（1，2），（），（2，0），），（2，2）和（）和（3，0），求），求 a）R的自反闭包的自反闭包 b）R的对称闭包的对称闭包Solu
36、tionSolution：a a）(0,0),(0,1),(1,1),(1,2),(2,0),(2,2),(3,0),(3,3)(0,0),(0,1),(1,1),(1,2),(2,0),(2,2),(3,0),(3,3)b)(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0)b)(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0)【example】从有穷集上关系的有向图怎样构造表示它的自从有穷集上关系的有向图怎样构造表示它的自反闭包的有向图？反闭包的有向图？在练
37、习在练习57中画出给定有向图所表示关系的自反闭包的有向中画出给定有向图所表示关系的自反闭包的有向图。图。【example】确定下面的顶点序列是否为右面的有向图中的路径确定下面的顶点序列是否为右面的有向图中的路径 a)a,b,c,e b)b,e,c,b,e c)a,a,b,e,d,e d)b,c,e,d,a,a,b e)b,c,c,b,e,d,e,d f)a,a,b,b,c,c,b,e,dSolution:a)是一条路径是一条路径 b)不是一条路径（其中在不是一条路径（其中在e和和c之间没有边）之间没有边）c)是一条路径是一条路径 d)不是一条路径（其中在不是一条路径（其中在d和和a之间没有边）
38、之间没有边）e)是一条路径是一条路径 f)不是一条路径不是一条路径思考：思考：确定该有向图中是否存在一条以下面给定的第一顶点作为确定该有向图中是否存在一条以下面给定的第一顶点作为起点、以第二顶点作为终点的路径？起点、以第二顶点作为终点的路径？a）a，b b）b，a c）b，b d）a，e e）b，d f）c，d g）d，d h）e，a i）e，cSolution：a)存在一条路径存在一条路径a,b b)存在一条路径存在一条路径b,e,a c)存在一条路径存在一条路径b,c,b d)存在一条路径存在一条路径a,b,e e)存在一条路径存在一条路径b,e,d f)存在一条路径存在一条路径c,e,d g)存在一条路径存在一条路径d,e,d 还有一条是还有一条是d，d h)存在一条路径存在一条路径e,a 还有一条是还有一条是e,a,b,e,a,b,e,a,b,e,a i)存在一条路径存在一条路径e,a,b,c 【example】给定给定A中关系中关系R如图所示：分别画出如图所示：分别画出r(R)、s(R)、t(R)、sr(R)、rs(R)、tr(R)、rt(R)、st(R)、ts(R)的图。的图。12431243r(R)1243s(R)1243t(R)1。2。43sr(R)1243tr(R)1。2。43st(R)1。2。43rs(R)1。2。43rt(R)1。2。43ts(R)