最后更新: 2025-01-22 09:19 查看: 159 次纠错评论(0) 课件开VIP

邻接矩阵

定义 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$ 成立。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：连通

下一篇：路径矩阵

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