關(guān)于可達(dá)性矩陣的一類算法的研究

程楠

DOI：10.16661/j.cnki.1672-3791.2017.25.247

摘 要：對于線性代數(shù)教材中，給出了很多種不同的計算方法，但是教材之中的這些方法均顯得比較復(fù)雜、繁瑣。而基于布爾矩陣?yán)碚撚嬎憧蛇_(dá)性矩陣，方法比較簡便，步驟較為清晰，可為大多數(shù)人所接受。本研究主要探討了布爾矩陣?yán)碚撍惴ㄈ绾斡嬎憧蛇_(dá)性矩陣，旨在為從事本領(lǐng)域的研究者提供一種新的算法。

關(guān)鍵詞：可達(dá)性矩陣 布爾矩陣?yán)碚?算法

中圖分類號：G64 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2017）09（a）-0247-02

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

1 可達(dá)性矩陣的具體定義

設(shè)D=屬于有向圖，其中V=﹛v1，v2，v3…，vn﹜，現(xiàn)令：

vi可達(dá)vj

否則

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

2 可達(dá)性矩陣的一般算法

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

2.1 根據(jù)有向圖D的通路數(shù)或者回路數(shù)算法

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

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

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

2.2 基于來對可達(dá)性矩陣進(jìn)行計算

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

3 布爾矩陣的運算方法及其實際應(yīng)用

3.1 布爾矩陣的運算方法

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

布爾矩陣的加V和乘為：

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

3.2 應(yīng)用舉例

如：將圖1中的可達(dá)性進(jìn)行求解。

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

4 結(jié)論

綜上所述可以得知，有向圖D求解的方法較多，由本文上述推理可以得知，采用布爾矩陣?yán)碚撨M(jìn)行求解。實際上而言，當(dāng)階數(shù)水平更高時，此種方法計算可達(dá)性矩陣的優(yōu)越性更加明顯。

參考文獻(xiàn)

[1] 左孝凌，李為鏗，劉永才.離散數(shù)學(xué)[M].上海：上?？茖W(xué)技術(shù)文獻(xiàn)出版社，1982：291-294.

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

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

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

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