關于可達性矩陣的一類算法的研究

程楠

DOI：10.16661/j.cnki.1672-3791.2017.25.247

摘 要：對于線性代數教材中，給出了很多種不同的計算方法，但是教材之中的這些方法均顯得比較復雜、繁瑣。而基于布爾矩陣理論計算可達性矩陣，方法比較簡便，步驟較為清晰，可為大多數人所接受。本研究主要探討了布爾矩陣理論算法如何計算可達性矩陣，旨在為從事本領域的研究者提供一種新的算法。

關鍵詞：可達性矩陣 布爾矩陣理論 算法

中圖分類號：G64 文獻標識碼：A 文章編號：1672-3791（2017）09（a）-0247-02

圖的可達性矩陣主要是用于判斷圖中任意2點之間是閉合還是順暢的一個非常重要的途徑與手段，同時它也是判斷一個有向圖連通強弱的一個非常重要的方法。然而，目前常規求解可達性矩陣的方法較為繁瑣。對此，應該探尋一種簡便、實用的算法來對可達性矩陣進行求解計算，從而為此種類型的矩陣的求解提供一種新的方法。

1 可達性矩陣的具體定義

設D=屬于有向圖，其中V=﹛v1，v2，v3…，vn﹜，現令：

vi可達vj

否則

稱屬于D的可達性矩陣，一般可將其記為“P（D）”，簡化可記為P。由于∈V，vivi，由此可知：可達性矩陣P上主對角線上的元素均為數字1。

2 可達性矩陣的一般算法

對于可達性矩陣的計算而言，主要包括兩種方法，即：根據有向圖D的通路數或者回路數算法、算法。

2.1 根據有向圖D的通路數或者回路數算法

定理：首先設A為有向圖D的鄰接矩陣，集合V=﹛v1，v2，v3，…，vn﹜均屬于D的頂點集，那么A的l次冪（記作“Al”）之中的元素為D中vi到vj，長度為l所具有通路的數量大小，其中為vi至自身長度為l的回路的數量大小。

根據可達性矩陣的具體定義以及定理，我們可將Bn=A1+A2+…+An（其中n屬于圖中所有的頂點數量）中所有非0元素改為0，當改為0的元素保持不變。此外，還應該將主對角線上面的數字全部變成1。最后根據如上計算可得到可達性矩陣P（D）。

上述方法非常復雜，計算量較大，極易引起各種錯誤的發生。

2.2 基于來對可達性矩陣進行計算

實際上而言，在實際的可達性矩陣計算過程當中，對有向圖D中長度為l所具有的通路的數量興趣不大，因此在實際過程中，可采用邏輯加、乘的方法，也就是說，基于的方法對可達性矩陣進行求解，且將Cn主對角線的元素全部變成數字1，從而可達性矩陣就計算出來了。

3 布爾矩陣的運算方法及其實際應用

3.1 布爾矩陣的運算方法

布爾加V與布爾乘的具體運算方法如下：

布爾矩陣的加V和乘為：

最終，應該注意將Bn中主對角線上數字均不為1的元素均用數字1來替換。

3.2 應用舉例

如：將圖1中的可達性進行求解。

根據如上推理及演算，最終得出P（D）=B5。

4 結論

綜上所述可以得知，有向圖D求解的方法較多，由本文上述推理可以得知，采用布爾矩陣理論進行求解。實際上而言，當階數水平更高時，此種方法計算可達性矩陣的優越性更加明顯。

參考文獻

[1] 左孝凌，李為鏗，劉永才.離散數學[M].上海：上海科學技術文獻出版社，1982：291-294.

[2] 耿素云，屈婉玲.離散數學[M].北京：高等教育出版社，2008：118-122，285.

[3] 崔彩霞.一種利用普通矩陣運算求傳遞閉包的方法[J].中國信息科技，2007（23）：100.

[4] 龐倩超.基于布爾矩陣運算的有向圖可達矩陣[J].大慶石油學院學報，2006，30（6）：99-101.

[5] 耿素云.離散數學[M].北京：高等教育出版社，1998.