岳秋菊　祁建宏　任志國(guó)　馮婕　屈易麗

(蘭州城市學(xué)院信息工程學(xué)院， 蘭州 730070)

?

利用Excel求解鄰接矩陣的冪矩陣

岳秋菊祁建宏任志國(guó)馮婕屈易麗

(蘭州城市學(xué)院信息工程學(xué)院， 蘭州 730070)

摘要：鄰接矩陣的冪矩陣可以用于求解集合上二元關(guān)系的傳遞閉包及圖論中的路徑矩陣、強(qiáng)分支等，但當(dāng)鄰接矩陣的階數(shù)較高時(shí)手工求解計(jì)算量大且繁瑣。針對(duì)此問(wèn)題，利用Excel中的函數(shù)求解功能，簡(jiǎn)化求解過(guò)程。

關(guān)鍵詞：鄰接矩陣； 冪矩陣； 傳遞閉包； 路徑矩陣

在離散數(shù)學(xué)中，鄰接矩陣的冪矩陣應(yīng)用廣泛，但求解冪矩陣時(shí)計(jì)算量大且容易出錯(cuò)。本文利用Excel中的函數(shù)求解冪矩陣，并在Excel中對(duì)冪矩陣的一些應(yīng)用給出簡(jiǎn)單易懂的求解方法，尤其是省去了需要編程的麻煩。

1相關(guān)概念

1.1鄰接矩陣

1.2傳遞閉包的關(guān)系矩陣A+和圖G的路徑矩陣P

對(duì)于集合V上的二元關(guān)系E，A是關(guān)系E的關(guān)系矩陣，可傳遞閉包E+的關(guān)系矩陣應(yīng)為：

A+=A∨A(2)∨A(3)∨…∨A(n)=P

(1)

1.3由給定圖G的路徑矩陣P求圖中結(jié)點(diǎn)的強(qiáng)分支

2利用Excel中的函數(shù)求解鄰接矩陣的冪矩陣

下面利用具體實(shí)例講述求解過(guò)程。設(shè)一簡(jiǎn)單有

向圖G的鄰接矩陣A：

在Excel中求解鄰接矩陣的冪矩陣的步驟：

第一步，在Excel表中的“A1:F6”數(shù)據(jù)區(qū)域輸入矩陣A。

第二步，先選定存放A(2)的數(shù)據(jù)區(qū)域“G1：L6”，再按編輯鍵F2后，選擇“插入”→“函數(shù)”→“MMULT(array1,array2)”,用點(diǎn)選方式在array1和array2中輸入或者選擇求乘積的矩陣區(qū)域，或在編輯區(qū)域輸入“=MMULT(A1:F6,A1:F6)”，最后同時(shí)按住“CTRL+SHIFT+ENTER”，此時(shí)可求得A(2)，用類(lèi)似的方法可依次求得A(3),A(4),A(5),A(6)，結(jié)果如圖1所示。

3鄰接矩陣的冪矩陣應(yīng)用

3.1各階冪矩陣在有向簡(jiǎn)單圖中應(yīng)用

圖1　鄰接矩陣的各階冪矩陣

3.2在Excel中求解傳遞閉包矩陣和路徑矩陣

按布爾運(yùn)算方法求解公式(1)，先求冪矩陣的和矩陣，再將和矩陣中的非零元素變?yōu)?，0元素不變，求得的矩陣與按布爾運(yùn)算求得的矩陣結(jié)果相同。下面先求冪矩陣的和矩陣，再求關(guān)系矩陣和路徑矩陣，步驟如下：

第一步，在Excel中的A8單元格中輸入“=A1+G1+M1+S1+Y1+AE1”,回車(chē)。

第二步，選擇A8向左拖動(dòng)填充柄至F8，再選擇“A8:F8”，向下拖動(dòng)至“A13:F13”，此時(shí)區(qū)域“A8：F13”的數(shù)據(jù)區(qū)域就是冪矩陣的和矩陣：A+A(2)+A(3)+A(4)+A(5)+A(6)。

第三步，在Excel中的H8單元格中輸入“=IF(A8>0,1,0)”，回車(chē)后向左拖動(dòng)至M8單元格，再選擇“H8:M8”單元格向下拖動(dòng)至“H13:M13”，即可求得傳遞閉包的關(guān)系矩陣A+和路徑矩陣P，如圖2所示。

圖2　傳遞閉包的關(guān)系矩陣A+和路徑矩陣P

3.3利用路徑矩陣在Excel中求解圖G的強(qiáng)分支

按照P×PT的定義，在Excel中的求解步驟：

第一步，選中路徑矩陣P的數(shù)據(jù)區(qū)域單元格“H8:M13”，再右鍵點(diǎn)擊“復(fù)制”。

第二步，先選中A15單元格，再選擇“選擇性粘貼”，在對(duì)話框中選中“數(shù)值”和“轉(zhuǎn)置”，再點(diǎn)“確定”，此時(shí)路徑矩陣的轉(zhuǎn)置矩陣PT就在“A15:F20”單元格中。

第三步，先選中H15單元格，輸入“=H8*A15”，再向左拖動(dòng)填充柄至M15單元格，最后選擇“H15:M15”后向下拖動(dòng)填充柄至“H20:M20”，此時(shí)“H15:M20”單元格中的數(shù)據(jù)就是 P×PT矩陣中的數(shù)據(jù)，如圖3所示。

圖3　P矩陣和P×PT矩陣

在P×PT矩陣中，第1行中的元素(1,1)，(1,3)，(1,4)，(1,5)的值都為1，由此可知結(jié)點(diǎn)v1和結(jié)點(diǎn)v3,v4,v5構(gòu)成強(qiáng)分支，也可從第3行或者第4、第5行中得到同樣的結(jié)果；第2行中元素(2,2)和(2,6)的值都為1，則可知點(diǎn)v2和點(diǎn)v6構(gòu)成強(qiáng)分支，也可從第6行得到相同的結(jié)果。因此，圖G中的強(qiáng)分支為：{v1,v3,v4,v5}和{v2,v6}。

4結(jié)語(yǔ)

通過(guò)Excel中的函數(shù)求解鄰接矩陣的冪矩陣，以及對(duì)冪矩陣的各種應(yīng)用的求解過(guò)程，可以看出利用Excel中的函數(shù)求解簡(jiǎn)單易懂。尤其是對(duì)不懂程序設(shè)計(jì)和數(shù)學(xué)知識(shí)薄弱的人來(lái)講，由于大部分人經(jīng)常用Excel來(lái)做簡(jiǎn)單的數(shù)據(jù)處理，對(duì)該軟件比較熟悉，于是運(yùn)用Excel求解就變得非常容易，避免了人工求解時(shí)的繁瑣和容易出錯(cuò)的問(wèn)題。

參考文獻(xiàn)

[1] 王海樹(shù). Excel在矩陣相關(guān)計(jì)算中的應(yīng)用[J]．電腦知識(shí)與技術(shù)，2007(1)：12-14.

[2] 曹曉東，原旭. 離散數(shù)學(xué)及算法[M]. 北京：機(jī)械工業(yè)出版社，2008：145-152.

[3] 岳秋菊. 基于最短路徑優(yōu)化問(wèn)題Dijkstra算法程序的設(shè)計(jì)和實(shí)現(xiàn)[J]．甘肅高師學(xué)報(bào)，2008(2)：28-30.

[5] 岳秋菊，朱正平. 基于圖的鄰接矩陣求其距離矩陣的算法與實(shí)現(xiàn)[J]. 自動(dòng)化與儀器儀表，2013(1)：139-140.

Using Microsoft Excel to Solve the Power of Adjacency Matrix

YUEQiujuQIJianhongRENZhiguoFengJieQUYili

(College of Information Technology of Lanzhou City University, Lanzhou 730070, China)

Abstract:The method of solving the transitivity closure of binary relations in the set and path Matrix or the strong connected component in Graph theory with manual labor calculating the Adjacency Matrix Power requires a large quantity of calculation, especially Higher-order matrix, which is very complex. In this paper, the above questions is realized by the built-in function Excel rather than programming. This solved the difficulties above greatly and made more complicated problems: the Adjacency Matrix Power problem very easy.

Key words:Adjacency Matrix; power matrix; transitive closure; path matrix

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1673-1980(2015)02-0118-02

中圖分類(lèi)號(hào)：TP391

作者簡(jiǎn)介：岳秋菊(1977 — )，女，碩士，講師，研究方向?yàn)閿?shù)據(jù)處理與算法。

基金項(xiàng)目：甘肅省教育廳科研項(xiàng)目(1111B-04)；甘肅省大專(zhuān)院?？蒲许?xiàng)目(2013-JY-25，2013-JY-26)

收稿日期：2014-09-29