离散数学-3-11相容关系.ppt

第三章 集合与关系3-11 相容关系 授课人：李朔 Email:chn.nj.ls@1一．相容关系n 与等价关系类似，另一类应用非常广泛的关系，就是相容 关系 n 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为相容关系设 x1=cat, x2=teacher, x3=cold, x4=desk, x5=knife, x6=byr的关系矩阵如下：2一．相容关系n 由于r是对称的，因此r的关系矩阵也是对称矩阵，因此， 对相容关系，其关系矩阵只需写出下三角部分即可（简化 矩阵，P136 表3-11.1) n 至于关系图，因r是自反和对称的，故每个结点都有环， 且任两点若有连线，必有双向线，因此，大家约定对相 容关系，在画图时，不画每个元素的环，同时对每对双向 线，只画出单线，这样就更加简洁直观，如上例，关系图 可表示如上右图.3二．相容类n P136 定义3-11.2 设r 是集合A上的相容关系，若CA， 且对于C中任两个元素a1, a2有a1 r a2，则称C是由相容关系 r产生的相容类。

n 例如上例的相容关系r可产生相容类 { x1, x2},{ x1, x3},{x2, x3},{x6},{ x2, x4, x5}对于前三个相容类，都能加入新的元素组成新的相容类，而 对于后两个相容类，加入任一新元素，就不再成为相容类 ，我们称它们为最大相容类 n P137定义3-11.3 设r为集合A上的相容关系，不能真包含在 其它相容类中的相容类称作最大相容类，记作Cr若Cr为A上最大相容类，显然它是A的子集，对任何xCr ，x必与Cr中的所有元素有相容关系.而在A－Cr中没有任何 元素与Cr中所有元素有相容关系4二．相容类n 在相容关系图中，最大完全多边形的顶点集合，就是最大 相容类所谓完全多边形，就是其每个顶点都与其它顶点 连接的多边形，例如一个三角形是完全多边形，一个四边 形再加两条对角线就是完全多边形 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=CiU{xj}，其中j满足xj Ci且xj与Ci中各元素都相容的 最小足标 由于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, 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＝ 对任一xA，必存在某个j>0，使xAj，故  Aj Aj，即R因此R是自反的 其次，若x, yA且R，则有某个j>0使  Aj Aj，故 AjAj故R是对 称的 因此R是A上的相容关系9三．完全覆盖 n 从上述可见，给定集合A上的任一个覆盖，必可在A上构造 对应于此覆盖的一个相容关系但是不同的覆盖却能构造 相同的相容关系 n 例：A＝{1, 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。