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

路径矩阵

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

$$
p_{i j}= \begin{cases}1 & \text { 若 } v_i \text { 与 } v_j \text { 之间至少存在一条路径 } \\ 0 & \text { 若 } v_i \text { 与 } v_j \text { 之间不存在路径 }\end{cases}
$$

称 $P(G)$ 为图 $G$ 的路径矩阵。
$P(G)$ 是布尔矩阵，具有如下性质。
$G$ 是连通图当且仅当 $P(G)$ 中元素全为 1 。

可以证明：对 $n$ 个顶点的 $G$ ，若从 $v_i$ 到 $v_j$ 之间存在一条路径，则从 $v_i$ 到 $v_j$ 必有一条长度不超过 $n-1$ 的路径（证明留作习题）。同理，若 $G$ 中有一条闭路径，则必有一条长度不超过 $n$ 的闭路径。利用这一特性，我们可以从图 $G$ 的邻接矩阵 $M(G)$ 来求得路径矩阵 $P(G)$ 。为此，只要设 $B_n=M+M^2+\cdots+M^n$ ，从 $B_n$ 中将非零元素改为 1 ，零元素不变，便得到路径矩阵 $P(G)$ 。由于 $P(G)$是一个布尔矩阵，其中 $p_{i j}=1$ 表示 $v_i$ 到 $v_j$ 之间存在路径，但不需要知道有多少条路径。我们所关心的是两个顶点之间是否存在路径，为此我们将 $M^k(1 \leqslant k \leqslant n)$ 改为 $M^{(k)}(1 \leq k \leq n)$ ，得到 $P=M^{(1)} v$ $M^{(2)} \vee \cdots \vee M^{(n)}$ ，其中 $M^{(1)}=M, M$ 是布尔矩阵，$\vee$ 是逻辑运算，$M^{(k)}$ 是 $M$ 在布尔矩阵意义下的 $k$ 次幂，也是布尔矩阵。

在有向图中经常用到邻接矩阵和路径矩阵，其性质类似于无向图。
有向图实质上就是顶点集上二元关系的关系图，因而我们可以用关系矩阵也就是有向图的矩阵来表示它。

定义 8.21 （邻接矩阵）设 $G$ 是 $n$ 个顶点，无多重边的有向图。 $n \times n$ 矩阵 $M=\left(m_{i j}\right)$（依顶点次序 $v_1, \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$ 的邻接矩阵。
类似定理 8.11 有如下定理。
定理 8.12 设 $M$ 是 $n$ 个顶点的简单有向图 $G$ 的邻接矩阵，$M^k=\left(m_{i j}{ }^{(k)}\right)$ 等于从顶点 $v_i$ 到 $v_j$ 之间长度为 $k$ 的有向路径数目。

证明类似定理 8.11 的证明，此处从略。

定义8．22（路径矩阵）设有向图 $G$ 有 $n$ 个顶点，无多重弧。 $n \times n$ 矩阵 $P=\left(p_{i j}\right)$ ，也记为 $P(G)$ ，其中

$$
p_{i j}= \begin{cases}1 & \text { 若从 } v_i \text { 到 } v_j \text { 至少存在一条有向路径 } \\ 0 & \text { 若从 } v_i \text { 到 }_{v_j} \text { 不存在有向路径 }\end{cases}$$

称 $P(G)$ 为有向图 $G$ 的路径矩阵，或可达性矩阵。
$P(G)$ 具有如下性质：有向图 $G$ 是强连通图当且仅当 $P(G)$ 中元素全为 1 。
完全类似于无向图的情况，我们可以从有向图 $G$ 的邻接矩阵 $M(G)$ 来求得路径矩阵 $P(G)$ 。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：邻接矩阵

下一篇：二分图

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