图Graph的表示

本文概述

• （a）无向图的表示
• （b）有向图的表示
• （c）多重图的表示

有两种用矩阵表示图G的主要方法, 即邻接矩阵和关联矩阵表示。

（a）无向图的表示

1.邻接矩阵表示：如果无向图G由n个顶点组成, 则图的邻接矩阵为n x n矩阵A = [aij], 由下式定义

如果顶点vi和vj之间存在边, 其中i是行, j是列, 则aij = 1的值。

如果顶点vi和vj之间没有边, 则aij的值= 0。

示例：找到图G所示的图G的邻接矩阵MA：

解：由于图G由四个顶点组成。因此, 邻接矩阵将为4 x 4矩阵。邻接矩阵如下图所示：

2.关联矩阵表示：如果无向图G由n个顶点和m个边组成, 则关联矩阵为n x m矩阵C = [cij], 定义为

在入射矩阵中, 每个顶点都有一行, 每个边缘都有一行。

无向图（无环）的入射矩阵中1的数量等于图中所有顶点的度之和。

示例：考虑如图3所示的无向图G。找到其发生率矩阵MI。

解决方案：无向图由四个顶点和五个边组成。因此, 入射矩阵为4 x 5矩阵, 如图所示：

（b）有向图的表示

1.邻接矩阵表示：如果有向图G由n个顶点组成, 则图的邻接矩阵为n x n矩阵A = [aij], 由下式定义

如果顶点Vi和Vj之间存在边, 且Vi为初始顶点, Vj为最终顶点, 则aij的值= 1。

如果顶点Vi和Vj之间没有边, 则aij的值= 0。

有向图的邻接矩阵中的1的数量等于边的数量。

示例：考虑图2中所示的有向图。确定其邻接矩阵MA。

解：由于有向图G由五个顶点组成。因此, 邻接矩阵将是5 x 5矩阵。有向图的邻接矩阵如下：

2.关联矩阵表示：如果有向图G由n个顶点和m个边组成, 则关联矩阵为n x m矩阵C = [cij], 由下式定义

入射矩阵中的1的数量等于图中边的数量。

示例：考虑如图5所示的有向图G。找到其发生率矩阵MI。

解决方案：有向图由四个顶点和五个边组成。因此, 入射矩阵是一个4 x 5的矩阵, 如图所示：

（c）多重图的表示

仅由邻接矩阵表示形式表示。

（i）多重图的邻接矩阵表示：如果多重图G由顶点组成, 则图的邻接矩阵为n x n矩阵A = [aij], 并由

如果顶点vi和vj之间存在一个或多个边缘, 则aij = N, 其中vi和vj之间的边缘数目为。

如果vi和vj之间没有边缘。

示例：考虑图所示的多图, 确定其邻接矩阵。

解决方案：由于多重图由五个顶点组成。因此, 邻接矩阵将是5 x 5矩阵。多重图的邻接矩阵如下：