相容关系(Consistent Relation)是一种重要的二元关系，指集合A上具有自反性与对称性的二元关系。若R是A上的相容关系，S⊆A，S内任何两元素有关系R，而A-S内任何元素至少与S内某一个元素没有关系R，则称S是A关于R的一个极大相容类，S的子集都称为相容类。A的任何一个元素组成的单元集都是一个相容类。任何两个元素a，b只要aRb，就组成相容类a，b。一般地，任何α个元素，只要在关系图中每两个元素都有双向箭头相连，就组成一个相容类，极大相容类是A的具有这个性质的最大子集，A的极大相容类可以不只一个。A的极大相容类可以不只一个。

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

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

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

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

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

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

例如上例的相容关系R,可产生相容类等。

对于相容类，能加进新的元素组成新的相容类，而相容类加入任意一个新元素，就不能组成相容类，这里称作最大相容类。

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

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

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

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

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

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

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

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

解 最大相容类为: 。

定理 设R是有限集A上的相容关系，C是一个相容类，那么一定存在一个最大相容类CR，使得。

证明

设,构造相容类序列

其中 ,且，其中j是满足而与中各元素都有相容关系，且j是满足上述条件的最小下标。

由于A的元素个数,所以至多经过步，就使这个过程结束，而这个序列的最后一个相容类，就是所要找的最大相容类。