程楠
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=
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.