(1.5.2)--ch3—第七讲离散数学离散数学.pdf
离离 散散 数数 学学 Discrete MathematicsDiscrete Mathematics 3.11 相容关系相容关系 定义定义3.11.1 集合集合A上的关系上的关系r,如果它是如果它是自反的自反的,对称的对称的,则称则称 r 是是 A上的上的相容关系相容关系(Compatibility Relations).例例1 设集合设集合A=216，243，357，648.定义定义 A上的关系上的关系r r=|x,y A,且且x与与y中至少有一个相同数字中至少有一个相同数字 则则r是是 A上的一个相容关系上的一个相容关系.令令 a=216,b=243,c=357,d=648,则则 r=,1101111101101101rM r 的关系图为的关系图为:r 的关系矩阵为的关系矩阵为:可以看出相容关系的关系图、关系矩阵有以下特点可以看出相容关系的关系图、关系矩阵有以下特点:(1)每个结点都有环每个结点都有环;(2)任意两个结点之间任意两个结点之间,若有弧线若有弧线,则必为双向的则必为双向的,否则没有弧线否则没有弧线.(3)主对角线元素为主对角线元素为1;(4)矩阵为对称矩阵矩阵为对称矩阵;因此我们可以将例因此我们可以将例1中中r 的关系图简化为的关系图简化为:也可省去也可省去Mr中阶梯折线以上的部分中阶梯折线以上的部分,只用下边的梯形表示相只用下边的梯形表示相容关系容关系.bcdabc101110定义定义3.11.1 设设 r 为集合为集合A上的相容关系上的相容关系,C A,若对于若对于C中任中任 意两个元素意两个元素x,y,有有xry,称称 C 是由相容关系是由相容关系r 产生的相容类产生的相容类.如如 例例1中的相容类有中的相容类有 a,b,a,d ,b,c,b,d a,b,c a,b,d 定义定义3.11.2 设设 r 为集合为集合A上的相容关系上的相容关系,不能真包含在任何不能真包含在任何 其它相容类中的相容类其它相容类中的相容类,称作称作最大相容类最大相容类.记作记作Cr 如如 例例1中最大相容类是中最大相容类是 b,c,a,b,d 定义定义3.11.2 设设 r 为集合为集合A上的相容关系上的相容关系,C A,C,如果如果 1.对任意对任意a,b C,均有均有 r 2 对任意对任意a A-C,在在C中至少存在一个元素中至少存在一个元素c,使使 r 则称则称C是相容关系是相容关系r 的的最大相容类最大相容类.根据最大相容类的定义根据最大相容类的定义,它可以从相容关系它可以从相容关系r 的简化关系的简化关系图求得图求得,具体方法是具体方法是:(1)r 的简化关系图中的简化关系图中,每一个最大完全多边形的结点集合每一个最大完全多边形的结点集合,是一个最大相容类是一个最大相容类.(2)r 的简化关系图中的简化关系图中,不在完全多边形中的边的两个端点的不在完全多边形中的边的两个端点的 集合也是一个最大相容类集合也是一个最大相容类.(3)r 的简化关系图中的简化关系图中,每一个孤立结点的单点集合每一个孤立结点的单点集合,也是一个也是一个 最大相容类最大相容类.完全多边形完全多边形:其每个顶点都与其它顶点连接的多边形其每个顶点都与其它顶点连接的多边形.例例2 设给定相容关系设给定相容关系r 的简化关系图如下的简化关系图如下,求出其最大相容类求出其最大相容类.R的最大相容类为的最大相容类为:g,d,e,c,d,f,a,b,d,f.定理定理3.11.1 设设 r 为集合为集合A上的相容关系上的相容关系,C是一个相容类是一个相容类,那么必存在一个最大相容类那么必存在一个最大相容类Cr,使得使得C Cr.定义定义3.11.4 在集合在集合A上给定相容关系上给定相容关系r,其最大相容类的集合其最大相容类的集合,称作集合称作集合A的的完全覆盖完全覆盖,记作记作Cr(A).如例如例2中中,A的完全覆盖为的完全覆盖为:g,d,e,c,d,f,a,b,d,f 当相容关系当相容关系r确定时确定时,由它产生的最大相容类集合是唯一的由它产生的最大相容类集合是唯一的 因此因此 r 确定集合确定集合A的唯一的完全覆盖的唯一的完全覆盖.注意注意:例例 设设 A=a,b,c,d,e,f,R为为A上的相容关系上的相容关系,其图形表示其图形表示如图所示如图所示.求求r的完全覆盖的完全覆盖.cb。dfea解解 由图可知由图可知,r 产生的最大相容类为产生的最大相容类为:a,b,f,a,d,e,c,f 所以所以r 确定的完全覆盖为确定的完全覆盖为:S=a,b,f,a,d,e,c,f 定理定理3.11.2 给定集合给定集合A的覆盖的覆盖A1,A2,An,由它确定的由它确定的 关系关系R=(A1A1)(A2A2)(AnAn)是相容关系是相容关系.注意注意:由定理可知由定理可知,给定集合给定集合A的任意一个覆盖的任意一个覆盖,必可在必可在A上构造上构造 一个对应于此覆盖的一个相容关系一个对应于此覆盖的一个相容关系,构造出的相同的相容关系构造出的相同的相容关系.但是两个不同的覆盖却能但是两个不同的覆盖却能 例例3 设设A=a,b,c,d,集合集合S1=a,b,b,c,d 和和 S2=a,b,b,c,c,d,b,d 是是 A 的两个不同的覆盖的两个不同的覆盖 但根据它们构造出的相容关系均是但根据它们构造出的相容关系均是 R=,定理定理3.11.3集合集合A上的相容关系上的相容关系r与完全覆盖与完全覆盖Cr(A)是是1-1对应的对应的.练习练习 设集合设设集合设A=a1,a2,a3,a4,a5,是是A上的相容关系上的相容关系,111001011110101其关系矩阵的下三角矩阵为其关系矩阵的下三角矩阵为(1)试根据相容关系的对称性试根据相容关系的对称性,填入关系矩阵中的其它元素填入关系矩阵中的其它元素 1100111010001110111010101(2)用列举法表示用列举法表示(3)写出写出的完全覆盖的完全覆盖.=,S=a1,a2,a3,a4,a2,a4,a1,a5,a3,a5 本节介绍了集合的划分与覆盖、等价关系、等价类、本节介绍了集合的划分与覆盖、等价关系、等价类、商集、相容关系、最大相容类、完全覆盖的概念商集、相容关系、最大相容类、完全覆盖的概念.小小 结结 重点掌握重点掌握:等价关系、等价类、商集、完全覆盖等概念等价关系、等价类、商集、完全覆盖等概念及等价关系与划分、相容关系与覆盖、完全覆盖之间的及等价关系与划分、相容关系与覆盖、完全覆盖之间的联系联系.
