孫翠先，張 健，吳煥春

(唐山學(xué)院 基礎(chǔ)教學(xué)部，河北 唐山 063000)

0 引言

集合A上的二元關(guān)系R的傳遞性描述了序偶之間的內(nèi)在聯(lián)系。當(dāng)A的元數(shù)|A|比較小(|A|≤4)時(shí)，可通過(guò)序偶法、關(guān)系矩陣法或關(guān)系圖法判定，計(jì)算量不大，人工判定可以完成。但當(dāng)|A|較大時(shí)，不論上述三種方法哪一種，人工計(jì)算量都非常巨大，基本上不可能完成。而求關(guān)系R的傳遞閉包t(R)時(shí)，當(dāng)R不具有傳遞性，就需要通過(guò)不斷添加新序偶使之具備傳遞性為止。因此當(dāng)|A|較大時(shí)，求t(R)變得非常困難。此時(shí)Warshall提出了一種算法[1]。本文在Warshall算法基礎(chǔ)上，利用關(guān)系矩陣，借助數(shù)學(xué)軟件Matlab，給出求t(R)的優(yōu)化算法。此法實(shí)現(xiàn)了傳遞閉包的Matlab計(jì)算，最大優(yōu)點(diǎn)是對(duì)|A|無(wú)限制，程序簡(jiǎn)便易操作，最重要的一點(diǎn)是給出了新添加的序偶矩陣。

1 算法

1.1 符號(hào)引入

給定集合A上的一個(gè)二元關(guān)系R，設(shè)MR為R的關(guān)系矩陣，MR=(rij)，這里rij只取0或1，它是一個(gè)布爾矩陣。設(shè)集合A={a1，a2，…，an}，t(R)的關(guān)系矩陣為Mt(R)。

1.2 傳遞閉包的矩陣性質(zhì)

1.3 Matlab程序

Mt=R；

a=size(R)；

for k=1∶a

for i=1∶a

for j=1∶a

Mt(i，j)=max(min(Mt(i，k)，Mt(k，j))，Mt(i，j))；

end

end

end

Mt

Mt-R=NR

還原得t(R)。

2 實(shí)例模擬求傳遞閉包

給定A={a，b，c，d，e，f，g，h}，|A|=8，R={，，，，，，，}。

在Matlab R2007b下運(yùn)行：

>>Mt=MR；

>>a=size(MR)；

>>for k=1∶a

for i=1∶a

for j=1∶a

Mt(i，j)=max(min(Mt(i，k)，Mt(k，j))，Mt(i，j))；

end

end

end

>>Mt

Mt=

>>Mt-MR

ans=

ans即為新添加的序偶矩陣。新添加的序偶集合為

NR={，，，，，}，結(jié)果t(R)=R∪NR。

3 結(jié)語(yǔ)

實(shí)例中全域關(guān)系|EA|=64，而|R|=8，|R|占|EA|的百分比只有12.5%，此時(shí)可以人工手算。但當(dāng)|R|占|EA|的百分比只有30%以上時(shí)，人工求t(R)幾乎不可能實(shí)現(xiàn)，而此時(shí)突顯本文給出的方法的優(yōu)越性。