定义定义10.7.1 对非空集合A上的关系R,如果R是自反的、对称的,则称RA上的相容关系。
例题例1 A是英文单词的集合
    
  A上的关系R
  y至少有一相同字母}
  显然,R是自反的、对称的,但不是传递的。因此,R是相容关系。
  相容关系的关系矩阵的对角线元素都是1,且矩阵是对称的。相容关系的关系图中,每个顶点都有自圈,而且若一对顶点间有边则有向边成对出现。因此可以简化关系图,可以不画自圈,并用无向边代替一对来回的有向边。对例1的R,设
    
  则关系图可以简化为图10.7.1。
图示图 10.7.1
   
定义定义10.7.2 (相容类) 对非空集合A上的相容关系R,若,且C中任意两个元素xyxRy,则称C是由相容关系R产生的相容类,简称相容类。
  这个定义也可以写成
    
例题例2 对例1中的相容关系R,相容类有等。前两个相容类都可以加入其他元素,构成更大的相容类。如加入得到另一相容类。后两个相容类再加入任何新元素就不是相容类了,这两个相容类成为最大相容类。
定义定义10.7.3 对非空集合A上的相容关系R,一个相容类若不是任何相容类的真子集,就称为最大相容类,记作
  对最大相容类有下列性质:
   
  和
   
  上面两个公式的含义为若为最大相容类,显然它是A的子集,对于任意x必与中所有元素有相容关系。而在 中没有任何元素与所有元素有相容关系。
  在相容关系的简化图中,最大完全多边形是每个顶点与其他所有顶点相连的多边形。这种最大完全多边形的顶点集合,才是最大相容类。此外,一个孤立点的集合也是最大相容类;如果两点连线不是最大完全多边形的边,这两个顶点的集合也是最大相容类。
例题例3 对例1的相容关系R,最大相容类有
定理定理10.7.1 对非空有限集合A上的相容关系R,若C是一个相容类,则存在一个最大相容类,使
证明证明。构造相容类的序列
    
  使,而j是满足中各元素有关系R的最小下标。
  因为,所以至多经过步,过程就结束,而且序列中最后一个相容类是。结论得证。
  对任意的,有相容类 。它必定包含在某个中。所以,的集合覆盖住A