离散数学-3-11 相容关系(精品)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第三章 集合与关系,3-11 相容关系,授课人：李朔,Email:,chn,.,nj,.,ls,gmail,.com,1,一相容关系,与等价关系类似，另一类应用非常广泛的关系，就是相容关系。,P135,定义3-11.1,给定集合,A,上的关系,r，,若,r,是,自反的,，,对称的,，则称,r,是,A,上的,相容关系,。,例如,：设,A,是由下列英文单词组成的集合。,A=cat,teacher,cold,desk,knife,by,。,定义关系：,r=,x,y,A,且,x,和,y,有相同的字母,。,易见,r,是自反，对称的。因此,r,为相容关系。,设,x,1,=cat,x,2,=teacher,x,3,=cold,x,4,=desk,x,5,=knife,x,6,=by,r,的关系矩阵如下：,2,一相容关系,由于,r,是对称的，因此,r,的关系矩阵也是对称矩阵，因此，对相容关系，其关系矩阵只需写出下三角部分即可（简化矩阵，,P136,表3-11.1)。,至于关系图，因,r,是自反和对称的，故每个结点都有环，且任两点若有连线，必有双向线，因此，大家约定。对相容关系，在画图时，不画每个元素的环，同时对每对双向线，只画出单线，这样就更加简洁直观，如上例，关系图可表示如上右图.,3,二相容类,P136,定义,3-11.2,设,r,是集合,A,上的相容关系，若,C,A,，,且对于,C,中,任两个元素,a,1,a,2,有,a,1,r a,2,，,则称,C,是由相容关系,r,产生的,相容类,。,例如上例的相容关系,r,可产生相容类。,x,1,x,2,x,1,x,3,x,2,x,3,x,6,x,2,x,4,x,5,。,对于前三个相容类，都能加入新的元素组成新的相容类，而对于后两个相容类，,加入任一新元素，就不再成为相容类,，我们称它们为最大相容类。,P137,定义3-11.3,设,r,为集合,A,上的相容关系，不能真包含在其它相容类中的相容类。称作,最大相容类,，记作,C,r,。,若,C,r,为,A,上最大相容类，显然它是,A,的子集，对任何,x,C,r,，,x,必与,C,r,中的所有元素有相容关系.而在,A,C,r,中没有任何元素与,C,r,中所有元素有相容关系。,4,二相容类,在相容关系图中，,最大完全多边形的顶点集合,，就是最大相容类。所谓,完全多边形,，就是其每个顶点都与其它顶点连接的多边形，例如一个三角形是完全多边形，一个四边形再加两条对角线就是完全多边形。,此外，在相容关系图中，一个孤立点，以及不是完全多边形的两个结点的连线，也是最大相容类。,5,二相容类,P137,例：给定相容关系图写出最大相容类。,解：最大相容类为：,x,1,x,2,x,4,x,5,x,3,x,4,x,6,x,4,x,5,x,7,:,6,二相容类,P137,定理,3-11.1,设,r,是有限集,A,上的相容关系，,c,是一个相容类，那么必存在最大相容类,C,r,使,c,C,r,。,证明：设,A x,1,x,2,x,n,，,构造相容类序列,C,0,C,1,C,2,，,其中,C,0,=c,且,C,i,+1,=,C,i,U,x,j,，,其中,j,满足,x,j,C,i,且,x,j,与,C,i,中各元素都相容的最小足标。,由于,A,=n，,故至多经,n-,c,步，过程将终止，此时序列中最后一个相容类，即为所求。,由上可见，,A,中任一元,a，,可组成相容类,a，,而它必包含在一个最大相容类,C,r,中，因此，由最大相容类构成一个集合，则,A,中每一个元素至少属于该集合的一个成员中，即是说，,最大相容类的集合必然构成集合,A,的一个覆盖,。,7,三完全覆盖,P138,定义,3-11.4,在集合,A,上给定相容关系,r,，,其最大的相容类集合称为,A,的一个,完全覆盖,，记,C,r,(A),。,注意到集合,A,的覆盖不是唯一的，因此给定相容关系,r,，,可以作成不同的相容类集合，它们都是,A,的覆盖。但是，给定相容关系,r,只能,唯一对应一个完全覆盖,。如上例：,x,1,x,2,x,4,x,5,x,3,x,4,x,6,x,4,x,5,x,7,反过来，下面讨论由覆盖如何决定一个相容关系。,8,三完全覆盖,P138,定理,3-11.2,给定集合,A,的覆盖,A,1,A,2,A,n,。,由它确定的关系：,R=A,1,A,1,A,2,A,2,A,n,A,n,是,A,上相容关系。,证明：,因,A,。,对任一,x,A,，,必存在某个,j0,，,使,x,A,j,，,故,A,j,A,j,，,即,R,。,因此,R,是自反的。,其次，若,x,y,A,且,R,，,则有某个,j0,使,A,j,A,j,，,故,A,j,A,j,。,即,R,。,故,R,是对称的。,因此,R,是,A,上的相容关系。,9,三完全覆盖,从上述可见，给定集合,A,上的任一个覆盖，必可在,A,上构造对应于此覆盖的一个相容关系。但是不同的覆盖却能构造相同的相容关系。,例：,A1,2,3,集合1,2,3,3,4和1,2,2,3,1,3,3,4都是,A,的覆盖，但它们可以产生相同的相容关系。,R,，,但对完全覆盖有：,定理3-11.3,集合,A,上相容关系,r,与完全覆盖存在一一对应。,证明：略,10,本课小结,相容关系,相容类,完全覆盖,11,作业,P139(6),12,