最后更新: 2025-01-22 09:19 ● 参与者查看: 27 次纠错分享参与项目词条搜索

邻接矩阵

定义 8.19 （邻接矩阵）设 $G$ 是 $n$ 个顶点，无多重边的图。 $n \times n$ 矩阵 $M=\left(m_{i j}\right)$（依顶点次序 $v_1, v_2, \cdots, v_n$ 标记在矩阵的行和列上），也记为 $M(G)$ ，其中

$$
m_{i j}= \begin{cases}1 & \text { 若 } v_i \text { 与 } v_j \text { 相邻 } \\ 0 & \text { 若 } v_i \text { 与 } v_j \text { 不相邻 }\end{cases}
$$

称 $M(G)$ 为 $G$ 的邻接矩阵。

![图片](/uploads/2025-01/5ee639.jpg)
 
 例 8.3 如图 8.9 所示，
按顶点次序 $1,2,3,4$ 标记在矩阵的行和列上，其邻接矩阵为：
 ![图片](/uploads/2025-01/b5c27e.jpg)
 
 邻接矩阵 $M$ 是布尔矩阵，它的幂 $M^2=M^* M$ ，其中矩阵乘法按普通加和乘运算。设 $M^2=\left(m_{i j}^{(2)}\right),\left(m_{i j}^{(2)}\right)=\sum_{k=1}^n m_{i k} \cdot m_{k j}$ ，如图的 $M^2$ 为

$$
M^2=\left(\begin{array}{llll}
2 & 1 & 2 & 1 \\
1 & 3 & 1 & 2 \\
2 & 1 & 2 & 1 \\
1 & 2 & 1 & 3
\end{array}\right)
$$

$M^2$ 中的 $m_{i j}^{(2)}(i \neq j)$ 等于顶点 $v_i$ 和 $v_j$ 之间长度为 2 的路径的数目。 $m_{i i}^{(2)}$ 等于顶点 $v_i$ 的度数。显然 $M$ 是对称矩阵，$M^2$ 也是对称矩阵。

一般地，对于正整数 $k, M$ 的 $k$ 次幂为：$M^k=M^{k-1} * M$ ，它有如下特性。
定理 8.11 设 $M$ 是 $n$ 个顶点的简单图 $G$ 的邻接矩阵，$M^k=\left(m_{i j}^{(k)}\right)$ ，则 $M^k$ 中 $m_{i j}{ }^{(k)}$ 的等于顶点 $v_i$ 和 $v_j$ 之间长度为 $k$ 的路径数目。

证明：用数学归纳法，以 $k$ 为归纳变量。
当 $k=2$ 时，命题成立；

设 $k=l$ 时，命题成立；由 $M^{l+1}=M^* M^l$ ，故 $m_{i j}^{(l+1)}=\sum_{k=1}^n m_{i k} * m_{k j}^{(l)}$
根据邻接矩阵的定义 $m_{i k}$ 表示联接 $v_i$ 与 $v_k$ 的长度为 1 的路的数目，根据归纳假设 $m_{k j}{ }^{(l)}$ 表示联接 $v_k$ 与 $v_j$ 的长度为 $l$ 的路的数目。所以上式右边不为零的每一项表示 $v_i$ 经过一条边到 $v_k$ ，再由 $v_k$ 经过一条长度为 $l$ 的路到 $v_j$ 。所以对 $k$ 求和，即得 $m_{i j}^{(l+1)}$ 是所有从 $v_i$ 到 $v_j$ 的总长度为 $l+1$ 的路的数目，所以命题对 $l+1$ 成立。

上一篇：连通

下一篇：路径矩阵

本文对您是否有用？有用 (0) 无用 (0)