相容關係
重要的二元關係
相容關係(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所示，寫出最大相容類。
圖1
定理 設R是有限集A上的相容關係，C是一個相容類，那麼一定存在一個最大相容類C，使得。
證明
設,構造相容類序列
其中 ,且，其中j是滿足而與中各元素都有相容關係，且j是滿足上述條件的最小下標。
由於A的元素個數,所以至多經過步，就使這個過程結束，而這個序列的最後一個相容類，就是所要找的最大相容類。
基本信息
- 外文名
- Consistent Relation
- 應用領域
- 數理科學
- 所屬學科
- 數學（集合論）