離散數(shù)學(xué)關(guān)系的閉包PPT課件

1、1離散數(shù)學(xué)離散數(shù)學(xué)集合論集合論 2 / 68主要內(nèi)容主要內(nèi)容n集合代數(shù)n二元關(guān)系n函數(shù)集合的基本概念集合的運算有窮集合的計數(shù)集合恒等式有序?qū)εc笛卡兒積二元關(guān)系關(guān)系的運算關(guān)系的性質(zhì) 關(guān)系的閉包等價關(guān)系與劃分偏序關(guān)系函數(shù)的定義與性質(zhì)函數(shù)的復(fù)合與反函數(shù)雙射函數(shù)與集合的基數(shù) 3 / 687.5 關(guān)系的閉包關(guān)系的閉包一一. . 閉包的定義閉包的定義定義定義7.147.14 設(shè)設(shè)r r是非空集合是非空集合a a上的關(guān)系上的關(guān)系,r,r的自反閉包的自反閉包( (對稱閉包對稱閉包, ,傳遞閉包傳遞閉包) )是是 a a上的關(guān)系上的關(guān)系 r r , ,它滿足它滿足: :(1) r(1) r 是自反的是自反的 (

2、 (對稱的對稱的, ,傳遞的傳遞的) )；(2) r(2) r r r ; ;(3) (3) 對對a a上任何包含上任何包含 r r 的自反關(guān)系的自反關(guān)系 ( (對稱關(guān)系對稱關(guān)系, ,傳遞關(guān)系傳遞關(guān)系) ) r r 都有都有r r r r . .注注:r:r的自反閉包記為的自反閉包記為 r(r),r(r),對稱閉包記為對稱閉包記為 s(r),s(r),傳遞閉包記傳遞閉包記 為為 t(r).t(r). reflexive, symmetric, transtive: r(r), s(r), t(r). 4 / 68閉包的計算閉包的計算定理定理 7.107.10 設(shè)設(shè)r r是是a a上的關(guān)系上的關(guān)

3、系, ,則則(1) r(r)=rr(1) r(r)=rr0 0; ;(2) s(r)= rr(2) s(r)= rr-1-1; ;(3) t(r)= rr(3) t(r)= rr2 2rr3 3. .證明證明：(1) (1) 由由i ia a= r= r0 0 r rrr0 0 知知, , rr rr0 0 是自反的是自反的, ,且且r r r rrr0 0. .設(shè)設(shè)r r是是a a上包含上包含r r的自反關(guān)系的自反關(guān)系, ,則則 r r r r , i , ia a r r, 因而因而 r rrr0 0 r riia a r rr r = = r r 即即 rrrr0 0 r r . .可見

4、可見rrrr0 0滿足自反閉包的定義滿足自反閉包的定義, ,從而從而 r(r)= rrr(r)= rr0 0. . (2) (2) 略略. . 5 / 68閉包的計算閉包的計算(3)(3)先證先證rrrr2 2 t(r),t(r),為此只需證明對任意正整數(shù)為此只需證明對任意正整數(shù)n n都有都有 r rn n t(r). t(r). 用歸納法用歸納法. .當(dāng)當(dāng)n=1n=1時時, r, r1 1 = r = r t(r).t(r).假設(shè)假設(shè) r rn n t(r), t(r), 下證下證 r rn+1n+1 t(r)t(r)事實上事實上, ,由于由于 r rn+1 n+1 = r= rn n r

5、r t(t( r rn n r)r) t(t( t(r)t(r) t(r)t(r) t(r)t(r)從而從而 r rn+1 n+1 t(r) . t(r) . 由歸納法完成證明由歸納法完成證明. 6 / 68閉包的計算閉包的計算下證下證 rrrr2 2 是傳遞的是傳遞的. . 事實上事實上, ,對任意對任意 ,( ( rr rr2 2)( )( rr rr2 2) ) t (t ( r rt t) ) s(s( r rs s) ) t t s( s( r rt t r rs s) ) t t s( s( r rt+st+s) ) rrrr2 2從而從而 rrrr2 2 是傳遞的是傳遞的. .

6、因因t(r)t(r)是傳遞閉包是傳遞閉包, , 故故t(rt(r) ) rr rr2 2. .由以上兩方面知由以上兩方面知, , t(r) t(r) rrrr2 2 . . 7 / 68通過關(guān)系矩陣求閉包 證證: :由定理由定理7.67.6和定理和定理7.107.10立即得證立即得證. .通過關(guān)系矩陣求閉包通過關(guān)系矩陣求閉包設(shè)關(guān)系設(shè)關(guān)系r, r(r), s(r), t(r)r, r(r), s(r), t(r)的關(guān)系矩陣分別為的關(guān)系矩陣分別為m, mm, mr r, m, ms s, m, mt t, , 則則: : m mr r = m+e, = m+e, m ms s = m+m= m+m

7、, , m mt t = m+m= m+m2 2+m+m3 3+ +, , 其中其中e e是與是與m m同階的單位矩陣同階的單位矩陣.m.m是是m m的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣, ,矩陣元素相矩陣元素相加時使用加時使用邏輯加邏輯加. .推論推論 設(shè)設(shè)r r是有限集合是有限集合a a上的關(guān)系，則存在正整數(shù)上的關(guān)系，則存在正整數(shù)r r使得使得 t(r)= rrt(r)= rr2 2rrr r. .r(r) = riar(r) r ia mxy = 1 exy = 1 nnnnnnnnnnnnnnncccccccccbbbbbbbbbaaaaaaaaa221222211121122122221112112

8、212222111211njibacijijij ,1, 8 / 68通過關(guān)系圖求閉包通過關(guān)系圖求閉包 設(shè)關(guān)系設(shè)關(guān)系r, r(r), s(r), t(r)r, r(r), s(r), t(r)的關(guān)系圖分別記為的關(guān)系圖分別記為g, gg, gr r, g, gs s, g, gt t, , 則則g gr r, g, gs s, g, gt t的頂點集與的頂點集與g g的頂點集相同的頂點集相同. .除了除了g g的邊外的邊外, ,依下述方法添依下述方法添加新邊加新邊: :(1)(1)對對g g的每個頂點的每個頂點, ,如果無環(huán)如果無環(huán), ,則添加一條環(huán)則添加一條環(huán), ,由此得到由此得到g gr r

9、; ;(2)(2)對對g g的每條邊的每條邊, ,如果它是單向邊如果它是單向邊, ,則添加一條反方向的邊則添加一條反方向的邊. .由此得由此得到到g gs s; ;), 2 , 1(klxlj(3) 對對g g的每個頂點的每個頂點x xi i , ,找出從找出從x xi i 出發(fā)的所有出發(fā)的所有2 2步步, 3, 3步步, , , , n n步長步長的有向路的有向路 ( (n n為為g g的頂點數(shù)的頂點數(shù)).).設(shè)路的終點分別設(shè)路的終點分別為為 , ,如果從如果從 x xi i 到到 x xj j 無邊無邊, ,則添上這則添上這條邊條邊. .如上處理完所有頂點后得到如上處理完所有頂點后得到 g

10、 gt tkjjjxxx,21 9 / 68warshall算法算法n設(shè)設(shè)a=xa=x1 1,x,x2 2,x,xn n,r,r為為a a上的二元關(guān)系上的二元關(guān)系,r,r的關(guān)系矩陣為的關(guān)系矩陣為m:m:1. 1. m mt t = m+m = m+m2 2+m+mn n2. warshall2. warshall算法算法考慮矩陣序列考慮矩陣序列 m m0 0,m,m1 1,m,mn n= = m mt t : k=0,1,n : k=0,1,nm mk ki,j=1i,j=1 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 在在g gr r中存在一條從中存在一條從x xi i到到x xj j的路徑的路徑并且除端點外中間只經(jīng)

11、過并且除端點外中間只經(jīng)過 x x1 1,x,x2 2,x,xk k 中的頂點中的頂點. .m mk+1k+1i,j=1i,j=1 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 在在g gr r中存在一條從中存在一條從x xi i到到x xj j的路的路徑并且除端點外中間只經(jīng)過徑并且除端點外中間只經(jīng)過 x x1 1,x,x2 2,x,xk k, ,x xk+1k+1 中的頂中的頂點點m mk ki,j=1 i,j=1 或者或者m mk ki,i,k+1k+1=1 m=1 mk k k+1k+1,j=1,j=1 10 / 68warshall算法示例算法示例n設(shè)設(shè) a=a,b,c,d, r=,求求 t( r ).解解0000

12、100001010010m00000100001110010m10000100001110111m20000100011111111m30000100011111111mt(r)4mk+1i,j=1 mki,k+1=1 mkk+1,j=1 11 / 68閉包的性質(zhì)閉包的性質(zhì) 定理定理7.117.11 設(shè)設(shè)r r是非空集合是非空集合a a上的關(guān)系上的關(guān)系, ,則則(1) r (1) r 是自反的當(dāng)且僅當(dāng)是自反的當(dāng)且僅當(dāng)r(r)=rr(r)=r(2) r (2) r 是對稱的當(dāng)且僅當(dāng)是對稱的當(dāng)且僅當(dāng) s(r)=rs(r)=r(3) r (3) r 是傳遞的當(dāng)且僅當(dāng)是傳遞的當(dāng)且僅當(dāng) t(r)=rt(

13、r)=r 證證:(1) :(1) 充分性顯然充分性顯然. .下證必要性下證必要性. . 因因 r r 是包含了是包含了 r r 的自反關(guān)系的自反關(guān)系, ,故故r(r)r(r) r.r. 另一方面另一方面, ,顯然顯然 r r r(r). r(r). 從而從而,r(r)=r.,r(r)=r. (2), (3) (2), (3)略略. .定理定理7.127.12 設(shè)設(shè) r r1 1 和和 r r2 2 是非空集合是非空集合a a上的關(guān)系上的關(guān)系, ,且且 r r1 1 r r2 2 , , 則則(1)r(r(1)r(r1 1) ) r(rr(r2 2); (2)s(r); (2)s(r1 1) )

14、 s(r s(r2 2); (3)t(r); (3)t(r1 1) ) t(r t(r2 2) ) 證明略證明略 12 / 68閉包的性質(zhì)閉包的性質(zhì)定理定理7.137.13 設(shè)設(shè) r r 是非空集合是非空集合a a上的關(guān)系上的關(guān)系（1 1）若）若r r是自反的是自反的, ,則則 s(r) s(r) 和和 t(r) t(r) 也是自反的也是自反的. .（2 2）若）若r r是對稱的是對稱的, ,則則 r(r) r(r) 和和 t(r) t(r) 也是自反的也是自反的. .（3 3）若）若r r是傳遞的是傳遞的, ,則則 r(r) r(r) 也是傳遞的也是傳遞的. .證明證明: :只證只證 (2)

15、 .(2) .先考慮先考慮r(r). r(r). 因因r r是是 a a上的對稱關(guān)系。故上的對稱關(guān)系。故r=rr=r-1-1 , , 同時同時 i ia a = i= ia a-1 -1 , ,于是于是 (ri(ria a) )-1-1=r=r-1-1iia a-1 -1 ( (根據(jù)習(xí)題根據(jù)習(xí)題7.20). 7.20). 從而從而 r(r)r(r)-1 -1 = (rr= (rr0 0) )-1 -1 = (ri= (ria a) )-1 -1 = r= r-1-1iia a-1 -1 = ri= ria a = r(r) .= r(r) .這便說明這便說明 r(r) r(r) 是對稱的是對稱

16、的. . 下面證明下面證明t(r)t(r)的對稱性的對稱性. .為此為此, ,先用數(shù)學(xué)歸納法證明先用數(shù)學(xué)歸納法證明: :若若r r是對稱的是對稱的, , 則對任何正整數(shù)則對任何正整數(shù)n, rn, rn n也是對稱的也是對稱的. . 事實上事實上, ,當(dāng)當(dāng)n=1n=1時時,r=r ,r=r 顯然是對稱的顯然是對稱的. . 13 / 68閉包的性質(zhì)閉包的性質(zhì)假設(shè)假設(shè)r rn n是對稱的是對稱的, ,下證下證r rn+1n+1 的對稱性的對稱性. .由于由于 r rn+1 n+1 r rn n r r t (t ( r rn n) r)r) t (t ( r rn n) r)r) r r r rn

17、n r rn+1n+1 故故 r rn+1 n+1 是對稱的是對稱的. .歸納法定成歸納法定成. .現(xiàn)在來證現(xiàn)在來證 t(r)t(r)的對稱性的對稱性. .由于由于 t(r) t(r) n(n( r rn n) ) n(n( r rn n) ) t(r)t(r) 因此因此t(r)t(r)是對稱的是對稱的. . 注注: :由于對稱閉包運算不保持傳遞性由于對稱閉包運算不保持傳遞性, ,故在運算順序故在運算順序 上它應(yīng)放在傳遞閉包之前上它應(yīng)放在傳遞閉包之前, ,即即 t st s r(r)=t(s(r(r). r(r)=t(s(r(r). 14 / 68注注n二元關(guān)系的閉包仍然是二元關(guān)系二元關(guān)系的閉包仍然是二元關(guān)系,還可以求它的閉包還可以求它的閉包.n例如例如,r是是a上的二元關(guān)系上的二元關(guān)系, r(r)是它的自