《离散数学-3-11相容关系》由会员分享，可在线阅读，更多相关《离散数学-3-11相容关系（12页珍藏版）》请在金锄头文库上搜索。
1、第三章 集合与关系3-11 相容关系 授课人：李朔 Email:1一相容关系n 与等价关系类似，另一类应用非常广泛的关系，就是相容 关系。 n P135 定义3-11.1 给定集合A上的关系r，若r是自反的，对 称的，则称r是A上的相容关系。 例如：设A是由下列英文单词组成的集合。 A=cat, teacher, cold, desk, knife, by。 定义关系： r=x, yA且x和y有相同的字母。易见r是自反，对称的。因此r为相容关系。设 x1=cat, x2=teacher, x3=cold, x4=desk, x5=knife, x6=byr的关系矩阵如下：2一相容关系n 由于r
2、是对称的，因此r的关系矩阵也是对称矩阵，因此， 对相容关系，其关系矩阵只需写出下三角部分即可（简化 矩阵，P136 表3-11.1)。 n 至于关系图，因r是自反和对称的，故每个结点都有环， 且任两点若有连线，必有双向线，因此，大家约定。对相 容关系，在画图时，不画每个元素的环，同时对每对双向 线，只画出单线，这样就更加简洁直观，如上例，关系图 可表示如上右图.3二相容类n P136 定义3-11.2 设r 是集合A上的相容关系，若CA， 且对于C中任两个元素a1, a2有a1 r a2，则称C是由相容关系 r产生的相容类。 n 例如上例的相容关系r可产生相容类。 x1, x2, x1, x3
3、,x2, x3,x6, x2, x4, x5。对于前三个相容类，都能加入新的元素组成新的相容类，而 对于后两个相容类，加入任一新元素，就不再成为相容类 ，我们称它们为最大相容类。 n P137定义3-11.3 设r为集合A上的相容关系，不能真包含在 其它相容类中的相容类。称作最大相容类，记作Cr。若Cr为A上最大相容类，显然它是A的子集，对任何xCr ，x必与Cr中的所有元素有相容关系.而在ACr中没有任何 元素与Cr中所有元素有相容关系。4二相容类n 在相容关系图中，最大完全多边形的顶点集合，就是最大 相容类。所谓完全多边形，就是其每个顶点都与其它顶点 连接的多边形，例如一个三角形是完全多边
4、形，一个四边 形再加两条对角线就是完全多边形。 n 此外，在相容关系图中，一个孤立点，以及不是完全多边 形的两个结点的连线，也是最大相容类。5二相容类n P137例：给定相容关系图写出最大相容类。解：最大相容类为： x1, x2, x4, x5 , x3, x4, x6, x4, x5, x7: 6二相容类n P137定理3-11.1 设r是有限集A上的相容关系，c是一个 相容类，那么必存在最大相容类Cr使c Cr。 证明：设A x1, x2, , xn ，构造相容类序列 C0 C1 C2 ，其中C0 = c 且Ci+1=CiUxj，其中j满足xj Ci且xj与Ci中各元素都相容的 最小足标。
5、 由于A = n，故至多经n- c 步，过程将终止，此时序列中最 后一个相容类，即为所求。 n 由上可见，A中任一元a，可组成相容类a，而它必包含 在一个最大相容类Cr中，因此，由最大相容类构成一个集 合，则A中每一个元素至少属于该集合的一个成员中，即 是说，最大相容类的集合必然构成集合A的一个覆盖。 7三完全覆盖 n P138 定义3-11.4 在集合A上给定相容关系r，其最大的相 容类集合称为A的一个完全覆盖，记Cr(A)。 n 注意到集合A的覆盖不是唯一的，因此给定相容关系r，可 以作成不同的相容类集合，它们都是A的覆盖。但是，给 定相容关系r,只能唯一对应一个完全覆盖。如上例： x1,
6、 x2, x4, x5 , x3, x4, x6, x4, x5, x7反过来，下面讨论由覆盖如何决定一个相容关系。8三完全覆盖 n P138 定理3-11.2 给定集合A的覆盖 A1, A2, , An 。由 它确定的关系：R = A1 A1 A2 A2 An An是A上相容关系。证明： 因A 。对任一xA，必存在某个j0，使xAj，故 Aj Aj，即R。因此R是自反的。 其次，若x, yA且R，则有某个j0使 Aj Aj，故 AjAj。即R。故R是对 称的。 因此R是A上的相容关系。9三完全覆盖 n 从上述可见，给定集合A上的任一个覆盖，必可在A上构造 对应于此覆盖的一个相容关系。但是不同的覆盖却能构造 相同的相容关系。 n 例：A1, 2, 3 集合1, 2, 3, 3, 4和1, 2, 2, 3, 1, 3, 3, 4都是 A的覆盖，但它们可以产生相同的相容关系。R, , , , , ，, , , , , n 但对完全覆盖有： n 定理3-11.3 集合A上相容关系r与完全覆盖存在一一对应。 证明：略 10本课小结n相容关系 n相容类 n完全覆盖11作业nP139 (6)12
