定义10.7.1
对非空集合A上的关系R,如果R是自反的、对称的,则称R为A上的相容关系。
例1
A是英文单词的集合
,
A上的关系R为
和y至少有一相同字母}。
显然,R是自反的、对称的,但不是传递的。因此,R是相容关系。
相容关系的关系矩阵的对角线元素都是1,且矩阵是对称的。相容关系的关系图中,每个顶点都有自圈,而且若一对顶点间有边则有向边成对出现。因此可以简化关系图,可以不画自圈,并用无向边代替一对来回的有向边。对例1的R,设

则关系图可以简化为图10.7.1。
图
10.7.1

定义10.7.2
(相容类) 对非空集合A上的相容关系R,若 ,且C中任意两个元素x和y有xRy,则称C是由相容关系R产生的相容类,简称相容类。
这个定义也可以写成
。
例2
对例1中的相容关系R,相容类有 , , , 等。前两个相容类都可以加入其他元素,构成更大的相容类。如 加入 得到另一相容类 。后两个相容类再加入任何新元素就不是相容类了,这两个相容类成为最大相容类。
定义10.7.3
对非空集合A上的相容关系R,一个相容类若不是任何相容类的真子集,就称为最大相容类,记作 。
对最大相容类 有下列性质:

和
。
上面两个公式的含义为若 为最大相容类,显然它是A的子集,对于任意 ,x必与 中所有元素有相容关系。而在
中没有任何元素与 所有元素有相容关系。
在相容关系的简化图中,最大完全多边形是每个顶点与其他所有顶点相连的多边形。这种最大完全多边形的顶点集合,才是最大相容类。此外,一个孤立点的集合也是最大相容类;如果两点连线不是最大完全多边形的边,这两个顶点的集合也是最大相容类。
例3
对例1的相容关系R,最大相容类有 和 。
定理10.7.1
对非空有限集合A上的相容关系R,若C是一个相容类,则存在一个最大相容类 ,使 。
证明
设 。构造相容类的序列
使 ,而j是满足 且 与 中各元素有关系R的最小下标。
因为 ,所以至多经过 步,过程就结束,而且序列中最后一个相容类是 。结论得证。
对任意的 ,有相容类
。它必定包含在某个 中。所以, 的集合覆盖住A。
|