离散数学-图论-图的矩阵表示(12.1) 灰太狼 2024-03-29 14:56 20阅读 0赞 ### 图的矩阵表示 ### #### 1 关联矩阵 #### 定义:设无向图G=<V,E>,V=\{ v 1 , v 2 , ⋅ ⋅ ⋅ , v n v\_1,v\_2,···,v\_n v1,v2,⋅⋅⋅,vn\},E=\{ e 1 , e 2 , ⋅ ⋅ ⋅ , e m e\_1,e\_2,···,e\_m e1,e2,⋅⋅⋅,em\},令 m i j m\_\{ij\} mij为顶点 v i v\_i vi与边 e j e\_j ej的关联次数,则称 ( m i j ) n × m (m\_\{ij\})\_\{n×m\} (mij)n×m为G的关联矩阵,记作M(G)。 例如: 无向图的关联矩阵为 ![在这里插入图片描述][248556df26644ca6980423edf450b3cf.png] 结论:矩阵的数值为顶点与边的关联次数 #### 2 邻接矩阵 #### 定义:设无向图G=<V,E>,V=\{ v 1 , v 2 , ⋅ ⋅ ⋅ , v n v\_1,v\_2,···,v\_n v1,v2,⋅⋅⋅,vn\},令 a i j a\_\{ij\} aij为顶点 v i v\_i vi邻接到顶点 v j v\_j vj的边的条数,称 ( a i j ) n × m (a\_\{ij\})\_\{n×m\} (aij)n×m为D的邻接矩阵,记作A(D),或简记为A。 有向图D的邻接矩阵为: ![在这里插入图片描述][695ecb1fe20c46d192f7c60bdee4ce60.png] 可以得出 A 2 , A 3 , A 4 A^2,A^3,A^4 A2,A3,A4: ![在这里插入图片描述][3cccf6e4ee0846baa00880d213b86b73.png] 不难看出,D中 v 2 v\_2 v2到 v 4 v\_4 v4的长度为1,2,3,4的通路分别为0,1,1,2条。 v 4 v\_4 v4到自身长度为1,2,3,4的回路分别为1,2,3,5条,D中长度小于等于4的通路有53条,其中有15条回路。 结论:A为 v i v\_i vi到达 v j v\_j vj长度为1的条数; A 2 A^2 A2为 v i v\_i vi到达 v j v\_j vj长度为2的条数; A 3 A^3 A3为 v i v\_i vi到达 v j v\_j vj长度为3的条数; A 4 A^4 A4为 v i v\_i vi到达 v j v\_j vj长度为4的条数 ### 3 可达矩阵 ### 定义:设无向图G=<V,E>,V=\{ v 1 , v 2 , ⋅ ⋅ ⋅ , v n v\_1,v\_2,···,v\_n v1,v2,⋅⋅⋅,vn\},令 P i j \{ a v i 可达 v j c 否则 P\_\{ij\}\\begin\{cases\} a & v\_i可达v\_j\\\\ c &否则 \\end\{cases\} Pij\{ acvi可达vj否则 称 P i j P\_\{ij\} Pij为D的可达矩阵,记作P(D),简记为P 有向图D的可达矩阵为: ![在这里插入图片描述][82048b9a9d4244ab97c6b644928f6b8b.png] 结论: v i v\_i vi能否到达 v j v\_j vj [248556df26644ca6980423edf450b3cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/dc9a1ae4268e4939a18b6dcc4a14badf.png [695ecb1fe20c46d192f7c60bdee4ce60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/fe017d334fa94a37a58509f0b85ef545.png [3cccf6e4ee0846baa00880d213b86b73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/15a2a105f13f4eb29a907fc8250e8a54.png [82048b9a9d4244ab97c6b644928f6b8b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/492b5f7de5f9459b9e4be019e2150b18.png
还没有评论,来说两句吧...