相容关系

重要的二元关系

相容关系(Consistent Relation)是一种重要的二元关系，指集合A上具有自反性与对称性的二元关系。给定集合A上的关系R，若R是自反的、对称的，则称R是A上的相容关系。相容关系R只要求满足自反性与对称性，因此，等价关系必定是相容关系但反之不真。

定义

定义：设R是集合A上的一个二元关系，如果R是自反的、对称的，则称R 是相容关系。

容易看到，等价关系是一种特殊的相容关系，即具有传递性的相容关系。在人际关系中，朋友关系是相容关系，但它不是等价关系，因为它满足自反性、对称性但不满足传递性。

又如，设A是由一些英文单词为元素组成的集合，A={dog,cat,deer,rat,coat,door}， R是A上的二元关系，其定义为：当两个单词具有相同的字母，则认为它们是相关的。

显然，R是自反的、对称的，所以R是相容关系。但R不是等价关系，因为它不是可传递的。

在相容关系的关系图上，每个结点处都有自回路且每两个相关结点间的弧线都是成对出现的。为了简化图形，我们对相容关系图，不画自回路，并且用单线代替成对的弧线。

相容类

设R是集合A上的一个相容关系，C是A的子集，如果对于C中任意两个元素x，y，有{x，y}∈R，称C是相容关系R产生的相容类。

例如上例的相容关系R,可产生相容类{dog,deer}， {cat, rat, coat}， {door}等。

对于相容类{dog,deer}，能加进新的元素组成新的相容类，而相容类{cat,rat,coat}加入任意一个新元素，就不能组成相容类，这里称作最大相容类。

最大相容类

设R是集合A上的一个相容关系，不能真包含在任何其他相容类中的相容类，称作最大相容类，记作CR。

又如，设A={134，345，275，347， 348，129}， R是A上的二元关系，其定义为: a, b∈A, 且a和b至少有一一个数字相同，则a和b相关。显然R是相容的。A的子集: {134， 347， 348}， {275， 345}， {134， 129}等都是相容类。

对于前两个相容类，都能添加新的元素组成新的相容类。如在相容类{134,347,348}中添加元素: 345，可组成新的相容类: {134， 345， 347, 348};在相容类(275，345}中添加新的元素: 347，可组成新的相容类: {275， 345，347}。因此相容类{134，347， 348}， {275，345}不是最大相容类。

而对于相容类{129，134}，添加任意的元素就不再组成相容类，因此相容类{129，134} 是最大相容类。

对于最大相容类也可以认为: R是A上的相容关系，B是相容类，在差集A-B中没有元素能和B中所有元素都相关的，则称B为最大相容类。

在相容关系图中，完全多边形的结点集合，就是相容类。完全多边形是指每个结点与其他结点联接的多边形。例如一个三角形是完全多边形，一个四边形加上两条对角线就是完全多边形。最大完全多边形的结点集合，就是最大相容类。

此外，在相容关系图中，一个孤立结点，以及不是完全多边形的两个结点的连线，也是最大相容类。

例题解析

例1：设给定相容关系图如图1所示，写出最大相容类。

解：最大相容类为: {1, 2，6}，{1, 4, 5，6}， {1， 7}， {3，6}，{8}。