1、5 覆蓋與劃分覆蓋與劃分定義定義：給定一非空集合，又設：給定一非空集合，又設 若若（1） ),2 , 1( ,miSAi（2） miiSA1則稱則稱A為為S的覆蓋。的覆蓋。 例：例：S=a,b,c，A=a,b,b,c，B=a,a,b,c， C=a,b,c，D=a,b,a,c 集合集合A,B,C,D都為都為S的覆蓋。的覆蓋。 12,miAAAAA，定義定義：給定一非空集合：給定一非空集合S，設非空集合，設非空集合 12,miAA AAA，如果有：如果有： ),2 , 1( ,) 1 (miSAimiiSA1) 3(jiAA )2(（i,j=1,2,m） 則稱集合則稱集合A是集合是集合S的一個劃分

2、。的一個劃分。例：例：S=a,b,c，A=a,b,c，B=a,c,b， C=a,b,c，D=a,b,c 集合集合A,B,C,D都為都為S的劃分。的劃分。 討論定義：討論定義： （2）劃分）劃分A中的元素，稱為劃分的類，在定義中中的元素，稱為劃分的類，在定義中 mAAA21,都是都是A中的一個類，類的個數稱為劃分的秩；中的一個類，類的個數稱為劃分的秩； （1）集合的劃分一定是一個覆蓋，而覆蓋不一定是劃分；）集合的劃分一定是一個覆蓋，而覆蓋不一定是劃分；（3）集合）集合S上的秩最大的劃分稱最大劃分，最小的稱最小劃分。上的秩最大的劃分稱最大劃分，最小的稱最小劃分。 例：設例：設S=a,b,c，下列，

3、下列 iA均為均為S的一個劃分：的一個劃分：,1cbaA 類有二個類有二個a,b,c, 秩為秩為2 ； ,2cbaA 類有二個類有二個a ,b ,c, 秩為秩為2 ； ,3bcaA 類有二個類有二個a,c,b, 秩為秩為2 ； ,4cbaA 秩為秩為3； 類有三個類有三個a,b, c, ,5cbaA 秩為秩為1。 類有一個類有一個a,b ,c, 所以所以A4 是最大劃分，是最大劃分， A5 是最小劃分是最小劃分定義定義：設：設A和和A是非空集合是非空集合S的二種劃分，并可表示成：的二種劃分，并可表示成： , 1miiAAnjjAA1若若A的每一個類的每一個類 jA都是都是A的某一個類的某一個類

4、 iA的子集，則稱劃分的子集，則稱劃分A是劃分是劃分A的加細，的加細， 或講或講A加細了加細了A，若，若A加細了加細了A且且 AA 則稱則稱A是是A的真加細。的真加細。例：例：S=a,b,c,d,S的劃分：的劃分：A=a,b,c,d,A=abc,d，則，則A是是A的真加細的真加細 A=abcd,則則A 是是A的真加細的真加細 定義定義：設：設X是一個集合，是一個集合，R是是X中的二元關系，若中的二元關系，若R是是自反自反的，的，對稱對稱的和的和可傳遞可傳遞的，則稱的，則稱R是等價關系。是等價關系。例：實數集合上的例：實數集合上的“=”關系（相等）為等價關系關系（相等）為等價關系6 等價關系等價

5、關系試驗證試驗證R是等價關系，是等價關系， 畫出畫出R的關系圖，列出的關系圖，列出R的關系矩陣的關系矩陣 解：（解：（1）R=（2）R的關系矩陣和關系圖的關系矩陣和關系圖 1 0 0 10 1 0 00 0 1 01 0 0 1RMR滿足自反、對稱和傳遞性質，滿足自反、對稱和傳遞性質，R是等價關系是等價關系例：設例：設A=1,2,3,4， R是是A集合上的二元關系集合上的二元關系,| ,3xyRx yx yA 為整數為整數定義定義：設：設 ImIyx,若若myx 為整數，為整數， 則稱則稱x模模m等于等于y，記作：，記作： )(mod myx R=| ，則，則R是一個等價關系。是一個等價關系。

6、 )(mod myx 定理定理：任何集合：任何集合 AI，R是集合是集合A中的關系，中的關系，mI，例：設例：設A=0，1，2，3，6，R=x,y|xy(x,yA)yx(mod 3)，計算計算domR和和ranR。定義定義：設：設R是是A集合中的等價關系，對于任何的集合中的等價關系，對于任何的 Ax來講，可把集合來講，可把集合 AxR規定成：規定成： |xRyAyyxR并稱是由并稱是由 Ax生成的生成的R等價類。等價類。RRddcc,RRbbaa,例：設例：設A=a,b,c,d,R是是A中的等價關系，中的等價關系，R=（1） AxR（2） Rx（3）若）若 Ax，則，則 Rxx（4）對于所有的

7、）對于所有的 Ayx,，或者，或者 RRyx或者或者 RRyx（5） XxRAx定理定理：設：設A是一個非空集合，是一個非空集合，R是是A中的等價關系，則中的等價關系，則例：設例：設X=N，關系，關系R= )3(mod|,yxXyXxyx是一等價關系，是一等價關系， 則則R可以找出三個等價類：可以找出三個等價類：R0=0，3，6，9R 1 =1，4，7，10R2=2，5，8，11定理定理：設：設A是一非空集合，是一非空集合，R是是A中的等價關系，中的等價關系，R等價類的集合等價類的集合xR| x A是是A的一個劃分，且此集合的一個劃分，且此集合稱為稱為A關于關于R的商集，用的商集，用 RA表示

8、之。例：設例：設A=x1,x2.xn （1）A集合中的全域關系集合中的全域關系: AAR1是一個等價關系，是一個等價關系， 1, RxA xA X關于關于R1的商集的商集1|,|11RAAxxRAR它形成了它形成了A的一個最小劃分的一個最小劃分 （2）A中的恒等關系中的恒等關系 xIR 2|22AxxRAR221RnRxx),(21Axxxn它形成了它形成了A的一個最大劃分的一個最大劃分 定理定理：X是一非空集合，是一非空集合， A為為X的一個劃分，且的一個劃分，且A=A1,A2,.An，則由，則由A導出的導出的X中的一個等價關系中的一個等價關系)(1iiniAAR例：例：Xa,b,c,d，A

9、=a,b,c,d則則 R(a,b a,b) (c,d c,d) =, 因此：集合因此：集合X上的等價關系與上的等價關系與X的劃分之間有一一對應關系。的劃分之間有一一對應關系。定義定義：設：設X是一個集合，是一個集合，R是是X中的二元關系，若中的二元關系，若R是是自反的，對稱的自反的，對稱的，則稱，則稱R是是相容關系相容關系。 由定義知由定義知, 等價關系是具有等價關系是具有傳遞性傳遞性的相容關系的相容關系; 相容關相容關 系是一個比等價關系更為普遍的關系。系是一個比等價關系更為普遍的關系。7 相容關系相容關系因為相容關系是自反和對稱的因為相容關系是自反和對稱的, 其關系矩陣是對稱的且其關系矩陣

10、是對稱的且主對角線元素全為主對角線元素全為1, 因此我們可僅用下三角矩陣因此我們可僅用下三角矩陣T來表來表示和存儲就夠了示和存儲就夠了, 即關系矩陣可以簡化為即關系矩陣可以簡化為“階梯形階梯形”。EX：設：設A = cat, teacher, cold, desk, knife, byR = x, y|x, y A 且且 x和和y至少有一個相同的字母至少有一個相同的字母R 是是 A上的一個相容關系上的一個相容關系, 簡記簡記 A 中元素依次為中元素依次為x1, x2, x3, x4, x5, x6, 則則R的關系矩陣的關系矩陣MR和對應簡化的下三角矩陣和對應簡化的下三角矩陣TR為：為：1110

11、00111110111100011110010110000001RM111111011101011000001RTcatteacher cold desk knife bycat teacher cold desk knife byEX：在相容關系的關系圖上，每個頂點都有：在相容關系的關系圖上，每個頂點都有自回路自回路且每兩個頂點且每兩個頂點間的弧線都是間的弧線都是成對出現成對出現的。為簡化相容關系的關系圖的。為簡化相容關系的關系圖, 不畫自回路不畫自回路, 并用無箭頭的單線段代替來回弧線并用無箭頭的單線段代替來回弧線, 使之成為無向圖。上例的關系使之成為無向圖。上例的關系圖如下圖如下:x1x

12、2x3x4x5x6定義定義1：設：設R是集合是集合A上的相容關系上的相容關系, 若若C A, 若任意若任意a,b C, 有有aRb, 則稱則稱C是由是由R產生的相容類。產生的相容類。例如上例的相容關系例如上例的相容關系R可產生相容類可產生相容類x1,x2，x1,x3，x2,x3，x6，x2,x4,x5，等等。，等等。對于前三個相容類，都能加進新的元素組成新的相容類，而對于前三個相容類，都能加進新的元素組成新的相容類，而后兩個相容類，加入任一新元素，就不能組成相容類，我們后兩個相容類，加入任一新元素，就不能組成相容類，我們稱它為最大相容類。稱它為最大相容類。x3x2x1求最大相容類的方法：求最大

13、相容類的方法： 關系圖法：畫出簡化相容關系的關系圖后，先確定結點最多的完關系圖法：畫出簡化相容關系的關系圖后，先確定結點最多的完全多邊形，以后逐次減少。全多邊形，以后逐次減少。最大完全多邊形最大完全多邊形:每個頂點都與其他所有頂點相聯結的多邊形。每個頂點都與其他所有頂點相聯結的多邊形。 (1) 一個結點的最大的完全多邊形；一個結點的最大的完全多邊形； (2) 二個結點的最大完全多邊形；二個結點的最大完全多邊形； (3) 三個結點的最大完全多邊形；三個結點的最大完全多邊形； (4)四個結點的最大完全多邊形；四個結點的最大完全多邊形； (5)五個結點的最大完全多邊形五個結點的最大完全多邊形;最大完全多邊形最大完全多邊形例：已知相容關系圖，求出最大相容類例：已知相容關系圖，求出最大相容類5 , 45 , 23 , 24 , 3 , 14321XXXX4 , 35 , 4 , 16 , 5 , 2 , 1321XXX最大相容類集合為：最大相容類集合為：121,3,42,32,54,5,1,2,5,61,4,53,4SS