傳遞閉包的Matlab實現(xiàn)

孫翠先，張 健，吳煥春

(唐山學院 基礎教學部，河北 唐山 063000)

0 引言

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

1 算法

1.1 符號引入

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

1.2 傳遞閉包的矩陣性質

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 實例模擬求傳遞閉包

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

在Matlab R2007b下運行：

>>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={，，，，，}，結果t(R)=R∪NR。

3 結語

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