图论基础：邻接矩阵与关联矩阵详解

图论基础：邻接矩阵与关联矩阵详解

引用

CSDN

1.

https://blog.csdn.net/weixin_43135178/article/details/135897339

在图论中，邻接矩阵和关联矩阵是两种常用的图的表示方法。它们分别从不同的角度描述了图的结构特征，对于理解和分析图的性质具有重要作用。本文将详细介绍这两种矩阵的概念、特点及其区别。

邻接矩阵

邻接矩阵是一种用来表示图中顶点间相互连接关系的矩阵。在邻接矩阵中，矩阵的行和列都代表图中的顶点。

对于无权图，如果顶点 i 和顶点 j 之间有一条边，则矩阵中的元素 Aij （位于第 i 行和第 j 列）将会是1；如果没有边，那么 Aij 将会是0。

对于有权图，Aij 将会是相应边的权重值。

对于无向图，邻接矩阵是对称的，因为边是双向的；对于有向图，邻接矩阵则不一定是对称的。

关联矩阵

对于关联矩阵第一行1 0 0 -1 1，表示点v1和各边的关系。（其中1表示是正向、-1表示是逆向）

如图1所示，v1和e1,e4,e5相连，和e2、e3未连，故关联矩阵的值为1 0 0 -1 1. 下面各行为点v2，v3, v4和各边的关联，以此类推。

关联矩阵是另一种表示图的方式，它关注的是顶点和边之间的关系。在关联矩阵中，矩阵的行代表图中的顶点，列代表图中的边。

如果顶点 i 和边 ej 相关联（即顶点 i 是边 ej 的一个端点），则矩阵中的元素 Bij 会是1（或者边的权重，如果是有权图）。

如果顶点 i 不是边 ej 的端点，则 Bij 会是0。

对于无向图的关联矩阵，每列有两个1（因为无向边有两个端点）；对于有向图，每列会有一个1（指向端点）和一个-1（来自端点），表示边的方向。

邻接矩阵与关联矩阵的关系

• 邻接矩阵主要描述顶点之间是否相连，而关联矩阵描述的是顶点和边之间的关系。
• 邻接矩阵是方阵，其大小为顶点数量的平方，即 n×n。关联矩阵的大小为顶点数量乘以边的数量，即 n×m。
• 邻接矩阵可以用来快速检查任意两个顶点是否直接相连。关联矩阵可以用来快速检查任意一个顶点与哪些边相连。
• 在某些计算中，如计算图的度数，邻接矩阵通常更为直接和方便。而关联矩阵在诸如网络流问题或是寻找图的割集（cut sets）等问题中可能更加有用。