1、1第4章 關系n4.1 關系的定義及其表示關系的定義及其表示n4.2 關系運算關系運算n4.3 關系的性質關系的性質n4.4 等價關系與偏序關系等價關系與偏序關系24.1 關系的定義及其表示n4.1.1 有序對與笛卡兒積有序對與笛卡兒積n4.1.2 二元關系的定義二元關系的定義n4.1.3 二元關系的表示二元關系的表示3定義定義4.1 由兩個元素，如由兩個元素，如x和和y，按照一定的順序，按照一定的順序組成的二元組稱為組成的二元組稱為有序對有序對，記作，記作 實例：點的直角坐標實例：點的直角坐標 (3, 4) 有序對的性質有序對的性質 有序性有序性 （當（當x y時）時） 與與相等的充分必要條

2、件是相等的充分必要條件是 = x=u y=v例例1 =，求，求 x, y. 解解 3y 4=2, x+5=y y=2, x= 3 有序對4笛卡兒積定義定義4.2 設設A, B為集合，為集合，A與與B 的的笛卡兒積笛卡兒積記作記作A B， A B = | x A y B .例例2 A=0, 1, B=a, b, c A B=, B A =, A = , B = P(A) A = , P(A) B = 5笛卡兒積的性質對于并或交運算滿足分配律對于并或交運算滿足分配律 A (B C)=(A B) (A C) (B C) A=(B A) (C A) A (B C)=(A B) (A C) (B C)

3、A=(B A) (C A) 若若A或或B中有一個為空集，則中有一個為空集，則A B就是空集就是空集. A=B= 不適合交換律不適合交換律 A B B A (A B, A, B)不適合結合律不適合結合律 (A B) C A (B C) (A, B, C)若若|A|=m, |B|=n, 則則 |A B|=mn 6有序 n 元組和 n 階笛卡爾積 定義定義4.3 (1) 由由 n 個元素個元素 x1, x2, , xn按照一定的順序排列構成按照一定的順序排列構成 有序有序 n 元組元組，記作，記作 (2) 設設A1, A2, , An為集合，稱為集合，稱 A1 A2 An= | xi Ai, i=1

4、,2, ,n 為為 n 階笛卡兒積階笛卡兒積. 實例實例 (1,1,0)為空間直角坐標，為空間直角坐標，(1,1,0) R R R7二元關系的定義定義定義4.4如果一個集合滿足以下條件之一：如果一個集合滿足以下條件之一：（1）集合非空）集合非空, 且它的元素都是有序對且它的元素都是有序對（2）集合是空集）集合是空集則稱該集合為一個則稱該集合為一個二元關系二元關系, 簡稱為簡稱為關系關系，記作，記作R.如如R, 可記作可記作 xRy；如果；如果 R, 則記作則記作x y實例：實例：R=, S=,a,b. R是二元關系是二元關系, 當當a, b不是有序對時，不是有序對時，S不是二元關系不是二元關系

5、根據上面的記法，可以寫根據上面的記法，可以寫1R2, aRb, a c等等. 8實例 例3 (1) R= | x,yN, x+y3 =, , , , , (2) C= | x,yR, x2+y2=1，其中R代表實數(shù)集合， C是直角坐標平面上點的橫、縱坐標之間的關系， C中的所有的點恰好構成坐標平面上的單位圓. (3) R= | x,y,zR, x+2y+z=3， R代表了空間直角坐標系中的一個平面. 95元關系的實例數(shù)據庫實體模型員工號員工號姓名姓名年齡年齡性別性別工資工資301302303304 張張 林林王曉云王曉云李鵬宇李鵬宇趙趙 輝輝 50434721 男男女女男男男男 1600125

6、01500900 5元組：元組：，10從A到B的關系與A上的關系nm2定義定義4.5 設設A,B為集合為集合, AB的任何子集所定義的二元關系叫做的任何子集所定義的二元關系叫做從從 A 到到 B 的二元關系的二元關系, 當當 A=B 時則叫做時則叫做 A上的二元關系上的二元關系.例例4 A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=, 從從A到到B的關系的關系: R1, R2, R3, R4, A上的關系上的關系R3和和R4. 計數(shù)：計數(shù)：|A|=n, |B|=m, |AB|=nm, AB 的子集有的子集有 個個. 所以從所以從A到到B有有 個不同的二元關系個不同的二

7、元關系. |A|=n, A上有上有 不同的二元關系不同的二元關系. 例如例如 |A|=3, 則則 A上有上有512個不同的二元關系個不同的二元關系. 22nnm211A上重要關系的實例設設A為任意集合，為任意集合，是是A上的關系，稱為上的關系，稱為空關系空關系定義定義 4.6 EA, IA分別稱為分別稱為全域關系全域關系與與恒等關系恒等關系，其中，其中 EA= | xA yA=AA IA= | xA例如例如, A=1,2, 則則 EA=, IA=,12A上重要關系的實例（續(xù)）小于等于關系小于等于關系LA, 整除關系整除關系DA, 包含關系包含關系R 定義如下：定義如下：定義定義4.7 LA=|

8、 x,yAxy, 這里這里A R，R為實數(shù)集合為實數(shù)集合 DB=| x,yBx整除整除y, B Z*, Z*為非為非0整數(shù)集整數(shù)集 R =| x,yAx y, 這里這里A是集合族是集合族.例如例如 A=1,2,3, B=a,b, 則則 LA=, DA=, A=P(B)=,a,b,a,b, 則則A上的包含關系是上的包含關系是 R =, ,類似的還可以定義類似的還可以定義大于等于關系大于等于關系, 小于關系小于關系, 大于關系大于關系, 真真包含關系包含關系等等等等. 13矩陣的定義定義定義 由由mn個數(shù)個數(shù)aij(i(i=1,2,m, j=1,2,n)=1,2,m, j=1,2,n)排成的排成的

9、一個一個m行行n列的矩形表，稱為列的矩形表，稱為mn矩陣。記為矩陣。記為mnm2m12n22211n1211aaaaaaaaa14定義定義 矩陣的乘法msm2m12s22211s1211smijaaaaaaaaa)a (Asns2s12n22211n1211nsijbbbbbbbbb)b(Bmnm2m12n22211n1211nmijccccccccc)c (AB，其中，skbabababac1kjiksjis2ji21ji1ij(i=1,2,(i=1,2,m, j=1,2,m, j=1,2,n),n) 15矩陣的乘法64533134037160513230017263503743101216

10、關系的表示表示方式：關系的集合表達式、關系矩陣、關系圖表示方式：關系的集合表達式、關系矩陣、關系圖 定義定義4.8 關系矩陣關系矩陣 若若A=x1, x2, , xm，B=y1, y2, , yn，R是從是從A到到B的關系，的關系，R的關系矩陣是布爾矩陣的關系矩陣是布爾矩陣MR = rij m n, 其中其中 rij = 1 R. 定義定義4.9 關系圖關系圖 若若A= x1, x2, , xm，R是從是從A上的關系，上的關系，R的關系圖是的關系圖是GR=, 其中其中A為結點集，為結點集，R為邊集為邊集.如果如果屬于關系屬于關系R，在圖中就有一條從，在圖中就有一條從 xi 到到 xj 的有向邊

11、的有向邊. 注意：設注意：設A, B為有窮集為有窮集關系矩陣適合于表示從關系矩陣適合于表示從A到到B 的關系或者的關系或者A上的關系上的關系關系圖適合于表示關系圖適合于表示A上的關系上的關系 17實例例例5 A=a, b, c, d, R=,R的關系矩陣的關系矩陣 MR 和關系圖和關系圖 GR 如下：如下：001000000001011118n4.2.1 關系的基本運算關系的基本運算n定義域、值域、域、逆、合成定義域、值域、域、逆、合成n基本運算的性質基本運算的性質n4.2.2 關系的冪運算關系的冪運算n冪運算的定義冪運算的定義n冪運算的方法冪運算的方法n冪運算的性質冪運算的性質4.2 關系運

12、算19關系的基本運算定義定義4.10 定義域定義域、值域值域 和和 域域 domR = x | y ( R) ranR = y | x ( R) fldR = domR ranR 例例1 R=, 則則 domR = ranR = fldR = a, c, a, d, b, d a, c, a, d b, d, d20關系的基本運算（續(xù)）定義定義4.11 R 的的逆逆 R 1 = | R定義定義4.12 R與與S的的合成合成 R S = | y ( R S) 例例2 R=, , , S=, , , , R 1 = R S = S R =, , , , , , , 21合成運算的圖示方法 利用圖示

13、（不是關系圖）方法求合成利用圖示（不是關系圖）方法求合成 R S =, , S R =, , , 22 ）（jkijnjiksrc1用矩陣表示兩個關系的復合23100000100010RM00010000011000000100SM000101000010000 SRCMM1)()()()(451435132512151115srsrsrsrc例題24基本運算的性質 定理定理4.1 設設F是任意的關系是任意的關系, 則則(1) (F 1) 1=F(2) domF 1=ranF, ranF 1=domF證證 (1) 任取任取, 由逆的定義有由逆的定義有 (F 1) 1 F 1 F所以有所以有 (

14、F 1) 1=F(2) 任取任取x, xdomF 1 y (F 1) y (F) xranF 所以有所以有domF 1= ranF. 同理可證同理可證 ranF 1 = domF.25定理定理4.2 設設F, G, H是任意的關系是任意的關系, 則則 (1) (F G) H=F (G H) (2) (F G) 1= G 1 F 1 證證 (1) 任取任取, (F G) H t (F GH) t ( s (FG)H) t s (FGH) s (F t (GH) s (FG H) F (G H) 所以所以 (F G) H = F (G H)基本運算的性質（續(xù)） 26(2) 任取任取, (F G)

15、1 F G t (F(t, x)G) t (G 1(t, y)F 1) G 1 F 1所以所以 (F G) 1 = G 1 F 1 基本運算的性質（續(xù)） 27定理定理4.3 設設 R 為為 A上的關系上的關系, 則則 R IA= IA R = R 證明證明任取任取 R IA t (RIA) t (Rt=yyA) R從而有從而有R IA=R. 同理可證同理可證 IA R=R. 基本運算的性質（續(xù)） 28A上關系的冪運算定義定義定義4.13 設設R為為A上的關系上的關系, n為自然數(shù)為自然數(shù), 則則 R 的的 n次冪次冪是是 (1) R0 = | xA = IA (2) Rn+1 = Rn R 注

16、意：注意： 對于對于A上的任何關系上的任何關系R1和和R2都有都有 R10 = R20 = IA 對于對于A上的任何關系上的任何關系 R 都有都有 R1 = R 29冪運算的方法對于集合表示的關系對于集合表示的關系R，計算，計算Rn 就是就是 n 個個 R 合成合成 . 矩陣表示的關系就是矩陣相乘矩陣表示的關系就是矩陣相乘, 其中相加采用邏輯加其中相加采用邏輯加. 例例3 設設A = a, b, c, d, R = , 求求R的各次冪的各次冪, 分別用矩陣和關系圖表示分別用矩陣和關系圖表示.解解 R與與R2的關系矩陣分別為的關系矩陣分別為 0000100001010010M 000000001

17、0100101000010000101001000001000010100102M30同理同理R3和和R4的矩陣是：的矩陣是：因此因此M4 = M2, 即即R4 = R2. 因此可以得到因此可以得到R2 = R4 = R6 = , R3 = R5 = R7 = 而而R0 = IA的關系矩陣的關系矩陣 0000000010100101,000000000101101043MM 10000100001000010M冪運算的方法（續(xù)）31用關系圖的方法得到用關系圖的方法得到R0, R1, R2, R3,的關系圖如下圖所示的關系圖如下圖所示冪運算的方法（續(xù)）32冪運算的性質定理定理4.4 設設 A 為

18、為 n 元集元集, R是是A上的關系上的關系, 則存在自然數(shù)則存在自然數(shù) s 和和 t, 使得使得 Rs = Rt.證證 R 為為A上的關系上的關系, 由于由于|A| = n, A上的不同關系只有上的不同關系只有 個個. 當列出當列出 R 的各次冪的各次冪 R0, R1, R2, , , , 必存在自然數(shù)必存在自然數(shù) s 和和 t 使得使得 Rs = Rt.22n33定理定理4.5 設設 R 是是 A 上的關系上的關系, m, nN, 則則 (1) Rm Rn = Rm+n (2) (Rm)n = Rmn 證證 用歸納法用歸納法 (1) 對于任意給定的對于任意給定的 mN, 施歸納于施歸納于

19、n.若若n=0, 則有則有 Rm R0 = Rm IA= Rm = Rm+0 假設假設 Rm Rn = Rm+n, 則有則有Rm Rn+1 = Rm (Rn R) = (Rm Rn) R = Rm+n+1 , 所以對一切所以對一切 m, nN 有有 Rm Rn = Rm+n. 冪運算的性質（續(xù)）34(2) 對于任意給定的對于任意給定的 mN, 施歸納于施歸納于 n. 若若 n = 0, 則有則有 (Rm)0 = IA = R0 = Rm0 假設假設 (Rm)n = Rmn, 則有則有(Rm)n+1 = (Rm)n Rm = (Rmn) Rm = Rmn+m = Rm(n+1) 所以對一切所以對

20、一切 m, nN 有有 (Rm)n = Rmn. 冪運算的性質（續(xù)）35定理定理4.6 設設R 是是A上的關系上的關系, 若存在自然數(shù)若存在自然數(shù) s, t (st) 使得使得 Rs = Rt, 則則 (1) 對任何對任何 kN 有有 Rs+k = Rt+k (2) 對任何對任何 k, iN 有有Rs+kp+i = Rs+i, 其中其中p = t s (3) 令令S=R0,R1, , Rt 1, 則對于任意的則對于任意的 qN有有 RqS證明證明 (1) Rs+k = Rs Rk = Rt Rk = Rt+k （2）對）對 k 歸納歸納. 若若k=0, 則有則有 Rs+0p+i = Rs+i假

21、設假設 Rs+kp+i = Rs+i, 其中其中p = t s, 則則Rs+(k+1)p+i = Rs+kp+i+p = Rs+kp+i Rp = Rs+i Rp = Rs+p+i = Rs+t s+i = Rt+i = Rs+i 由歸納法命題得證由歸納法命題得證.冪運算的性質（續(xù)）36(3) 任取任取 qN, 若若qt, 顯然有顯然有 RqS. 若若 qt, 則存在自然數(shù)則存在自然數(shù) k 和和 i 使得使得 q = s+kp+i，其中，其中0ip 1. 于是于是Rq = Rs+kp+i = Rs+i 而而 s+i s+p 1 = s+t s 1 = t 1 這就證明了這就證明了 RqS.冪運

22、算的性質（續(xù)）374.3 關系的性質n4.3.1關系性質的定義和判別關系性質的定義和判別n自反性與反自反性自反性與反自反性n對稱性與反對稱性對稱性與反對稱性n傳遞性傳遞性n4.3.2 關系的閉包關系的閉包n閉包定義閉包定義n閉包計算閉包計算n Warshall算法算法 38自反性與反自反性定義定義4.14 設設R為為A上的關系上的關系, (1) 若若 x(xA R), 則稱則稱R在在A上是上是自反自反的的. (2) 若若 x(xA R), 則稱則稱R在在A上是上是反自反反自反的的.自反：自反：A上的全域關系上的全域關系EA, 恒等關系恒等關系IA, 小于等于關系小于等于關系LA, 整除關系整除

23、關系DA反自反：實數(shù)集上的小于關系、冪集上的真包含關系反自反：實數(shù)集上的小于關系、冪集上的真包含關系.R2自反自反, R3 反自反反自反, R1既不自反也不反自反既不自反也不反自反.例例1 A = a, b, c, R1, R2, R3 是是 A上的關系上的關系, 其中其中 R1 = , R2 = , R3 = 39對稱性與反對稱性例例2 設設Aa,b,c, R1, R2, R3和和R4都是都是A上的關系上的關系, 其中其中 R1,， R2, R3,， R4,定義定義4.15 設設R為為A上的關系上的關系, (1) 若若 x y(x,yARR), 則稱則稱R為為A上上 對稱對稱的關系的關系.(

24、2) 若若 x y(x,yARRx=y), 則稱則稱R 為為A上的上的反對稱反對稱關系關系.實例實例 對稱：對稱：A上的全域關系上的全域關系EA, 恒等關系恒等關系IA和空關系和空關系 反對稱：恒等關系反對稱：恒等關系IA，空關系是空關系是A上的反對稱關系上的反對稱關系R1 對稱、反對稱對稱、反對稱. R2 對稱對稱. R3 反對稱反對稱. R4 不對稱、也不反對稱不對稱、也不反對稱40傳遞性 例例3 設設Aa, b, c, R1, R2, R3是是A上的關系上的關系, 其中其中 R1, R2, R3定義定義4.16 設設R為為A上的關系上的關系, 若若 x y z(x,y,zARRR),則稱

25、則稱R是是A上的上的傳遞傳遞關系關系.實例：實例：A上的全域關系上的全域關系 EA, 恒等關系恒等關系 IA 和空關系和空關系 , 小小于等于關系于等于關系, 小于關系小于關系, 整除關系整除關系, 包含關系包含關系, 真包含關系真包含關系R1 和和 R3 是是A上的傳遞關系上的傳遞關系, R2不是不是A上的傳遞關系上的傳遞關系.41關系性質的充要條件設設 R 為為 A 上的關系上的關系, 則則 (1) R 在在 A 上自反當且僅當上自反當且僅當 IA R (2) R 在在 A 上反自反當且僅當上反自反當且僅當 RIA= (3) R 在在 A 上對稱當且僅當上對稱當且僅當 R=R 1 (4)

26、R 在在 A 上反對稱當且僅當上反對稱當且僅當 RR 1 IA (5) R 在在 A 上傳遞當且僅當上傳遞當且僅當 R R R 42自反性證明證明模式證明模式 證明證明 R 在在 A 上自反上自反 任取任取 x, x A . . R 前提前提 推理過程推理過程 結論結論例例4 證明若證明若 IA R ，則則 R 在在 A 上自反上自反. 證證 任取任取x, x A IA R 因此因此 R 在在 A 上是自反的上是自反的.43對稱性證明證明模式證明模式 證明證明 R 在在 A 上對稱上對稱 任取任取 R . . R 前提前提 推理過程推理過程 結論結論例例5 證明若證明若 R=R 1 , 則則

27、R 在在A上對稱上對稱. 證證 任取任取 R R 1 R 因此因此 R 在在 A 上是對稱的上是對稱的.44反對稱性證明證明模式證明模式 證明證明 R 在在 A 上反對稱上反對稱 任取任取 R R . x=y 前提前提 推理過程推理過程 結論結論例例6 證明若證明若 RR 1 IA , 則則 R 在在 A 上反對稱上反對稱. 證證 任取任取 R R R R 1 RR 1 IA x=y 因此因此 R 在在 A 上是反對稱的上是反對稱的.45傳遞性證明證明模式證明模式 證明證明 R 在在 A上傳遞上傳遞 任取任取， R R . R 前提前提 推理過程推理過程 結論結論例例7 證明若證明若 R R

28、R , 則則 R 在在 A 上傳遞上傳遞. 證證 任取任取， R R R R R 因此因此 R 在在 A 上是傳遞的上是傳遞的.46關系性質判別自反性自反性反自反性反自反性對稱性對稱性反對稱性反對稱性傳遞性傳遞性表達式表達式IA RRIA=R=R 1 RR 1 IA R R R關系關系矩陣矩陣主對角主對角線元素線元素全是全是1主對角線主對角線元素全是元素全是0矩陣是對稱矩陣是對稱矩陣矩陣若若rij1, 且且ij, 則則rji0對對M2中中1所所在位置在位置,M中相應位置中相應位置都是都是1關系圖關系圖每個頂每個頂點都有點都有環(huán)環(huán)每個頂點每個頂點都沒有環(huán)都沒有環(huán)如果兩個頂如果兩個頂點之間有邊點之

29、間有邊, 一定是一對一定是一對方向相反的方向相反的邊邊(無單邊無單邊)如果兩點之如果兩點之間有邊間有邊, 一一定定是一條有向是一條有向邊邊(無雙向邊無雙向邊)如果頂點如果頂點xi到到xj有邊有邊, xj到到xk有邊有邊,則則從從xi到到xk也也有邊有邊 47實例例例8 判斷下圖中關系的性質判斷下圖中關系的性質, 并說明理由并說明理由(3) 自反，不是反自反；反對稱，不是對稱；不傳遞自反，不是反自反；反對稱，不是對稱；不傳遞. (1)(2)(3)(1) 不是自反也不是反自反；對稱不是自反也不是反自反；對稱, 不是反對稱；不傳遞不是反對稱；不傳遞.(2) 反自反反自反, 不是自反；反對稱不是自反；

30、反對稱, 不是對稱；傳遞不是對稱；傳遞.48運算與性質的關系自反性自反性反自反性反自反性對稱性對稱性反對稱性反對稱性傳遞性傳遞性R1 1 R1R2 R1R2 R1 R2 R1 R2 49閉包定義定義定義4.17 設設R是非空集合是非空集合A上的關系上的關系, R 的的自反自反 (對稱對稱或或傳遞傳遞) 閉包閉包 是是A上的關系上的關系R , 使得使得 R 滿足以下條件：滿足以下條件： (1) R 是自反的（對稱的或傳遞的）是自反的（對稱的或傳遞的） (2) R R (3) 對對A上任何包含上任何包含R 的自反（對稱或傳遞）關系的自反（對稱或傳遞）關系R 有有 R R . 一般將一般將 R 的自

31、反閉包記作的自反閉包記作 r(R), 對稱閉包記作對稱閉包記作 s(R), 傳遞傳遞閉包記作閉包記作 t(R). 50閉包的構造方法集合表示集合表示定理定理4.7 設設R為為A上的關系上的關系, 則有則有 (1) r(R)=RR0 (2) s(R)=RR 1 (3) t(R)=RR2R3說明：說明：對于有窮集合對于有窮集合A (|A|=n) 上的關系上的關系, (3)中的并最多不超過中的并最多不超過Rn. 若若R 是自反的，則是自反的，則 r(R)=R; 若若 R 是對稱的，則是對稱的，則 s(R)=R;若若R 是傳遞的，則是傳遞的，則 t(R)=R. 51定理4.7的證明只證只證 (1) 和

32、和 (3) 證證 r(R)=RR0 只需證明只需證明RR0 滿足閉包定義滿足閉包定義. RR0包含了包含了R 由由IA RR0可知可知 RR0 在在 A上是自反的上是自反的. 下面證明下面證明RR0是包含是包含R 的最小的自反關系的最小的自反關系. 假設假設R 是包含是包含R 的自反關系，那么的自反關系，那么IA R , R R ，因此有因此有 RR0=IA R R 52任取任取和和 RR2R3. RR2R3. RR2R3.于是，由于是，由RR2R3.的傳遞性得的傳遞性得 t(R) RR2R3 對對n 進行歸納證明進行歸納證明 Rn t(R).n=1時顯然為真時顯然為真. 假設假設n=k時為真

33、，那么對于任意時為真，那么對于任意 Rk+1 Rk R t ( Rk R) t ( t(R) t(R) t(R) （t(R)傳遞）傳遞） 于是，于是， RR2R3 t(R) 定理4.7的證明（續(xù)）53矩陣表示矩陣表示設關系設關系R, r(R), s(R), t(R)的關系矩陣分別為的關系矩陣分別為M, Mr, Ms 和和 Mt , 則則 Mr =M + E Ms =M + M Mt =M + M2 + M3 + 其中其中E 是和是和 M 同階的單位矩陣同階的單位矩陣, M 是是 M 的轉置矩陣的轉置矩陣. 注意：在上述等式中矩陣的元素相加時使用邏輯加注意：在上述等式中矩陣的元素相加時使用邏輯加

34、. 閉包的構造方法（續(xù)）54圖表示圖表示設關系設關系R, r(R), s(R), t(R)的關系圖分別記為的關系圖分別記為G, Gr, Gs, Gt , 則則Gr, Gs, Gt 的頂點集與的頂點集與G 的頂點集相等的頂點集相等. 除了除了G 的邊以的邊以外外, 以下述方法添加新的邊：以下述方法添加新的邊： 考察考察G 的每個頂點的每個頂點, 如果沒有環(huán)就加上一個環(huán)如果沒有環(huán)就加上一個環(huán). 最終得到最終得到的是的是Gr. 考察考察G 的每一條邊的每一條邊, 如果有一條如果有一條 xi 到到 xj 的單向邊的單向邊, ij, 則則在在G中加一條中加一條 xj 到到 xi 的反方向邊的反方向邊.

35、最終得到最終得到Gs. 考察考察G 的每個頂點的每個頂點 xi, 找從找從 xi 出發(fā)的每一條路徑，如果出發(fā)的每一條路徑，如果從從 xi 到路徑中的任何結點到路徑中的任何結點 xj 沒有邊，就加上這條邊沒有邊，就加上這條邊. 當當檢查完所有的頂點后就得到圖檢查完所有的頂點后就得到圖Gt . 閉包的構造方法（續(xù)）55實例例例1 設設A=a,b,c,d, R=,R和和 r(R), s(R), t(R)的關系圖如下圖所示的關系圖如下圖所示. Rr(R)s(R)t(R)56傳遞閉包的計算Warshall算法算法思路：算法思路：考慮考慮 n+1個矩陣的序列個矩陣的序列M0, M1, , Mn , 將矩陣

36、將矩陣 Mk 的的 i 行行 j 列列的元素記作的元素記作Mki,j. 對于對于k=0,1,n, Mki,j=1當且僅當在當且僅當在R 的關系圖中存在一條從的關系圖中存在一條從 xi 到到 xj 的路徑，并且這條路徑的路徑，并且這條路徑除端點外中間只經過除端點外中間只經過x1, x2, , xk中的頂點中的頂點. 不難證明不難證明M0就是就是R 的關系矩陣，而的關系矩陣，而 Mn 就對應了就對應了R 的傳遞閉包的傳遞閉包. Warshall算法算法：從從M0開始，順序計算開始，順序計算 M1, M2, , 直到直到 Mn 為止為止. 57Warshall算法的依據從從 Mk i, j 計算計算

37、 Mk+1i, j: i, j V. 頂點集頂點集 V1=1,2, , k, V2=k+2, ,n,V=V1 k+1 V2，Mk+1i,j=1 存在從存在從i 到到 j 中間只經過中間只經過V1 k+1中點的路徑中點的路徑這些路徑分為兩類：這些路徑分為兩類：第第1類：只經過類：只經過 V1中點中點第第2類：經過類：經過 k+1點點存在第存在第1類路徑：類路徑：Mki,j=1存在第存在第2類路徑：類路徑： Mki,k+1=1 Mkk+1,j=158Warshall算法及其效率算法算法4.1 Warshall算法算法 輸入：輸入：M （R 的關系矩陣）的關系矩陣）輸出：輸出：Mt （t(R)的關系

38、矩陣）的關系矩陣） 1. MtM2. for k1 to n do3. for i1 to n do4. for j1 to n do5. Mti, j Mti, j + Mti, k Mtk, j 時間復雜度時間復雜度 T(n)=O(n3)594.4 等價關系與偏序關系n4.4.1 等價關系等價關系n4.4.2 等價類和商集等價類和商集n4.4.3 集合的劃分集合的劃分n4.4.4 偏序關系偏序關系n4.4.5 偏序集與哈斯圖偏序集與哈斯圖60等價關系的定義與實例定義定義4.18 設設R為非空集合上的關系為非空集合上的關系. 如果如果R是自反的、對稱的是自反的、對稱的和傳遞的和傳遞的, 則稱

39、則稱R為為A上的上的等價關系等價關系. 設設 R 是一個等價關系是一個等價關系, 若若R, 稱稱 x等價于等價于y, 記做記做xy. 例例1 設設 A=1, 2, , 8, 如下定義如下定義 A上的關系上的關系R： R=| x,yA xy (mod 3)其中其中 xy (mod 3) 叫做叫做 x與與y 模模3相等相等, 即即 x 除以除以3的余數(shù)與的余數(shù)與 y 除以除以3的余數(shù)相等的余數(shù)相等. 不難驗證不難驗證R為為A上的等價關系上的等價關系, 因為因為 xA, 有有xx(mod 3) x,yA, 若若xy(mod 3), 則有則有yx(mod 3) x,y,zA, 若若xy(mod 3),

40、 yz(mod 3), 則有則有 xz(mod 3)61模3等價關系的關系圖設設 A=1, 2, , 8, R= | x,yA xy (mod 3) R 的關系圖如下：的關系圖如下：62等價類定義定義4.19 設設R為非空集合為非空集合A上的等價關系上的等價關系, xA，令，令 xR = y | yA xRy 稱稱 xR 為為x關于關于R 的的等價類等價類, 簡稱為簡稱為 x 的等價類的等價類, 簡記為簡記為x. 實例實例 A= 1, 2, , 8 上模上模 3 等價關系的等價類：等價關系的等價類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,663等價類的性質AxAx 定理定

41、理4.8 設設R是非空集合是非空集合A上的等價關系上的等價關系, 則則 (1) xA, x 是是A的非空子集的非空子集. (2) x, yA, 如果如果 xRy, 則則 x=y. (3) x, yA, 如果如果 x y, 則則 x與與y不交不交. (4) ，即所有等價類的并集就是即所有等價類的并集就是A. 64性質的證明(1)由等價類定義可知由等價類定義可知, xA有有x A. 由自反性有由自反性有xRx，因此因此xx, 即即x非空非空. (2)任取任取z, 則有則有zx R RR R R R 從而證明了從而證明了zy. 綜上所述必有綜上所述必有x y. 同理可證同理可證y x. 這就得到了這

42、就得到了x=y.(3) 假設假設xy, 則存在則存在zxy, 從而有從而有 zx zy, 即即R R 成立成立. 根據根據R 的對稱性和傳遞性必有的對稱性和傳遞性必有R, 與與x y矛盾矛盾65性質的證明（續(xù)）(4) 先證先證 . 任取任取y, y x (xA yx) yx x A yA 從而有從而有 .再證再證A . 任取任取y, yA yy yA y從而有從而有A 成立成立. 綜上所述得綜上所述得AxAx Axx AxAxAxAx Axx Axx Axx 66商集定義定義4.20 設設R 為非空集合為非空集合A 上的等價關系上的等價關系, 以以R 的所有的所有等等價類作為元素的集合稱為價類

43、作為元素的集合稱為A關于關于R 的的商集商集, 記做記做 A/R, A/R = xR | xA 例例2令令A=1, 2, , 8，A關于模關于模 3 等價關系等價關系R 的商集為的商集為 A/R = 1, 4,7, 2, 5, 8, 3, 6 A關于恒等關系和全域關系的商集為：關于恒等關系和全域關系的商集為： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 67集合的劃分定義定義4.21 設設A為非空集合為非空集合, 若若A的子集族的子集族 ( P(A) 滿滿足下面條件：足下面條件： (1) (2) x y (x,y xyxy=) (3) =A 則稱則稱 是是A的一個的一個劃分劃

44、分, 稱稱 中的元素為中的元素為A的的劃分塊劃分塊.例例3 設設Aa, b, c, d, 給定給定 1, 2, 3, 4, 5, 6如下：如下： 1=a, b, c,d， 2=a, b,c,d 3=a,a, b, c, d， 4=a, b,c 5=,a, b,c, d， 6=a,a,b, c, d 則則 1和和 2是是A的劃分的劃分, 其他都不是其他都不是A的劃分的劃分. 68等價關系與劃分的一一對應商集商集 A/R 就是就是A 的一個劃分的一個劃分 不同的商集對應于不同的劃分不同的商集對應于不同的劃分 任給任給A 的一個劃分的一個劃分 , 如下定義如下定義A 上的關系上的關系 R：R = |

45、 x, yA x 與與 y 在在 的同一劃分塊中的同一劃分塊中 則則R 為為A上的等價關系上的等價關系, 且該等價關系確定的商集就是且該等價關系確定的商集就是 . 例例4 給出給出A1,2,3上所有的等價關系上所有的等價關系求解思路：先做出求解思路：先做出A的所有劃分的所有劃分, 然后根據劃分寫出然后根據劃分寫出 對應的等價關系對應的等價關系. 69例 4 1, 2和和 3分別對應于等價關系分別對應于等價關系 R1, R2和和R3. 其中其中 R1=,IA R2=,IA R3=,IAA上的等價關系與劃上的等價關系與劃分之間的對應：分之間的對應： 4對應于全域關系對應于全域關系EA 5對應于恒等

46、關系對應于恒等關系IA70實例根據有序對根據有序對的的 x+y=2,3,4,5,6,7,8 將將A A劃分劃分. (A A)/R=, , , , , , , , , , , , , , 例例5 設設A=1,2,3,4，在，在A A上定義二元關系上定義二元關系 R： , R x+y = u+v，求求R 導出的劃分導出的劃分. 解解 A A=, , , , , , , , , , , , , , 71偏序關系定義定義4.22 非空集合非空集合A上的自反、反對稱和傳遞的關系，上的自反、反對稱和傳遞的關系，稱為稱為A上的上的偏序關系偏序關系，記作，記作 . 設設 為偏序關系為偏序關系, 如果如果 ,

47、則記作則記作 x y, 讀作讀作 x“小于或等于小于或等于”y. 實例實例 集合集合A上的恒等關系上的恒等關系 IA 是是A上的偏序關系上的偏序關系. 小于或等于關系小于或等于關系, 整除關系和包含關系也是相應集合整除關系和包含關系也是相應集合上的偏序關系上的偏序關系. 72相關概念定義定義4.23 x與與y可比可比 設設R為非空集合為非空集合A上的偏序關系上的偏序關系, x, y A, x與與y 可比可比 x y y x.結論：結論： x, y A，下述幾種情況發(fā)生其一且僅發(fā)生其一，下述幾種情況發(fā)生其一且僅發(fā)生其一. x y, y x, xy, x與與y不可比不可比定義定義4.24 擬序擬序

48、 R為非空集合為非空集合A上的關系上的關系,如果如果R是反自反和傳遞的，是反自反和傳遞的，則稱則稱R是是A上的擬序關系，簡稱為擬序，記作上的擬序關系，簡稱為擬序，記作 . 定義定義4.25 全序全序 R為非空集合為非空集合A上的偏序上的偏序, x, y A, x與與y 都可比，都可比，則稱則稱R為全序為全序. 定義定義4.26 覆蓋覆蓋 x,yA, 如果如果x y且不存在且不存在 z A使得使得 x z y, 則則稱稱 y覆蓋覆蓋x.實例：數(shù)集上的小于或等于關系是全序關系實例：數(shù)集上的小于或等于關系是全序關系 整除關系不是正整數(shù)集合上的全序關系整除關系不是正整數(shù)集合上的全序關系 1, 2, 4

49、, 6集合上的整除關系集合上的整除關系, 2覆蓋覆蓋1, 4 和和 6 覆蓋覆蓋2. 但但4不覆蓋不覆蓋1.73偏序集與哈斯圖定義定義4.27 集合集合A和和A上的偏序關系上的偏序關系 一起叫做一起叫做偏序集偏序集, 記記作作.實例：整數(shù)集和數(shù)的小于等于關系構成偏序集實例：整數(shù)集和數(shù)的小于等于關系構成偏序集 冪集冪集P(A)和包含關系構成偏序集和包含關系構成偏序集. 哈斯圖哈斯圖：利用偏序自反、反對稱、傳遞性簡化的關系圖：利用偏序自反、反對稱、傳遞性簡化的關系圖特點：特點： 每個結點沒有環(huán)每個結點沒有環(huán) 兩個連通的結點之間的序關系通過結點位置的高低兩個連通的結點之間的序關系通過結點位置的高低

50、表示，位置低的元素的順序在前表示，位置低的元素的順序在前 具有覆蓋關系的兩個結點之間連邊具有覆蓋關系的兩個結點之間連邊74哈斯圖實例例例6 75 例例7 已知偏序集已知偏序集的哈斯圖如下圖所示的哈斯圖如下圖所示, 試求出集合試求出集合A和關系和關系R的表達式的表達式. 哈斯圖實例（續(xù)）A=a, b, c, d, e, f, g, h R=, IA 76偏序集的特定元素定義定義4.28 設設為偏序集為偏序集, B A, yB. (1) 若若 x(xBy x)成立成立, 則稱則稱 y 為為 B 的的最小元最小元. (2) 若若 x(xBx y)成立成立, 則稱則稱 y 為為 B 的的最大元最大元. (3) 若若 x(xBx yx=y)成立成立, 則稱則稱 y 為為B的的極小元極小元. (4) 若若 x(xBy xx=y)成立成立, 則稱則稱 y 為為B的的極大元極大元. 性質：性質：對于有窮集，極小元和極大元必存在，可