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

路径矩阵

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

上一篇：邻接矩阵

下一篇：二分图

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