离散数学图的矩阵表示法.pptVIP

7.3 图的矩阵表示 ;无向图的关联矩阵; 例:求下图G的关联矩阵;无向图的关联矩阵;有向图的关联矩阵;例: 求图G的关联矩阵。 ;有向图的关联矩阵(续);定义 设有向图D=V,E, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令 为顶点vi邻接到顶点vj边的条数，称( )m?n为D的邻接矩阵, 记作A(D), 简记为A. ;求下图G的邻接矩阵。 ;定义 设有向图D=V,E, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令 为顶点vi邻接到顶点vj边的条数，称( )m?n为D的邻接矩阵, 记作A(D), 简记为A. 性质; D中的通路及回路数;D中的通路及回路数(续);例(续);在下图中v1到v3长度为1、2、3、4的通路分别有多少条，G中共有长度为4的通路多少条，其中回路多少条，长度小于等于4的通路共有多少条，其中回路多少条。 ;解:因为 ; 所以，由v1到v3长度为1、2、3、4的通路分别有0、2、2、4条，G中共有长度为4的通路43条，其中回路11条，长度小于等于4的通路共有87条，其中回路22条。 注 无向图也有相应的邻接矩阵，一般只考虑简单图，无向图的邻接矩阵是对称的，其性质基本与有向图邻接矩阵的性质相同。; 例如:下图邻接矩阵为： ;有向图的可达矩阵;有向图的可达矩阵(续);; 图9.24邻接矩阵A和A2，A3，A4如下：; ;则图G的可达性矩阵?;可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。 ; 定义 设G=?V,E?是简单无向图，V={v1,v2,…,vn} P(G)=( pij) n×n 其中： i,j=1,…,n 称P(G)为G的连通矩阵。简记为P。 无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。