利用Excel求解邻接矩阵的幂矩阵

岳秋菊　祁建宏　任志国　冯婕　屈易丽

(兰州城市学院信息工程学院， 兰州 730070)



利用Excel求解邻接矩阵的幂矩阵

岳秋菊祁建宏任志国冯婕屈易丽

(兰州城市学院信息工程学院， 兰州 730070)

摘要：邻接矩阵的幂矩阵可以用于求解集合上二元关系的传递闭包及图论中的路径矩阵、强分支等，但当邻接矩阵的阶数较高时手工求解计算量大且繁琐。针对此问题，利用Excel中的函数求解功能，简化求解过程。

关键词：邻接矩阵； 幂矩阵； 传递闭包； 路径矩阵

在离散数学中，邻接矩阵的幂矩阵应用广泛，但求解幂矩阵时计算量大且容易出错。本文利用Excel中的函数求解幂矩阵，并在Excel中对幂矩阵的一些应用给出简单易懂的求解方法，尤其是省去了需要编程的麻烦。

1相关概念

1.1邻接矩阵

1.2传递闭包的关系矩阵A+和图G的路径矩阵P

对于集合V上的二元关系E，A是关系E的关系矩阵，可传递闭包E+的关系矩阵应为：

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

(1)

1.3由给定图G的路径矩阵P求图中结点的强分支

2利用Excel中的函数求解邻接矩阵的幂矩阵

下面利用具体实例讲述求解过程。设一简单有

向图G的邻接矩阵A：

在Excel中求解邻接矩阵的幂矩阵的步骤：

第一步，在Excel表中的“A1:F6”数据区域输入矩阵A。

第二步，先选定存放A(2)的数据区域“G1：L6”，再按编辑键F2后，选择“插入”→“函数”→“MMULT(array1,array2)”,用点选方式在array1和array2中输入或者选择求乘积的矩阵区域，或在编辑区域输入“=MMULT(A1:F6,A1:F6)”，最后同时按住“CTRL+SHIFT+ENTER”，此时可求得A(2)，用类似的方法可依次求得A(3),A(4),A(5),A(6)，结果如图1所示。

3邻接矩阵的幂矩阵应用

3.1各阶幂矩阵在有向简单图中应用

图1　邻接矩阵的各阶幂矩阵

3.2在Excel中求解传递闭包矩阵和路径矩阵

按布尔运算方法求解公式(1)，先求幂矩阵的和矩阵，再将和矩阵中的非零元素变为1，0元素不变，求得的矩阵与按布尔运算求得的矩阵结果相同。下面先求幂矩阵的和矩阵，再求关系矩阵和路径矩阵，步骤如下：

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

第二步，选择A8向左拖动填充柄至F8，再选择“A8:F8”，向下拖动至“A13:F13”，此时区域“A8：F13”的数据区域就是幂矩阵的和矩阵：A+A(2)+A(3)+A(4)+A(5)+A(6)。

第三步，在Excel中的H8单元格中输入“=IF(A8>0,1,0)”，回车后向左拖动至M8单元格，再选择“H8:M8”单元格向下拖动至“H13:M13”，即可求得传递闭包的关系矩阵A+和路径矩阵P，如图2所示。

图2　传递闭包的关系矩阵A+和路径矩阵P

3.3利用路径矩阵在Excel中求解图G的强分支

按照P×PT的定义，在Excel中的求解步骤：

第一步，选中路径矩阵P的数据区域单元格“H8:M13”，再右键点击“复制”。

第二步，先选中A15单元格，再选择“选择性粘贴”，在对话框中选中“数值”和“转置”，再点“确定”，此时路径矩阵的转置矩阵PT就在“A15:F20”单元格中。

第三步，先选中H15单元格，输入“=H8*A15”，再向左拖动填充柄至M15单元格，最后选择“H15:M15”后向下拖动填充柄至“H20:M20”，此时“H15:M20”单元格中的数据就是 P×PT矩阵中的数据，如图3所示。

图3　P矩阵和P×PT矩阵

在P×PT矩阵中，第1行中的元素(1,1)，(1,3)，(1,4)，(1,5)的值都为1，由此可知结点v1和结点v3,v4,v5构成强分支，也可从第3行或者第4、第5行中得到同样的结果；第2行中元素(2,2)和(2,6)的值都为1，则可知点v2和点v6构成强分支，也可从第6行得到相同的结果。因此，图G中的强分支为：{v1,v3,v4,v5}和{v2,v6}。

4结语

通过Excel中的函数求解邻接矩阵的幂矩阵，以及对幂矩阵的各种应用的求解过程，可以看出利用Excel中的函数求解简单易懂。尤其是对不懂程序设计和数学知识薄弱的人来讲，由于大部分人经常用Excel来做简单的数据处理，对该软件比较熟悉，于是运用Excel求解就变得非常容易，避免了人工求解时的繁琐和容易出错的问题。

参考文献

[1] 王海树. Excel在矩阵相关计算中的应用[J]．电脑知识与技术，2007(1)：12-14.

[2] 曹晓东，原旭. 离散数学及算法[M]. 北京：机械工业出版社，2008：145-152.

[3] 岳秋菊. 基于最短路径优化问题Dijkstra算法程序的设计和实现[J]．甘肃高师学报，2008(2)：28-30.

[5] 岳秋菊，朱正平. 基于图的邻接矩阵求其距离矩阵的算法与实现[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

文献标识码：A

文章编号：1673-1980(2015)02-0118-02

中图分类号：TP391

作者简介：岳秋菊(1977 — )，女，硕士，讲师，研究方向为数据处理与算法。

基金项目：甘肃省教育厅科研项目(1111B-04)；甘肃省大专院校科研项目(2013-JY-25，2013-JY-26)

收稿日期：2014-09-29