【离散数学】图论（六）图的表示——矩阵

正文之前

在用计算机来表示一个图时，通常是采用矩阵形式来表示的，这一篇我们将介绍两种矩阵

• 邻接矩阵(adjacency matrix)
• 关联矩阵(incidence matrix)

正文

1. 邻接矩阵

1. 画图

• 在邻接矩阵中，设矩阵共有i行，j列，行和列都用结点表示

• i ≠ j 时，i 和 j 的元素表示与结点 i 和结点 j 相关联的边数

• i = j 时，元素表示与此结点相关联的圈数的两倍

简单来说，每一列的元素之和或者每一行的元素之和（二者相同）表示该结点的度数

以此图为例，列举各结点度数：

• a - 3
• b - 5（圈表示2）
• c - 3
• d - 3

所以我们得出如下邻接矩阵：

2. 特点

若A为一个简单图的邻接矩阵，则Aⁿ_i.j表示结点 i 到结点 j 的长度为 n 的路径数量，图的每条边长度都为1（听上去有点生涩，我们举个例子）

此图为例，我们画出邻接矩阵

然后我们画出矩阵A²

在矩阵A²中：

A²_a,a表示从结点 a 到结点 a 有3条长度为2的路径：

1. (a, b, a)
2. (a, c, a)
3. (a, d, a)

A²_a,b表示从结点a到结点b有1条长度为2的路径：

1. (a, c, b)

A²_a,c表示从结点a到结点c有2条长度为2的路径：

1. (a, b, c)
2. (a, d, c)

A²_a,d表示从结点a到结点d有1条长度为2的路径：

1. (a, c, d)

关联矩阵

1. 画图

• 在关联矩阵中，设矩阵共有i行，j列，行用结点表示，列用边表示

• 当某个结点v与某条边e关联时，就用1表示A_v,e，否则，用0表示

画出关联矩阵：

关于图的表示就介绍到这里了，谢谢大家！