对称矩阵有什么性质 已知邻接矩阵求可达矩阵

对称矩阵有什么性质 已知邻接矩阵求可达矩阵

初中音乐教学反思-韵母是什么

龙源期刊网

基于ISM的可达矩阵简易算法及实现

作者：姚道洪

来源：《价值工程》2015年第28期

摘要：系统解释结构模型（ISM）是系统工程中广泛运用的一种分析方法，根据邻接矩阵

求可达矩阵是建立多级递阶结构模型的一个重要步骤.本文从邻接矩阵和可达矩阵的定义出

发，介绍了一种求可达矩阵的简易方法，并通过MATLAB编程实现。

Abstract：InterpretativeStructuralModeling（ISM）isananalyticmethodanditiswidely

usedinsystemengineering，andthecalculationofreachabilitymatrixisalsothemostimportantstep

ngfromthedefinitionofadjacencymatrixandreachabilitymatrix，thispaper

introducesasimplealgorithmofreachalilitymatrix，andattachedtoprogramcode.

关键词：解释结构模型；邻接矩阵；可达矩阵；Matlab

Keywords：interpretativestructuralmodeling；adjacencymatrix；reachabilitymatrix；

Matlab

中图分类号：TP391文献标识码：A文章编号：1006-4311（2015）28-0212-03

0引言

解释结构模型法（InterpretativeStructuralModelingMethod，简称ISM），是系统分析中常

用的结构模型化技术。它将复杂系统化整为零，充分利用专家知识，将子系统结合计算机技术

构建多级递阶结构模型。在要素较多，关系错综复杂的情况下，ISM能发挥重要作用，利用有

向图、矩阵、计算机技术定性地对要素间层次结构做一解释，以助于对系统做出合理评价。图

论在近半个世纪以来得到了飞速发展，图论的应用也从最初的迷宫游戏应用到了工程领域，数

学上的理论价值也逐渐突显。通过矩阵研究图，是几何问题代数化的典型例子，特别是伴随着

计算机的迅猛发展，图论问题的计算效率也得到了飞速提升。

邻接矩阵、可达矩阵和关联矩阵是图的三种常用表达形式，在已知邻接矩阵求可达矩阵问

题上，成熟的常用方法在文献[1]中有介绍：一般方法要对有向图的邻接矩阵做多次幂乘运

算，布尔矩阵算法在有向图的结点数量较少时适用，通过求传递闭包的Warshall算法在计算机

的协助下效率更高。这些算法计算量大，算法原理较难掌握，也影响到ISM在系统分析中的

推广应用。为此，很多文献都为简化可达矩阵算法做了努力：文献[2]利用求传递闭包的算法

求可达矩阵；文献[3]奖有向图表达成二元关系，通过计算删减二元关系的传递闭包来求解可

达矩阵；文献[4]用VB实现了Warshall算法；文献[5]在传统算法基础上提出最短路径的可达

矩阵算法；文献[6]充分利用可达顶点传递性阐述了一种更为简便的方法求可达矩阵。本文从

龙源期刊网

邻接矩阵的构造意义出发，设计了一表式操作求可达矩阵的算法，并通过MATLAB编程实

现。

1基本概念

1.2可达矩阵

定义3：对于有向图D=，V={v1，v2，…，vn}，设

pij=1，从vi到vj存在通路0，从vi到vj不存在通路

则称矩阵P（D）=（pij）n×n为有向图的可达矩阵。

可达矩阵可以表达任意两顶点间是否存在通路。

2由邻接矩阵求可达矩阵的简易算法

2.1原理

在邻接矩阵A（D）（以下用A表示）中，如果aij=1，表示顶点vi到vj有通路；同时如

果ajk=1，表示顶点vj到vk也有通路，那么在vi到vk间也必定有通路，即aik=1。换言之，

如果aij=1且ajk=1，那么在B=（bij）n×n=AT中bkj=ajk=1，我们就在矩阵A和B的第j列找

值为1的元素，同时记录下1所在的行数i和k，然后把矩阵A中的aik改写成1。可能在矩阵

A和B的第j列的不同行都有1，那就对i和k做不同组合，然后把矩阵A中所有的aik都改写

成1。以上过程对所有的j=1，2，…，n都进行查找和改写，每一轮改写后重新再对各列j=1，

2，…，n再次查找和改写，直到矩阵A不可再修改为止，然后把主对角线上的所有元素都改

写成1，最终邻接矩阵A就被改写成了可达矩阵M。

2.2操作步骤

可以根据上述原理设计步骤，同时这也是编写计算机程序的参照步骤：

①确立邻接矩阵A并求转置矩阵AT；

②从第1列起，将A和AT中各列逐个查找，把值为1的行数i和k记录下来（可能有多

对），然后把A中第i行第k列的元素改写成1；

③在其他各列上重复第②步，直到A中无可改写元素为止；

④将中主对角线上的元素全部换成1，便得到可达矩阵M。

3应用举例

龙源期刊网

5结语

本文做了两个工作：一是简化了由邻接矩阵求可达矩阵的算法，整个求解过程通过表格操

作完成；二是根据简化算法思想，借助于MATLAB计算软件编写了一个M文件，程序简捷，

运行速度快，有进一步推广使用的价值。

参考文献：

[1]王欣欣，李金保.关于由邻接矩阵求可达性矩阵的方法[J].吉林化工学院学报，2005，22

（4）：89-94.

[2]孙玉霞.谈谈可达性矩阵的一类算法[J].科技信息，2013（8）：262.

[3]汪小燕.基于被删减二元关系的可达性矩阵求解[J].苏州科技学院学报（自然科学版），

2014，31（1）：67-69.

[4]叶红.可达矩阵的Warshall算法实现[J].安徽大学学报（自然科学版），2011，35

（4）：31-35.

[5]原慧琳，汪定伟.最短路径的可达矩阵算法[J].信息与控制，2011，40（2）：202-208.

[6]白冰，李平.基于ISM的可达矩阵的简便算法[J].价值工程，2015，34（4）：213-215.

[7]孙道德，王敏生.离散数学[M].合肥：中国科学技术大学出版社，2010.