傳遞閉包的Matlab實現
2019-06-15 02:35:24孫翠先吳煥春
唐山學院學報 2019年3期
孫翠先，張 健，吳煥春
(唐山學院 基礎教學部，河北 唐山 063000)
0 引言
集合A上的二元關系R的傳遞性描述了序偶之間的內在聯系。當A的元數|A|比較小(|A|≤4)時，可通過序偶法、關系矩陣法或關系圖法判定，計算量不大，人工判定可以完成。但當|A|較大時，不論上述三種方法哪一種，人工計算量都非常巨大，基本上不可能完成。而求關系R的傳遞閉包t(R)時，當R不具有傳遞性，就需要通過不斷添加新序偶使之具備傳遞性為止。因此當|A|較大時，求t(R)變得非常困難。此時Warshall提出了一種算法[1]。本文在Warshall算法基礎上，利用關系矩陣，借助數學軟件Matlab，給出求t(R)的優化算法。此法實現了傳遞閉包的Matlab計算，最大優點是對|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={
3 結語
實例中全域關系|EA|=64，而|R|=8，|R|占|EA|的百分比只有12.5%，此時可以人工手算。但當|R|占|EA|的百分比只有30%以上時，人工求t(R)幾乎不可能實現，而此時突顯本文給出的方法的優越性。
