相容關系(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的元素個數,所以至多經過步，就使這個過程結束，而這個序列的最后一個相容類，就是所要找的最大相容類。
參考資料 >