《离散数学课件-第4章-5》由会员分享，可在线阅读，更多相关《离散数学课件-第4章-5（67页珍藏版）》请在金锄头文库上搜索。
1、1*离散数学 Discrete Mathematics 汪荣贵贵 教授合肥工业业大学软软件学院专专用课课件2010.6& 学习内容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这里要介绍关系的自反闭包、对称闭包和 传递闭包。【example】给给定 A中关系R，如图图所示，求A上另一个关系R，使得它是包含R的“最小的”(序偶尽量少)具有自反(对对 称
2、、传递传递 )性的关系。这这个R就是R的自反(对对称、传递传递 )闭闭包。2。31。2。32。32。32。3123123123这三个关系图分别是R的自反、对称、传递闭包。一、关系的闭包 定义：给定 A中关系R,若A上另一个关系R，满足：RR；R是自反的(对称的、传递的)；R是“最小的”，即对于任何A上自反(对称、传递)的关系R,如果RR,就有RR。则称R是R的自反(对称、传递)闭包。记作r(R)、s(R)、t(R)(reflexive、symmetric、transitive)2.计算方法1.给定 A中关系R,则 r(R)=RIA。proof：令R =RIA,显然R是自反的和R R ，下面证明
3、 R是“最小的”：如果有A上自反关系R“且R R”,又IA R“,所以 RIA R”,即R R“ 。所以R就是R的自反闭 包。即r(R)=RIA 。2.给定 A中关系R,则 s(R)=RRC 。证明方法与1类似。【example 】整数集上的关系R=(a,b)|ab的对称闭包是 多少？Solution：R的对称闭包是关系R RC =(a,b)|ab (b,a)|ab =(a,b)|ab二、有向图的路径使用有向图表示关系有助于构造关系的传递闭包 。为此引入 一些需要用到的术语。通过沿有向图的边(按照这条边的箭头指示的相同方向)移动有向图就得到一条有向图中的路径。定义1：在有向图G中从a到b的一条
4、路径是G中一条或多条边的序列(x0,x1),(x1, x2),(x2, x3),(xn-1, xn),其中 x0=a, xn=b.即一个边的序列，其中一天的终点和路径中下一条边 的起点相同。这条路径记为x0, x1, xn-1, xn,长度为n 。在同一定点开始和结束的路径叫做回路或圈。注：有向图的一条路径可以多次通过一个顶点。此外，有 向图的一条边也可以多次出现在一条路径中。【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 这些路径的长度是多少？这个列表中的哪些路径
5、是回路？Solution：因为(a，b)、(b，e)和(e，d)都是边，a,b,e,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的路径。 两条路径b，a，c，b，a，a，b和e，b，a，b，a，b，e是回路，因为它们在同一
6、顶点开始和结束。路径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：设R是集合A上的关系。从a到b存在一条长为1的路径， 当且仅当（a，b）Rn。Proof：使用数学归纳法证明。根据定义，从a到b存在一条长为1的路径，当且仅当 （a，b）R。因此当n=1时定理为真。假定对于正整数n定理为真，这是归纳假设。从a到b存在一条长为n+1的路径，当且仅当存在元素c A使得从a到c存在一
7、条长为1的路径，即(a,c) R,以及一条从c到b的长为n的路径，即(c,b) Rn.因此由归纳假设，从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的路径。因为Rn由对(a,b)构成，使得存在一条从a到b的长度为n的路径，从而R*是所有集合Rn的并。换句话说，许多模型都用到连通性关系。【examp
8、le】设R是世界上所有人的集合上的关系，如果a认识b ，那么R包含(a,b). Rn是什么？其中n是大于2的正整数。R*是什 么？ Solution：如果存在c使得(a,c) R且(c,b) R即存在c使得a认识c，c 认识b，那么关系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
9、是什么？R*是什么？Solution:如果换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州恰好跨越n次州界到达b州 。R*由对(a,b)构成，可以从a州跨越任意多次边界到达b州。那 些包含与美国大陆不相连的州的有序对是不在R*中的。 定理2可证证明一个关系的传递闭传递闭 包t(R)和相关的连连通性
10、关系 是等同的。定理2：关系R的传递闭传递闭 包t(R)等于连连通性关系R*.Proof：注意R*包含R.为证为证 明R*是R的传递闭传递闭 包，我们们必须证须证明R*是传递传递 的且对对一切包含R的传递传递 关系S，有R* S.首先，我们证们证 明R*是传递传递 的。如果(a,b) R*和(b,c) R*，那么在R中存在从a到b和从b到c的路径。我们从a到b的路径开始，并且沿着从b到c的路径就得到一条从a到c的路径，因此， (a,c) R*。这就得出R*是传递的。现在假设S是包含R的传递关系，因为S是传递的，Sn也是传递的，并且Sn S.此外，因为和Sk S，因此S* S.现在注意到如果R
11、S,那么R* S*,这是由于任何R中的路径也是S中的路径。从而R* S* S.于是，任何包含R的传递关系也一定包含R*.因此，R*是R的传递闭包。 已经知道传递闭包等于连通性关系，下面考虑这个关系的计 算问题。通过引理1我们知道在一个有限的有向图中为了计算这种关系只需要检测包含不超过n条边的路径就足够了，这里n是集合 中的元素个数。24*引理1：设A是n元素集合，R是A上的关系。如果R中存在一条从a到b的长至少为1的路径，那么存在一条长度不超过n的这种路径。此外，当a b时，如果在R中存在一条从a到b的路径，那么存在一条长度不超过n-1的这种路径。 Proof：假设R中存在一条从a到b的路径。
12、令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=b假设xi=xj满足0 ij m-1。那么这条路径包含一条从xi到xi 自身的回路。可以把这条回路从由a到b的路径中删除，上下的 路径，即 x0,x1,xi,xj+1,xm-1,xm 是从a到b的更短的路径。因此，最短长度的这种路径的长度一定小于等于n。由引理1
13、，我们看出R的传递闭包是R,R2,R3,Rn的并。这是由于在R*的两个顶点之间存在一条路径，当且仅当对某个正整数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的传递闭包的0-1矩阵，其中Solution：由定理3，R*的0-1矩阵是因为所以30 定理3可以作为计算关系R*的矩阵的算法基础。
14、为求出这个矩阵，要连续计算MR的布尔幂，知道第n次幂为止。当计算每次幂时就构成这个幂与所有较小的幂的联合。当做到第n次幂时，就得到关系R*的矩阵。这个过程见算法1.【example】设A=1,2,3，定义A上的二元关系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的布尔幂求M R*
15、,需要求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元素集合上的关系，设 是这n个元素的任 意排列。沃舍尔算法中用到一条路径的内点的概念。内点：如果 是一条路径，它的内点是即除了第一和最后一个顶点之外在路径中的所有顶点。 沃舍尔算法的基础是构造一系列0-1矩阵。这些矩阵是其中 是这个关系的0-1矩阵，且如果存在一条从vi到vj的路径使得这条路径的所有内点都在集合 之中，那么 。否则为0.注意 ，因为 的第(i,j)项是1，当且仅当存在一 条从vi到vj的路径，且全部内点都在集合 之中 。下面的例子可以说明Wk表示什么.【example】设R是一个关系，它的有向图如图所示，设a,b,c,d是集合元素的排列。求矩阵W0,W1,W2,W3,W4.矩阵W4是R的传递闭包。Solution：令v1=a,v2=b,v3=c,v4=d.W0是这个关系的矩阵
