基于關(guān)系矩陣的傳遞閉包求解方法＊

郭麗君

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

0 引言

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

1 基本定義和定理

定義1設(shè)R 是集合X 上的關(guān)系，若R ?R＇且R＇是傳遞的，若另有R ?R＇＇且R＇＇是傳遞的，則必有R＇ ?R＇＇，此時(shí)稱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（符號(hào)＂?＂表示關(guān)系R的復(fù)合運(yùn)算）。

定理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 的傳遞閉包對(duì)應(yīng)的關(guān)系矩陣為

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

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

⑴當(dāng)Xi≠Xj，且有(ai,aj),(aj,ai)?R 時(shí)，由于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 時(shí)，由 于(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í)，必存在正整數(shù)k＜n，使得Rk={(ai,ai)}，Rk+1=R，即A(k+1)=A。

因此t(R)對(duì)應(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，因此計(jì)算可以終止，由公式⑵可得

由此得到關(guān)系矩陣A＇對(duì)應(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)，因此計(jì)算可以終止，由公式⑵可得

由此得到關(guān)系矩陣A＇對(duì)應(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)：

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

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

具體給出算法如下：

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

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

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

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

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

4 結(jié)束語

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