郭麗君

(蘭州博文科技學(xué)院電信工程學(xué)院，甘肅 蘭州 730101)

0 引言

二元關(guān)系是離散數(shù)學(xué)集合論中的重要概念，在計算機學(xué)科的相關(guān)專業(yè)中應(yīng)用極為廣泛，如數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)、語法分析理論等，很多相關(guān)理論和研究判定方法都是建立在關(guān)系傳遞閉包運算的基礎(chǔ)上[2-6]，因此關(guān)系的傳遞閉包運算也成了很多學(xué)者爭相研究的對象[7-13]，已有理論雖然已經(jīng)得到了一些很好的結(jié)果，但方法仍略顯繁瑣和復(fù)雜，使得學(xué)生在理解的過程中存在困難。通過利用關(guān)系的關(guān)系矩陣，不用對關(guān)系中的有序偶做過多的判斷和對比，也不必對元素進行篩選和刪除，僅使用矩陣的簡單運算，給出了傳遞閉包運算較為簡單的方法，使得學(xué)生在學(xué)習(xí)的過程中易理解、易接受，且在此基礎(chǔ)上進一步通過計算機編程的方法求解較龐大的關(guān)系的傳遞閉包有了理論依據(jù)。

1 基本定義和定理

定義1設(shè)R 是集合X 上的關(guān)系，若R ?R＇且R＇是傳遞的，若另有R ?R＇＇且R＇＇是傳遞的，則必有R＇ ?R＇＇，此時稱R＇是R的傳遞閉包，記為t(R)=R。

定義2設(shè)定義在集合X={a1,a2,…,an}上的關(guān)系R，定義其關(guān)系矩陣為A=(aij)n，其中

定義3設(shè)R是集合X上的關(guān)系，定義Rn=R?R?…?R（符號＂?＂表示關(guān)系R的復(fù)合運算）。

定理1[1]設(shè)R是集合X上的關(guān)系，則R的傳遞閉包

定理2設(shè)R 是有限集合X 上的關(guān)系，且 ||X=n,則R的傳遞閉包t(R)=

2 主要結(jié)論

定理3設(shè)R 是集合X 上的關(guān)系，且 |X |=n，A為關(guān)系R的關(guān)系矩陣，必存在正整數(shù)k＜n，使得A(k)=O（零矩陣）或A(k+1)=A(i),i=1,2,…,k，則關(guān)系R 的傳遞閉包對應(yīng)的關(guān)系矩陣為

即A＇對應(yīng)的關(guān)系R＇=t(R)。

另一方面，令Xi={ai}，分以下三種情況討論。

⑴當(dāng)Xi≠Xj，且有(ai,aj),(aj,ai)?R 時，由于Rn=R?R?…?R，在關(guān)系的復(fù)合過程中，元素是遞減的狀態(tài)，必存在正整數(shù)k＜n，使得Rk=?，即A(k)=O（O為零矩陣）。

⑵ 當(dāng)Xi≠Xj，且 有(ai,aj),(aj,ai)∈R 時，由 于(ai,aj)?(aj,ai)=(ai,ai)，而(ai,ai)?(ai,aj)=(ai,aj)，因 此必存在正整數(shù)k＜n，使得A(k+1)=A(i),i=1,2,…,k。

⑶ 當(dāng)Xi=Xj時，必存在正整數(shù)k＜n，使得Rk={(ai,ai)}，Rk+1=R，即A(k+1)=A。

因此t(R)對應(yīng)的關(guān)系矩陣為

A＇=A(+)A(2)(+)…(+)A(k),k＜n

證明完畢。

例1設(shè)集合X={a,b,c,d}，定義集合X 上的關(guān)系R={(a,b),(a,c),(b,c),(b,d)}，通過關(guān)系矩陣求R 的傳遞閉包。

解：根據(jù)公式⑴先寫出關(guān)系R 的關(guān)系矩陣A，依次求出A(2),A(3)：

由于A(3)=O，因此計算可以終止，由公式⑵可得

由此得到關(guān)系矩陣A＇對應(yīng)的關(guān)系R＇={(a,b),(a,c),(a,d),(b,c),(b,d)}即為關(guān)系R的傳遞閉包。

例2設(shè)集合X={a,b,c,d}，定義集合X 上的關(guān)系R={(a,b),(c,b),(b,c),(c,d)}，通過關(guān)系矩陣求R 的傳遞閉包。

解：根據(jù)公式⑴先寫出關(guān)系R 的關(guān)系矩陣A，依次求出A(2),A(3)：

顯然A(4)=A(2)，因此計算可以終止，由公式⑵可得

由此得到關(guān)系矩陣A＇對應(yīng)的關(guān)系R'={(a,b),(a,c),(a,d),(b,b),(b,c),(b,d),(c,b),(c,c),(c,d)}即為關(guān)系R的傳遞閉包。

例3設(shè)集合X={a,b,c,d}，定義集合X 上的關(guān)系R={(a,b),(c,a),(b,c)}，通過關(guān)系矩陣求R的傳遞閉包.解：根據(jù)公式⑴先寫出關(guān)系R 的關(guān)系矩陣A，依次求出A(2),A(3)：

此時A(4)=A，因此計算終止，由公式⑵可得

矩陣A＇對應(yīng)的關(guān)系R'={(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)}即為關(guān)系R的傳遞閉包。

3 算法分析

通過寫出關(guān)系R 的關(guān)系矩陣，利用矩陣運算的方法得到關(guān)系R 的傳遞閉包所對應(yīng)的關(guān)系矩陣，進而寫出傳遞閉包的過程，這顯然比現(xiàn)有的傳遞閉包運算方法要簡單的多，更易操作。同時，利用計算機編程去解決更復(fù)雜的關(guān)系也得以實現(xiàn)。另一方面，在計算一個關(guān)系的傳遞閉包時，還要考慮關(guān)系自身的性質(zhì)，若關(guān)系R 自身具備傳遞性，則t(R)=R，利用該方法求關(guān)系的傳遞閉包時，不用驗證關(guān)系R 的性質(zhì)，對于滿足傳遞性的關(guān)系來說該方法仍然適用。

具體給出算法如下：

⑴寫出關(guān)系R 的關(guān)系矩陣A（A中僅有0,1 兩個元素）；

⑵ 使用布爾和與布爾乘的方法計算繼續(xù)計算A(k),k=2,3,…,n（A(k)中僅有0,1兩個元素）；

⑶當(dāng)A(k)=O或A(k+1)=A(i)，i=1,2,3,…,k時結(jié)束；

⑷計算A＇=A(+)A(2)(+)…(+)A(k)；

⑸輸出A＇即為關(guān)系t(R)的關(guān)系矩陣，計算結(jié)束。

4 結(jié)束語

通過使用關(guān)系矩陣求解關(guān)系的傳遞閉包，在主要結(jié)論定理3 的證明中分三種情況對關(guān)系進行了討論，通過三個對應(yīng)情況下的例題進行了佐證。與現(xiàn)有的方法相比，該方法在求解過程中不用對關(guān)系中的有序偶做過多的判斷和對比，也不必對元素進行篩選或刪除，求解方法簡單易懂，可對學(xué)習(xí)關(guān)系閉包運算的師生帶來一定啟發(fā)，同時為進一步利用計算機編程來求解關(guān)系的傳遞閉包提供了理論依據(jù)。