閉包,閉包

一、閉包的定義：

閉包是關係的一種特殊運算，運算結果依然是關係。

閉包是包含原關係具有某種性質的最小的關係。閉包有三種，自反閉包、對稱閉包、傳遞閉包。R的自反閉包記作r(R), 對稱閉包記作s(R), 傳遞閉包記作t(R)。

二、閉包的求法：

1.集合表示法中閉包的求法：

設R為A上的關係, 則有

2.矩陣表示法中閉包的求法：

設關係R, r(R), s(R), t(R)的關係矩陣分別為M, Mr , Ms 和 Mt ，則有

                          (1) Mr=M+E   

                          (2) Ms=M+M '      

                          (3) Mt=M+M2+M3+…

E 是單位矩陣, M '是 轉置矩陣，相加時使用邏輯加。

3.關係圖表示法中閉包的求法：

設關係R, r(R), s(R), t(R)的關係圖分別記為G, Gr, Gs, Gt, 則Gr , Gs , Gt 的頂點集與G 的頂點集相等. 除了G 的邊以外, 以下述方法添加新的邊：

(1) 考察G 的每個頂點, 若沒自迴路就加一個自迴路，得到Gr  

(2) 考察G 的每條邊, 若有一條 xi 到 xj 的單向邊, i≠j, 則在G中加一條 xj 到 xi 的反向邊,  得到Gs

(3) 考察G 的每個頂點 xi, 找 xi 可達的所有頂點 xj (允許i=j )， 如果沒有從 xi  到 xj  的邊, 就加上這條邊, 得到圖Gt

例：設A={a,b,c,d}, R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}, 求r(R), s(R), t(R)。

解：r(R)={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<a,a>,<b,b>,<c,c>,<d,d>}

s(R)={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<c,b>,<d,c>,<b,d>}

 t(R)={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<a,a>,<b,b>,<a,c>,<b,d>,<c,b>,<c,a>,<d,c>,<c,c>,<d,d>,<a,d>,<d,a>}

如果在關係圖中解，R和r(R), s(R), t(R)的關係圖如下圖所示。