离散数学课件第四章(第4讲).ppt

《离散数学课件第四章(第4讲).ppt》由会员分享，可在线阅读，更多相关《离散数学课件第四章(第4讲).ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5 覆盖与划分覆盖与划分定义定义：给定一非空集合，又设：给定一非空集合，又设 若若（1）（2）则称则称A为为S的覆盖。的覆盖。例：例：S=a,b,c，A=a,b,b,c，B=a,a,b,c，C=a,b,c，D=a,b,a,c 集合集合A,B,C,D都为都为S的覆盖。的覆盖。定义定义：给定一非空集合：给定一非空集合S，设非空集合，设非空集合 如果有：如果有：（i,j=1,2,m）则称集合则称集合A是集合是集合S的一个划分。的一个划分。例：例：S=a,b,c，A=a,b,c，B=a,c,b，C=a,b,c，D=a,b,c 集合集合A,B,C,D都为都为S的划分。的划分。讨论定义：讨论定义：（2）划

2、分）划分A中的元素，称为划分的类，在定义中中的元素，称为划分的类，在定义中 都是都是A中的一个类，类的个数称为划分的秩；中的一个类，类的个数称为划分的秩；（1）集合的划分一定是一个覆盖，而覆盖不一定是划分；）集合的划分一定是一个覆盖，而覆盖不一定是划分；（3）集合）集合S上的秩最大的划分称最大划分，最小的称最小划分。上的秩最大的划分称最大划分，最小的称最小划分。例：设例：设S=a,b,c，下列，下列 均为均为S的一个划分：的一个划分：类有二个类有二个a,b,c,秩为秩为2；类有二个类有二个a,b,c,秩为秩为2；类有二个类有二个a,c,b,秩为秩为2；秩为秩为3；类有三个类有三个a,b,c,秩

3、为秩为1。类有一个类有一个a,b,c,所以所以A4 是最大划分，是最大划分，A5 是最小划分是最小划分定义定义：设：设A和和A是非空集合是非空集合S的二种划分，并可表示成：的二种划分，并可表示成：若若A的每一个类的每一个类 都是都是A的某一个类的某一个类 的子集，则称划分的子集，则称划分A是划分是划分A的加细，的加细，或讲或讲A加细了加细了A，若，若A加细了加细了A且且 则称则称A是是A的真加细。的真加细。例：例：S=a,b,c,d,S的划分：的划分：A=a,b,c,d,A=abc,d，则，则A是是A的真加细的真加细 A=abcd,则则A 是是A的真加细的真加细 定义定义：设：设X是一个集合，

4、是一个集合，R是是X中的二元关系，若中的二元关系，若R是是自反自反的，的，对称对称的和的和可传递可传递的，则称的，则称R是等价关系。是等价关系。例：实数集合上的例：实数集合上的“=”关系（相等）为等价关系关系（相等）为等价关系6 等价关系等价关系试验证试验证R是等价关系，是等价关系，画出画出R的关系图，列出的关系图，列出R的关系矩阵的关系矩阵 解：解：（1）R=（2）R的关系矩阵和关系图的关系矩阵和关系图 R满足自反、对称和传递性质，满足自反、对称和传递性质，R是等价关系是等价关系例：设例：设A=1,2,3,4，R是是A集合上的二元关系集合上的二元关系为整数为整数定义定义：设：设 若若为整数，

5、为整数，则称则称x模模m等于等于y，记作：，记作：R=|，则，则R是一个等价关系。是一个等价关系。定理定理：任何集合：任何集合，R是集合是集合A中的关系，中的关系，例：设例：设A=0，1，2，3，6，R=x,y|xy(x,y A)yx(mod 3)，计算计算domR和和ranR。定义定义：设：设R是是A集合中的等价关系，对于任何的集合中的等价关系，对于任何的 来讲，可把集合来讲，可把集合 规定成：规定成：并称是由并称是由 生成的生成的R等价类。等价类。例：设例：设A=a,b,c,d,R是是A中的等价关系，中的等价关系，R=（1）（2）（3）若）若，则，则（4）对于所有的）对于所有的，或者，或者

6、 或者或者（5）定理定理：设：设A是一个非空集合，是一个非空集合，R是是A中的等价关系，则中的等价关系，则例：设例：设X=N，关系，关系R=是一等价关系，是一等价关系，则则R可以找出三个等价类：可以找出三个等价类：=0，3，6，9=1，4，7，10=2，5，8，11定理定理：设：设A是一非空集合，是一非空集合，R是是A中的等价关系，中的等价关系，R等价类的集合等价类的集合xR|x A是是A的一个划分，且此集合的一个划分，且此集合称为称为A关于关于R的商集，用的商集，用 表示之。例：设例：设A=x1,x2.xn（1）A集合中的全域关系集合中的全域关系:是一个等价关系，是一个等价关系，X关于关于R

7、1的商集的商集它形成了它形成了A的一个最小划分的一个最小划分（2）A中的恒等关系中的恒等关系 它形成了它形成了A的一个最大划分的一个最大划分 定理定理：X是一非空集合，是一非空集合，A为为X的一个划分，且的一个划分，且A=A1,A2,.An，则由，则由A导出的导出的X中的一个等价关系中的一个等价关系 例：例：Xa,b,c,d，A=a,b,c,d则则 R(a,b a,b)(c,d c,d)=,因此：集合因此：集合X上的等价关系与上的等价关系与X的划分之间有一一对应关系。的划分之间有一一对应关系。定义定义：设：设X是一个集合，是一个集合，R是是X中的二元关系，若中的二元关系，若R是是自反的，对称的

8、自反的，对称的，则称，则称R是是相容关系相容关系。由定义知由定义知,等价关系是具有等价关系是具有传递性传递性的相容关系的相容关系;相容关相容关 系是一个比等价关系更为普遍的关系。系是一个比等价关系更为普遍的关系。7 相容关系相容关系因为相容关系是自反和对称的因为相容关系是自反和对称的,其关系矩阵是对称的且其关系矩阵是对称的且主对角线元素全为主对角线元素全为1,因此我们可仅用下三角矩阵因此我们可仅用下三角矩阵T来表来表示和存储就够了示和存储就够了,即关系矩阵可以简化为即关系矩阵可以简化为“阶梯形阶梯形”。EX：设：设A=cat,teacher,cold,desk,knife,byR=x,y|x,

9、y A 且且 x和和y至少有一个相同的字母至少有一个相同的字母R 是是 A上的一个相容关系上的一个相容关系,简记简记 A 中元素依次为中元素依次为x1,x2,x3,x4,x5,x6,则则R的关系矩阵的关系矩阵MR和对应简化的下三角矩阵和对应简化的下三角矩阵TR为：为：catteacher cold desk knife bycat teacher cold desk knife byEX：在相容关系的关系图上，每个顶点都有：在相容关系的关系图上，每个顶点都有自回路自回路且每两个顶点且每两个顶点间的弧线都是间的弧线都是成对出现成对出现的。为简化相容关系的关系图的。为简化相容关系的关系图,不画自回

10、路不画自回路,并用无箭头的单线段代替来回弧线并用无箭头的单线段代替来回弧线,使之成为无向图。上例的关系使之成为无向图。上例的关系图如下图如下:x1x2x3x4x5x6定义定义1：设：设R是集合是集合A上的相容关系上的相容关系,若若C A,若任意若任意a,b C,有有aRb,则称则称C是由是由R产生的相容类。产生的相容类。例如上例的相容关系例如上例的相容关系R可产生相容类可产生相容类x1,x2，x1,x3，x2,x3，x6，x2,x4,x5，等等。，等等。对于前三个相容类，都能加进新的元素组成新的相容类，而对于前三个相容类，都能加进新的元素组成新的相容类，而后两个相容类，加入任一新元素，就不能组

11、成相容类，我们后两个相容类，加入任一新元素，就不能组成相容类，我们称它为最大相容类。称它为最大相容类。x3x2x1求最大相容类的方法：求最大相容类的方法：关系图法：画出简化相容关系的关系图后，先确定结点最多的完关系图法：画出简化相容关系的关系图后，先确定结点最多的完全多边形，以后逐次减少。全多边形，以后逐次减少。最大完全多边形最大完全多边形:每个顶点都与其他所有顶点相联结的多边形。每个顶点都与其他所有顶点相联结的多边形。(1)一个结点的最大的完全多边形；一个结点的最大的完全多边形；(2)二个结点的最大完全多边形；二个结点的最大完全多边形；(3)三个结点的最大完全多边形；三个结点的最大完全多边形

12、；(4)四个结点的最大完全多边形；四个结点的最大完全多边形；(5)五个结点的最大完全多边形五个结点的最大完全多边形;最大完全多边形最大完全多边形例：已知相容关系图，求出最大相容类例：已知相容关系图，求出最大相容类最大相容类集合为：最大相容类集合为：完全覆盖：设有完全覆盖：设有 集合集合 A 上的相容关系上的相容关系 R，其中最大相容，其中最大相容类的集合，称作集合类的集合，称作集合 A 的完全覆盖。的完全覆盖。定理：定理：A 上的每个相容关系，唯一的定义一个完全覆盖。上的每个相容关系，唯一的定义一个完全覆盖。最大相容类：最大相容类：b,g,f,e，b,a,e，b,c，d该集合的完全覆盖为：该集合的完全覆盖为：b,g,f,e，b,a,e，b,c，d gabcdef