最后更新: 2025-01-21 17:08 查看: 299 次纠错评论(0) 课件开VIP

邻接矩阵

## 邻接矩阵
定义7－3．1 设 $G =< V , E >$ 是一个简单图，它有 n 个结点 $V =\{ V 1, V 2, \ldots, Vn \}$ ，则 n 阶方阵 $A ( G )=( aij ) n ^* n$ 称为 G 的邻接矩阵。其中

$$
a_{i j}=\left\{\begin{array}{rr}
1 & v_i \text { 邻接 } v_j \\
0 & v_i \text { 不邻接 } v_j \text { 或 } i=j
\end{array}\right.
$$

示例
 ![图片](/uploads/2025-01/1f9be1.jpg)
 
 －邻接矩阵 $A(G)$ 是 $n^* n$ 方阵，按照矩阵运算可以计算 $A^{(2)}(G)$ ， $A^{(3)}(G), \ldots, A^{(n)}(G)$ 。
－定理7－3．1 设 $A(G)$ 是图 $G$ 的邻接矩阵，则 $A^{(k)}(G)$ 中的 $i$ 行 j
列元素 $\left.a^{(k) j}\right)^{( }$等于 $G$ 中结点 $v i$ 到结点 $v j$ 的长度为 $k$ 的路的数目。
－$A^{(k)}(G)$ 中元素 $a^{(k) i i}$ 表示vi到vi长度为 $k$ 的回路的条数。
－本结论为有向图和无向图均成立
 ![图片](/uploads/2025-01/2f032e.jpg)
 
 
 ## 可达矩阵
 －定义7－3．2 设 $G =< V , E >$ 是一个简单有向图，$| V |= n$ ，若结点已编序，定义 $n$ 阶方阵 $P(G)=\left( pij _{ ij }\right) n ^* n$ 称为 G 的可达性矩阵。其中

$$
p_{i j}= \begin{cases}1 & v_i \text { 到 } v_j \text { 存在路 } \\ 0 & v_i \text { 到 } v_j \text { 没有路 }\end{cases}
$$

－用于判断图中任意两点间 $j$ 是否存在路
－从图G的邻接矩阵A可以得到可达性矩阵
$B=A+A^2+\ldots+A^n$ ，再把 $B$ 中所有不为零的元素换为1，即得到可达性矩阵 $P$
－可达性矩阵也可用warshall算法计算

例 设有向图G的邻接矩阵为

求 $G$ 的可达矩阵 $P$ 。

$$
A=\left(\begin{array}{llll}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 \\
1 & 0 & 0 & 0
\end{array}\right)
$$

解 根据矩阵乘法运算得

$$
A^2=\left(\begin{array}{llll}
0 & 0 & 1 & 1 \\
2 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 \\
0 & 1 & 0 & 0
\end{array}\right) \quad A^3=\left(\begin{array}{llll}
2 & 1 & 0 & 1 \\
1 & 2 & 1 & 1 \\
2 & 2 & 1 & 2 \\
0 & 0 & 1 & 1
\end{array}\right) \quad A^4=\left(\begin{array}{llll}
1 & 2 & 1 & 1 \\
2 & 2 & 2 & 3 \\
3 & 3 & 2 & 3 \\
2 & 1 & 0 & 1
\end{array}\right)
$$

根据矩阵的加法运算得

于是

$$
B_4=A+A^2+A^3+A^4=\left(\begin{array}{llll}
3 & 4 & 2 & 3 \\
5 & 5 & 4 & 6 \\
7 & 7 & 4 & 7 \\
3 & 2 & 1 & 2
\end{array}\right)
$$

$$
P=\left(\begin{array}{llll}
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1
\end{array}\right)
$$

由此可知，图 $G$ 中任两结点均是可达的，且任一结点均有回路，因而 $G$ 是连通图。

## 关联矩阵
－定义7－3．3 给定无向图G $=< V , E >$ ，令 $v 1, v 2, \ldots, Vp$ 和 $e 1, e 2, \ldots, e q$ 分别记为 $M(G)$ 的结点和边，则矩阵 $M(G)=\left(m_{i j}\right)$ 定义如下，称 $M(G)$ 为完全关联矩阵。

$$
m_{i j}=\left\{\begin{array}{cc}
1 & v_i \text { 关联 } e_j \\
0 & v_i \text { 不关联 } e_j
\end{array}\right.
$$

![图片](/uploads/2025-01/c4f48d.jpg)
 
 －定义7－3．4 给定简单有向图G＝＜V，E＞，令 $V 1, v 2, \ldots, Vp$ 和 $e 1, e 2, \ldots, e q$ 分别记为 $M(G)$ 的结点和边，则矩阵 $M(G)=\left(m_{i j}\right)$ 定义如下，称 $M(G)$ 为完全关联矩阵。

$$
m_{i j}=\left\{\begin{array}{cc}
1 & v_i \text { 是 } e_j \text { 的起点 } \\
-1 & v_i \text { 是 } e_j \text { 的终点 } \\
0 & v_i \text { 不关联 }{ }_j
\end{array}\right.
$$

![图片](/uploads/2025-01/a28670.jpg)

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：强连通图与单向连通图的判定定理

下一篇：欧拉图

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