离散数学3.11相容关系课件

1、1,离散数学(Discrete Mathematics),张捷,第三章 集合与关系 （Sets and Relations),3.6 关系的闭包运算(Closure Operations) 3.7 集合的划分与覆盖(Partition 任意两个结点之间,若有弧线,则必为双向的,否则没有弧线.,的关系图为:,的关系矩阵为:,我们也可以省去 中阶梯折线以上的部分，只用下边的梯 形表示相容关系 。,因此我们可以将例1中 的关系图简化为:,a b 1 c 0 1 d 1 1 0,是一个相容关系.,2. 最大相容类（greatest consistent classes） 定义3.9.2 设是有限集A上

2、的相容关系， ，如果 1. 对任意a,bC，均有ab 2. 对任意xA-C，在C中至少存在一个元素c，使 得 ，则称C是相容关系的最大相容类。,例如 例1中相容关系的最大相容类是,例2中相容关系的最大相容类是,3.9.2 相容关系与覆盖(CompatibilityRelations & covers) 定理3.9.1 设是有限集合A上的一个相容关系， =n，则对于任意aA，必存在一个最大相容类C，使得aC。,证明 设aA ，若对于任意bA ，ab均有,则a就是一个最大相容类。,若存在 ，使得 ，,则令,由于A中元素个数有限，所以至多经过n-1步，这个过程就会终止，而最后得到的 ，就是最大相容类

3、且,对于 来说，若存在元素 ，使得 与 中各元素都有相容关系，则又得 ，,3.9.2 相容关系与覆盖(CompatibilityRelations & covers) 根据最大相容类的定义，它可以从相容关系 的 简化关系图求得，具体方法是：,（1） 的简化关系图中，每一个最大完全多边形的结点集合，是一个最大相容类。,（2） 的简化关系图中，不在完全多边形中的边的两个端点的集合，也是一个最大相容类。,（3） 的简化关系图中，每一个孤立结点的单点集合，是一个最大相容类。,最大完全多边形:其每个顶点都与其它顶点连接的多边形.,定理3.9.2 设是有限集合A上的一个相容关系，则 的所有最大相容类的集合

4、是A的一个覆盖。,故 ，S是A的一个覆盖。,证明 设 是的所有最大相容类构成的集合，显然,由定理3.9.1，对任意aA，必存在某个最大相容类，使得 ，,因此 ,于是 ,集合A上相容关系的最大相容类所构成的A的覆盖常记作 ,称为A的完全覆盖.,当相容关系确定时,由它产生的最大相容类集合是唯一的,因此确定集合A的唯一的完全覆盖 .,定理3.9.3 设 是A的一个覆盖，根据S定义的关系 是A上的相容关系。,证明 因为 ，所以对于任意aA，必然存在某个 使得 ，因此 ，于是 ，故是自反的。,例4 设A=a,b,c,d,集合 和 是A的两个不同的覆盖，但根据它们构造出的相容关系均是,注意:由定理3.9.3可知,给定集合A的任意一个覆盖,必可在A上构造一个对应于此覆盖的一个相容关系,但是两个不同的覆盖却能构造出的相同的相容关系.,第三章 集合与关系(Sets & Relations),小结：本结介绍了相容关系、最大相容类、完全覆盖的概念。重点掌握最大相容类的求法及相容关系与覆盖、完全覆盖之间的联系。 思考题：