关于可达性矩阵的一类算法的研究

程楠

DOI：10.16661/j.cnki.1672-3791.2017.25.247

摘 要：对于线性代数教材中，给出了很多种不同的计算方法，但是教材之中的这些方法均显得比较复杂、繁琐。而基于布尔矩阵理论计算可达性矩阵，方法比较简便，步骤较为清晰，可为大多数人所接受。本研究主要探讨了布尔矩阵理论算法如何计算可达性矩阵，旨在为从事本领域的研究者提供一种新的算法。

关键词：可达性矩阵 布尔矩阵理论 算法

中图分类号：G64 文献标识码：A 文章编号：1672-3791（2017）09（a）-0247-02

图的可达性矩阵主要是用于判断图中任意2点之间是闭合还是顺畅的一个非常重要的途径与手段，同时它也是判断一个有向图连通强弱的一个非常重要的方法。然而，目前常规求解可达性矩阵的方法較为繁琐。对此，应该探寻一种简便、实用的算法来对可达性矩阵进行求解计算，从而为此种类型的矩阵的求解提供一种新的方法。

1 可达性矩阵的具体定义

设D=属于有向图，其中V=﹛v1，v2，v3…，vn﹜，现令：

vi可达vj

否则

称属于D的可达性矩阵，一般可将其记为“P（D）”，简化可记为P。由于∈V，vivi，由此可知：可达性矩阵P上主对角线上的元素均为数字1。

2 可达性矩阵的一般算法

对于可达性矩阵的计算而言，主要包括两种方法，即：根据有向图D的通路数或者回路数算法、算法。

2.1 根据有向图D的通路数或者回路数算法

定理：首先设A为有向图D的邻接矩阵，集合V=﹛v1，v2，v3，…，vn﹜均属于D的顶点集，那么A的l次幂（记作“Al”）之中的元素为D中vi到vj，长度为l所具有通路的数量大小，其中为vi至自身长度为l的回路的数量大小。

根据可达性矩阵的具体定义以及定理，我们可将Bn=A1+A2+…+An（其中n属于图中所有的顶点数量）中所有非0元素改为0，当改为0的元素保持不变。此外，还应该将主对角线上面的数字全部变成1。最后根据如上计算可得到可达性矩阵P（D）。

上述方法非常复杂，计算量较大，极易引起各种错误的发生。

2.2 基于来对可达性矩阵进行计算

实际上而言，在实际的可达性矩阵计算过程当中，对有向图D中长度为l所具有的通路的数量兴趣不大，因此在实际过程中，可采用逻辑加、乘的方法，也就是说，基于的方法对可达性矩阵进行求解，且将Cn主对角线的元素全部变成数字1，从而可达性矩阵就计算出来了。

3 布尔矩阵的运算方法及其实际应用

3.1 布尔矩阵的运算方法

布尔加V与布尔乘的具体运算方法如下：

布尔矩阵的加V和乘为：

最终，应该注意将Bn中主对角线上数字均不为1的元素均用数字1来替换。

3.2 应用举例

如：将图1中的可达性进行求解。

根据如上推理及演算，最终得出P（D）=B5。

4 结论

综上所述可以得知，有向图D求解的方法较多，由本文上述推理可以得知，采用布尔矩阵理论进行求解。实际上而言，当阶数水平更高时，此种方法计算可达性矩阵的优越性更加明显。

参考文献

[1] 左孝凌，李为铿，刘永才.离散数学[M].上海：上海科学技术文献出版社，1982：291-294.

[2] 耿素云，屈婉玲.离散数学[M].北京：高等教育出版社，2008：118-122，285.

[3] 崔彩霞.一种利用普通矩阵运算求传递闭包的方法[J].中国信息科技，2007（23）：100.

[4] 庞倩超.基于布尔矩阵运算的有向图可达矩阵[J].大庆石油学院学报，2006，30（6）：99-101.

[5] 耿素云.离散数学[M].北京：高等教育出版社，1998.