图的表示

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

(a)无向图的表示

1. 邻接矩阵表示： 如果无向图 G 包含 n 个顶点，则图的邻接矩阵是一个 n x n 矩阵 A = [a_ij]，定义如下

如果顶点 v_i 和 v_j 之间存在一条边，其中 i 是行，j 是列，则 a_ij 的值为 1。

如果顶点 v_i 和 v_j 之间没有边，则 a_ij 的值为 0。

示例： 找到图 G 的邻接矩阵 M_A，如图所示

解决方案： 由于图 G 包含四个顶点。因此，邻接矩阵将是一个 4 x 4 矩阵。邻接矩阵如下所示

2. 关联矩阵表示： 如果无向图 G 包含 n 个顶点和 m 条边，则关联矩阵是一个 n x m 矩阵 C = [c_ij]，定义如下

对于每个顶点有一行，对于每条边有一列，在关联矩阵中。

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

示例： 考虑如图所示的无向图 G。 找到它的关联矩阵 M_I。

解决方案： 无向图包含四个顶点和五条边。 因此，关联矩阵是一个 4 x 5 矩阵，如图所示

(b)有向图的表示

1. 邻接矩阵表示： 如果有向图 G 包含 n 个顶点，则图的邻接矩阵是一个 n x n 矩阵 A = [a_ij]，定义如下

如果顶点 V_i 和 V_j 之间存在一条边，其中 V_i 是初始顶点，V_j 是最终顶点，则 a_ij 的值为 1。

如果顶点 V_i 和 V_j 之间没有边，则 a_ij 的值为 0。

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

示例： 考虑如图所示的有向图。 确定其邻接矩阵 M_A。

解决方案： 由于有向图 G 包含五个顶点。 因此，邻接矩阵将是一个 5 x 5 矩阵。 有向图的邻接矩阵如下所示

2. 关联矩阵表示： 如果有向图 G 包含 n 个顶点和 m 条边，则关联矩阵是一个 n x m 矩阵 C = [c_ij]，定义如下

关联矩阵中 1 的数量等于图中边的数量。

示例： 考虑如图所示的有向图 G。 找到它的关联矩阵 M_I。

解决方案： 有向图包含四个顶点和五条边。 因此，关联矩阵是一个 4 x 5 矩阵，如图所示

(c)多重图的表示

仅通过邻接矩阵表示表示。

(i)多重图的邻接矩阵表示： 如果多重图 G 包含顶点，则图的邻接矩阵是一个 n x n 矩阵 A = [a_ij]，定义如下

如果顶点 v_i 和 v_j 之间存在一条或多条边，则 a_ij = N，其中 N 是 v_i 和 v_j 之间的边的数量。

如果 v_i 和 v_j 之间没有边。

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

解决方案： 由于多重图包含五个顶点。 因此，邻接矩阵将是一个 5 x 5 矩阵。 多重图的邻接矩阵如下所示