离散数学中的图矩阵

本文涉及到的图矩阵主要包括邻接矩阵和关联矩阵，在离散数学中这部分内容属于用矩阵来表示图。

邻接矩阵

定义

用矩阵表示图，首先应该明确矩阵的阶数，从以上定义来看，临接矩阵的行列取决于顶点数。行和列均为定点数。

邻接矩阵是图顶点之间的关系，包括顶点集合，顶点之间权值，顶点直接不相通，可以用无穷大来表示

邻接图 图-1 邻接矩阵结构

二维数据表示

图-3 二维数组

关联矩阵

关联矩阵是顶点与边之间的关系。

对于无向图关联矩阵，Mij取值只能是{1，2，0}三种中一个。 分别表示关联一次，关联两次（顶点和起点重合的环），不关联。

对于有向图关联矩阵，Mij的取值只能是{1，-1,0}三种中一个。分别表示Vi为ej的起点，Vi为Ej的终点，Vi与ej不关联。下图中的例子即为有向图关联矩阵。

例：

有向图-顶点与边关系 有向图关联矩阵

参考资料

图邻接矩阵