离散数学-图论-图的矩阵表示（12.1）

灰太狼 2024-03-29 14:56 69阅读 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