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

第三章 集合与关系 3-11 相容关系 授课人：李朔 Email:chn.nj.ls@ 一．相容关系 与等价关系类似，另一类应用非常广泛的关系，就是相容关系。 P135 定义3-11.1 给定集合A上的关系r，若r是自反的，对称的，则称r是A上的相容关系。 例如：设A是由下列英文单词组成的集合。 A={cat, teacher, cold, desk, knife, by}。 定义关系： r={x, y?x, y?A且x和y有相同的字母}。 易见r是自反，对称的。因此r为相容关系。 设 x1=cat, x2=teacher, x3=cold, x4=desk, x5=knife, x6=by r的关系矩阵如下： 一．相容关系 由于r是对称的，因此r的关系矩阵也是对称矩阵，因此，对相容关系，其关系矩阵只需写出下三角部分即可（简化矩阵，P136 表3-11.1)。 至于关系图，因r是自反和对称的，故每个结点都有环，且任两点若有连线，必有双向线，因此，大家约定。对相容关系，在画图时，不画每个元素的环，同时对每对双向线，只画出单线，这样就更加简洁直观，如上例，关系图可表示如上右图. 二．相容类 P136 定义3-11.2 设r 是集合A上的相容关系，若C?A，且对于C中任两个元素a1, a2有a1 r a2，则称C是由相容关系r产生的相容类。 例如上例的相容关系r可产生相容类。 { x1, x2},{ x1, x3},{x2, x3},{x6},{ x2, x4, x5}。 对于前三个相容类，都能加入新的元素组成新的相容类，而对于后两个相容类，加入任一新元素，就不再成为相容类，我们称它们为最大相容类。 P137定义3-11.3 设r为集合A上的相容关系，不能真包含在其它相容类中的相容类。称作最大相容类，记作Cr。 若Cr为A上最大相容类，显然它是A的子集，对任何x?Cr，x必与Cr中的所有元素有相容关系.而在A－Cr中没有任何元素与Cr中所有元素有相容关系。 二．相容类 在相容关系图中，最大完全多边形的顶点集合，就是最大相容类。所谓完全多边形，就是其每个顶点都与其它顶点连接的多边形，例如一个三角形是完全多边形，一个四边形再加两条对角线就是完全多边形。 此外，在相容关系图中，一个孤立点，以及不是完全多边形的两个结点的连线，也是最大相容类。 二．相容类 P137例：给定相容关系图写出最大相容类。 解：最大相容类为： { x1, x2, x4, x5 }, { x3, x4, x6}, {x4, x5}, {x7}: 二．相容类 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 ?步，过程将终止，此时序列中最后一个相容类，即为所求。 由上可见，A中任一元a，可组成相容类{a}，而它必包含在一个最大相容类Cr中，因此，由最大相容类构成一个集合，则A中每一个元素至少属于该集合的一个成员中，即是说，最大相容类的集合必然构成集合A的一个覆盖。 三．完全覆盖 P138 定义3-11.4 在集合A上给定相容关系r，其最大的相容类集合称为A的一个完全覆盖，记Cr(A)。 注意到集合A的覆盖不是唯一的，因此给定相容关系r，可以作成不同的相容类集合，它们都是A的覆盖。但是，给定相容关系r,只能唯一对应一个完全覆盖。如上例： {{ x1, x2, x4, x5 }, { x3, x4, x6}, {x4, x5}, {x7}} 反过来，下面讨论由覆盖如何决定一个相容关系。 三．完全覆盖 P138 定理3-11.2 给定集合A的覆盖{ A1, A2, ?, An }。由它确定的关系： R = A1 ? A1? A2? A2??? An ? An 是A上相容关系。 证明： 因A＝ 。对任一x?A，必存在某个j0，使x?Aj，故 x, x? Aj ?Aj，即x, x?R。因此R是自反的。 其次，若x, y?A且x, y?R，则有某个j0使 x, y? Aj ?Aj，故y, x? Aj?Aj。即y, x?R。故R是对称的。 因此R是A上的相容关系。 三．完全覆盖 从上述可见，给定集合A上的任一个覆盖，必可在A上构造对应于此覆盖的一个相容关系。但是不同的覆盖却能构造相同的相容关系。 例：A＝{1, 2,