教育信息处理13.pptVIP

二、图的矩阵描述……可达性矩阵 第四节 以ISM法分析教材结构 ISM方法要解决的具体问题是：如何利用单元之间各种凌乱的、已知的关系，揭示出系统的内部结构。既然任意一个包含许多离散、无序元素的静态确定性系统，都可采用直观的图模型(有向图或无向图)来描述，并且能进一步表达成抽象的矩阵形式，那么如果能先用图模型和矩阵描述出上述各种已知关系，在矩阵的基础上再进一步运算、推导，或许就能达到我们的目的，事实上这正是ISM方法解决问题的基本思路。 ISM方法主要通过建立解释结构模型来描述系统的结构，在这里，解释结构模型是指描述系统各单元之间关系的某种数学模型，例如，有向图就是一种直观的解释结构模型，矩阵表达式则是一种抽象的解释结构模型。 对于一个实际的系统，其解释结构模型的建立是一个从直观到抽象，然后又回到直观的过程，反映在结构模型的表现形式上，是从有向图过渡到邻接矩阵，可达矩阵、结构矩阵，最后得到多级递阶形式的层级网络图的一个过程。 4、可达矩阵的分解 分解可达矩阵的具体步骤是： 1）区域分解，就是将矩阵M化为分块对角化矩阵，或者说，把矩阵分解成m个分离的区域，使不同区域单元之间相互独立； 2）级间分解，即对属于同一区域内的单元进行分级，以明确各单元之间的层级关系； 3）求解结构模型。 1）区域分解 定义两个集合R(Si)、A(Si)设某系统可以表示为S=｛S1,S2,…,Sn｝, R(Si)：从Si出发，可能达到的全部要素的集合，称为可达集合。 A(Si)：所有可能达到Si的要素的集合，称为先行集合。 R(Si)∩A(Si)是从要素Si可能达到，而且又是能够达到Si的全部要素的集合。在图论中，这是一种强连接要素，或在图中处于环状的要素。 记底层单元的集合为B，则： B=｛Si∈S│A(Si)=R(Si)∩A(Si)｝ 对于底层单元集合B中的任意两个元素Bu和Bv，如果它们的可达性集合没有交集，则这两个单元分属于不同区域，反之，则属于同一区域。可得区域分解的准则： 如果R(Bu)∩R(Bv)≠空集，则Bu和Bv属于同一区域； 如果R(Bu)∩R(Bv)＝空集，则Bu和Bv属于不同区域； 将属于相同区域的单元归在一起，就可把集合S分离成m个独立的区域： ∏(S)=P1，P2，…，Pm（m为区域数） 称仅对角线元素为1，其他各个元素均为0，即： i=j时，Xij=1；i≠j时，Xij=0 X={Xij}，这样的矩阵为单位矩阵，并以I表示。 令I为单位矩阵，则系统(A)的可达性矩阵可定义为满足下列关系式的矩阵M： (A+I)k-1≠(A+I)k=(A+I)k+1=M 在这里可达矩阵的元素Mij的值，表示的是从Si出发，不论长度为多长，能否到达Sj的情况（假设任何Sj对它本身而言也是可达的）。