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

程楠

DOI：10.16661/j.cnki.1672-3791.2017.25.247

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

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

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

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

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

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

vi可達(dá)vj

否則

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

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

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

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

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

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

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

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

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

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

3.1 布爾矩陣的運(yùn)算方法

布爾加V與布爾乘的具體運(yùn)算方法如下：

布爾矩陣的加V和乘為：

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

3.2 應(yīng)用舉例

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

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

4 結(jié)論

綜上所述可以得知，有向圖D求解的方法較多，由本文上述推理可以得知，采用布爾矩陣?yán)碚撨M(jìn)行求解。實(shí)際上而言，當(dāng)階數(shù)水平更高時(shí)，此種方法計(jì)算可達(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] 崔彩霞.一種利用普通矩陣運(yùn)算求傳遞閉包的方法[J].中國(guó)信息科技，2007（23）：100.

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

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