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

岳秋菊　祁建宏　任志國　馮婕　屈易麗

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

?

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

岳秋菊祁建宏任志國馮婕屈易麗

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

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

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

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

1相關(guān)概念

1.1鄰接矩陣

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

對于集合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é)點的強分支

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

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

向圖G的鄰接矩陣A：

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

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

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

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

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

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

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

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

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

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

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

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

3.3利用路徑矩陣在Excel中求解圖G的強分支

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

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

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

第三步，先選中H15單元格，輸入“=H8*A15”，再向左拖動填充柄至M15單元格，最后選擇“H15:M15”后向下拖動填充柄至“H20:M20”，此時“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é)點v1和結(jié)點v3,v4,v5構(gòu)成強分支，也可從第3行或者第4、第5行中得到同樣的結(jié)果；第2行中元素(2,2)和(2,6)的值都為1，則可知點v2和點v6構(gòu)成強分支，也可從第6行得到相同的結(jié)果。因此，圖G中的強分支為：{v1,v3,v4,v5}和{v2,v6}。

4結(jié)語

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

參考文獻

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

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

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

[5] 岳秋菊，朱正平. 基于圖的鄰接矩陣求其距離矩陣的算法與實現(xiàn)[J]. 自動化與儀器儀表，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

文獻標(biāo)識碼：A

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

中圖分類號：TP391

作者簡介：岳秋菊(1977 — )，女，碩士，講師，研究方向為數(shù)據(jù)處理與算法。

基金項目：甘肅省教育廳科研項目(1111B-04)；甘肅省大專院校科研項目(2013-JY-25，2013-JY-26)

收稿日期：2014-09-29