邻接矩阵与可达矩阵计算

暨南大学应急管理学院1.邻接矩阵本部分内容出自《离散数学》图论章节1.邻接矩阵邻接矩阵的定义设G＝V，E是一个简单图，它有n个结点V＝{v1，v2，…，vn}，则n阶方阵A(G)＝(aij)称为G的邻接矩阵。aijVi与Vj之间存在关系；10Vi与Vj之间没有关系或者相同；0100000100000100000000100A12453邻接矩阵表达有向图1.邻接矩阵有向图邻接矩阵0100010100010110010000100A12453邻接矩阵表达有向图1.邻接矩阵无向图邻接矩阵说明：该邻接矩阵为对称矩阵1.邻接矩阵邻接矩阵乘幂表达的信息假设：A为简单图G的邻接矩阵，则Al中的第i行第j列元素等于联接图中节点vi到vj以的长度为l的链（或路）是数目。lija1.邻接矩阵邻接矩阵乘幂表达的信息证明：按照归纳法进行证明。当l=1时，，定理显然为真。假设，当l=k时，定理成立，考察l=k+1的情形如下：即：1lAAA1kkAAA11nkkijirrjraaa1.邻接矩阵邻接矩阵乘幂表达的信息根据假设和邻接矩阵的定义，可知：是联接Vi与Vr长度为k的链的数目，是联接Vr与Vj长度为1的链的数目。因此，表达式右端表示每一项由Vi经过一条长度为k的链到Vr，再由Vr经过一条边到Vj的，总长度为k+1的链的数目。11nkkijirijraaarjakira1.邻接矩阵邻接矩阵乘幂表达的信息对r进行求和，即得，表示所有从Vi到Vj长度为k+1的链的数目。1kija1.邻接矩阵案例0100010100010000000100010A有向图邻接矩阵1.邻接矩阵案例21010002000101000001000001A1.邻接矩阵案例30200020200020000000100010A1.邻接矩阵案例42020004000202000001000001A2.可达矩阵可达矩阵的定义设G＝V，E是一个简单图，它有n个结点V＝{v1，v2，…，vn}。若n阶方阵P＝(pij)称为G的可达矩阵，则：pijVi到Vj可达；10Vi到Vj不可达；2.可达矩阵可达矩阵计算程序从图G中的邻接矩阵A计算n步可达矩阵M，令：B=(A+I)n=I+A+A2+…+An再把B中的非零元素改为1而零元素不变，变换后的矩阵即为可达矩阵M。2.可达矩阵可达矩阵的性质可达矩阵表明了图中任意两结点间是否至少存在一条链以及在节点处是否有回路。B=(A+I)n表示两个结点之间经过n步是否能够联通的情况。2.可达矩阵可达矩阵布尔计算方法•布尔矩阵定义：矩阵中的元素属于0或1的矩阵；•图的邻接矩阵是一种典型的布尔矩阵；•图的可达矩阵也是一种布尔矩阵；2.可达矩阵可达矩阵布尔计算方法•布尔矩阵运算规则：（1）0+0=0；（2）0+1=1；（3）1+0=1；（4）1+1=1；2.可达矩阵可达矩阵布尔计算方法在计算(A+I)n的过程中利用布尔运算法则进行计算。124532.系统结构模型1100001100()001100001000101AI有向图邻接矩阵2.系统结构模型110001100011100011000110001110*001100011000110000100001000010001010010100111布尔运算乘积经过两步的可达矩阵2步可达矩阵2.系统结构模型111001110011110011100111001110*001100011000110000100001000010001110011100111布尔运算乘积经过三步的可达矩阵3步可达矩阵