离散数学(3.11相容关系)

1、1张捷第三章第三章 集合与关系集合与关系（Sets and Relations)Sets and Relations) 3.6 3.6 关系的闭包运算关系的闭包运算(Closure Operations)(Closure Operations)3.7 3.7 集合的划分与覆盖集合的划分与覆盖(Partition & Cover of Sets) (Partition & Cover of Sets) 3.8 3.8 等价关系等价关系(Equivalent Relations) (Equivalent Relations) 3.9 3.9 相容关系相容关系(Compatibility(Compa

2、tibilityRelations) Relations) 3.10 3.10 序关系序关系(Ordered Relations)(Ordered Relations)3.1 3.1 集合及其运算集合及其运算(Sets & Operations with sets)(Sets & Operations with sets) 3.2 3.2 序偶与笛卡尔积序偶与笛卡尔积(Ordered Pairs & Cartesian Product)(Ordered Pairs & Cartesian Product)3.3 3.3 关系关系 (Relations) (Relations) 3.4 3.4

3、关系的性质关系的性质(The Propeties(The Propeties of Relations) of Relations) 3.5 3.5 复合关系与逆关系复合关系与逆关系(Compound Relations & Inverse(Compound Relations & Inverse Relations) Relations)BABA 3.9 3.9 相容关系相容关系(Compatibility(CompatibilityRelations) Relations) 3.9.1 3.9.1 相容关系的定义相容关系的定义( (The definition of The definit

4、ion of CompatibilityCompatibility relations relations) )3.9.2 3.9.2 相容关系与覆盖相容关系与覆盖(Compatibility(CompatibilityRelations & Relations & covers) covers) 第三章第三章 集合与关系集合与关系(Sets & Relations)3.9 3.9 相容关系相容关系 3.9.1 3.9.1 相容关系的定义相容关系的定义( (The definitionThe definition of of CompatibilityCompatibility relatio

5、ns relations) ) 1. 1. 相容关系相容关系 定义定义3.9.1 3.9.1 集合集合A A上的关系上的关系 ，如果它是自反的，如果它是自反的，对称的，则称对称的，则称 是是A A上的相容关系。上的相容关系。 例例1 1 设设集合集合A=216A=216，243243，357357，648.648.定义定义A A上的关系上的关系 =x,yx,y|x,yA|x,yA，且，且x x与与y y中至少有一个相同数字中至少有一个相同数字 ， 则则 是是A A上的一个相容关系。但上的一个相容关系。但 不是等价关系。不是等价关系。令令 =216=216， =243=243， = 357= 3

6、57， = 648= 648，则，则 可表示为可表示为,bcdbcbabbbdabaaabcda,ddbdadcc 可以看出相容关系的可以看出相容关系的关系图有以下特点关系图有以下特点:(1)每个结点都有自环每个结点都有自环;(2)(2)任意两个任意两个结点之间结点之间,若有弧线若有弧线,则必为双向的则必为双向的,否则没有弧否则没有弧线线.的关系图为的关系图为:的关系矩阵为的关系矩阵为:1011011011111011M 我们也可以省去我们也可以省去 中阶梯折线以上的部分，只用下边的中阶梯折线以上的部分，只用下边的梯梯形表示相容关系形表示相容关系 。因此我们可以将例因此我们可以将例1中中 的关

7、系图简化为的关系图简化为:Mab 1c 0 1d 1 1 0是一个相容关系是一个相容关系.5S 例例2 2 设设 是某台微机上是某台微机上6 6项任务项任务的集合，有五个子程序的集合，有五个子程序 ， ， ， 和和 供它们选供它们选择调用，下表列出了它们调用子程序的情况。择调用，下表列出了它们调用子程序的情况。T5T4T3T2T1调用的子程序任务名称定义定义A A上的关系上的关系=(x,y)|x,yA=(x,y)|x,yA且且x x与与y y调用了相同的调用了相同的子程序子程序,同时也是一个等价关系同时也是一个等价关系.T621,SS32,SS13,SS4S5S,654321TTTTTTA5S

8、1S2S3S4S,T,T,T,T,T,T,T,T,T,T,T,T,T,T32133122122111T,T,T,T,T,T,T,T,T,T,T,T,T,T66554664443323 2. 2. 最大相容类最大相容类（greatest consistent classesgreatest consistent classes） 定义定义3.9.2 设设是有限集是有限集A A上的相容关系，上的相容关系， ，如果如果 1. 1. 对任意对任意a,bCa,bC，均有，均有abab 2. 2. 对任意对任意xAxA-C-C，在，在C C中至少存在一个元素中至少存在一个元素c c，使，使 得得 ，则称，

9、则称C C是相容关系是相容关系的最大相容类。的最大相容类。 例如例如 例例1 1中相容关系中相容关系的最大相容类是的最大相容类是例例2 2中相容关系中相容关系的最大相容类是的最大相容类是 CAC,cx,564321TTTTTT,dbacb 3.9.2 3.9.2 相容关系与覆盖相容关系与覆盖(Compatibility(CompatibilityRelations Relations & covers) & covers) 定理定理3.9.1 3.9.1 设设是有限集合是有限集合A A上的一个相容关系，上的一个相容关系， =n=n，则对于任意则对于任意aAaA，必存在一个最大相容类，必存在一个

10、最大相容类C C，使得，使得aCaC。证明证明 设设aAaA ，若对于任意，若对于任意bAbA ，abab均有均有 则则 a a 就是一个最大相容类。就是一个最大相容类。 若存在若存在 ，使得，使得 ，则令则令 由于由于A A中元素个数有限，所以至多经过中元素个数有限，所以至多经过n-1n-1步，这个过程步，这个过程就会终止，而最后得到的就会终止，而最后得到的 ，就是最大相容类且，就是最大相容类且 ba,11baC A11,baAb1ba 对于对于 来说，若存在元素来说，若存在元素 ，使得，使得 与与 中各元素都有相容关系，则又得中各元素都有相容关系，则又得 ， 1C,212bbaC 12CA

11、b2b1CiCaiC 3.9.2 3.9.2 相容关系与覆盖相容关系与覆盖(Compatibility(CompatibilityRelations Relations & covers) & covers) 根据最大相容类的定义，它可以从相容关系根据最大相容类的定义，它可以从相容关系 的的 简化关系图求得，具体方法是：简化关系图求得，具体方法是： （1 1） 的简化关系图中，每一个的简化关系图中，每一个最大完全多边形最大完全多边形的的结点集合，是一个最大相容类。结点集合，是一个最大相容类。（2 2） 的简化关系图中，不在完全多边形中的边的的简化关系图中，不在完全多边形中的边的两个端点的集合，

12、也是一个最大相容类。两个端点的集合，也是一个最大相容类。 （3 3） 的简化关系图中，每一个孤立结点的单点集的简化关系图中，每一个孤立结点的单点集合，是一个最大相容类。合，是一个最大相容类。最大完全多边形最大完全多边形: :其其每个顶点都与其它顶点连接每个顶点都与其它顶点连接的多边形的多边形. . 3.9.2 3.9.2 相容关系与覆盖相容关系与覆盖(Compatibility(CompatibilityRelations Relations & covers) & covers) 例例3 3 设给定相容关系设给定相容关系 的简化关系图如下：的简化关系图如下：求出它求出它 的最大相容类。的最大

13、相容类。解：解： 的最大相容类为：的最大相容类为： a,b,d,f,c,d,f,d,e,ga,b,d,f,c,d,f,d,e,g 定理定理3.9.2 3.9.2 设设是有限集合是有限集合A A上的一个相容关系，上的一个相容关系，则则 的所有最大相容类的集合是的所有最大相容类的集合是A A的一个覆盖。的一个覆盖。 故故 ，S S是是A A的一个覆盖。的一个覆盖。 证明证明 设设 是是的所有最大的所有最大相容类构成的集合相容类构成的集合，显然，显然 niiAC1,21nCCCS 由定理由定理3.9.13.9.1，对任意，对任意aAaA，必存在某个最大相容类，使，必存在某个最大相容类，使得得 ， 因

14、此因此 , , 于是于是 ,iCaniiCa1niiCA1niiAC1 集合集合A A上相容关系上相容关系的最大相容类所构成的的最大相容类所构成的A A的覆的覆盖常记作盖常记作 , ,称为称为A A的完全覆盖的完全覆盖. . )(AC 当当相容关系相容关系确定时确定时, ,由它产生的最大相容类集合是唯由它产生的最大相容类集合是唯一的一的, ,因此因此确定集合确定集合A A的唯一的完全覆盖的唯一的完全覆盖 . . )(AC定理定理3.9.3 3.9.3 设设 是是A A的一个覆盖，的一个覆盖，根据根据S S定义的关系定义的关系 是是A A上的相容关系。上的相容关系。,21nAAAS)()()(2

15、211nnAAAAAA 证明证明 因为因为 ，所以对于任意，所以对于任意aAaA，必然存在某，必然存在某个个 使得使得 ，因此，因此 ，于是于是 ，故，故是自反的。是自反的。 niiAA1)1 (njAjjAajjAAaa ,aa,对于任意对于任意a,bAa,bA ，若，若 ，则必存在某个，则必存在某个 使得使得 因而因而 ，于是，于是 ，故，故是对称是对称的。的。 由上证明由上证明 是是A A上的相容关系。上的相容关系。 ba,)1 (nkAkkkAAba ,kkAAab ,ab,dc,bc,cb,bb,ab,ba,aa, 例例4 4 设设A=a,b,c,dA=a,b,c,d,集合集合 和和 是是A A的两个不同的覆盖，但根据它们构造出的相容的两个不同的覆盖，但根据它们构造出的相容关系均是关系均是,1dcbbaS ,2dbdccbbaS dd,cc,bd,db,cd,注意注意: :由定理由定理3.9.33.9.3可知可知, ,给定集合给定集合A A的任意一个的任意一个覆盖覆盖, ,必可在必可在A A上构造一个对应于此覆盖的一个相上构造一个对应于此覆盖的一个相容关系容关系, ,但是两个不同的覆盖却能构造出的相同但是两个不同的覆盖却能构造出的相同的相容关系的相容关系. .第三章第三章 集合与关系集合与关系(Sets & Relations)小结：本结介绍了相容关系