最后更新: 2024-04-06 18:30 查看: 117 次反馈刷题

图的矩阵表示

## 图的矩阵表示
图的图解表示对于形象直观地分析给定图的某些特性有时是有用的, 但当图的结点数和边数较大时, 这种办法是不实际的。图的矩阵表示是另一个方便的方法, 它使图的有关信息能以矩阵的形式在计算机中储存起来并加以运算, 可揭示图的许多重要性质。计算机能识别图的矩阵表示, 这便于利用计算机来研究有关图的算法。但图的许多有强烈的直观背景的性质, 在用矩阵表示时会遇到困难。例如关于平面性的问题就是如此。

定义 12 设 $G=<V, E>$ 为无向图, $V=\left\{v_1, v_2, \Lambda, v_n\right\}, E=\left\{e_1, e_2, \Lambda, e_m\right\}$ 。令 $m_{i j}$ 为 $v_i$和 $\boldsymbol{e}_j$ 的关联次数, 则称 $M=\left[m_{i j}\right]_{n \times m}$ 为 $G$ 的关联矩阵。

图的最本质特征是边与结点的关联性质, 关联矩阵表示图的边与结点的关联性质, 它完整地体现了图的特征。关于关联矩阵有如下结论: $M$ 中每列元素之和等于 2; $M$ 的第 $i$ 行元素之和为 $\operatorname{deg}\left(v_i\right)$; $M$ 的全部元素之和为 $\sum_{i=1}^n \operatorname{deg}\left(v_i\right)=2 m$; 若 $M$ 的第 $i$ 行元素全为 0 , 则 $v_i$为孤立点。
定义 13 设 $G=<V, E>$ 为无向图, $V=\left\{v_1, v_2, \Lambda, v_n\right\}$ 。令 $a_{i j}$ 为以 $v_i$ 和 $v_j$ 为两个端点
的边数, 则称 $A=\left[a_{i j}\right]_{n \times n}$ 为 $G$ 的邻接矩阵。
邻接矩阵体现图中结点之间的邻接关系, 它是一个对称矩阵。
定义 14 设 $D=<V, E>$ 为无环有向图, $V=\left\{v_1, v_2, \Lambda, v_n\right\}, E=\left\{e_1, e_2, \Lambda, e_m\right\}$ 。令
有向图的关联矩阵有如下结论: $M$ 中每列元素中 1 和-1 各有一个; $M$ 的第 $i$ 行元素绝对值之和为 $\operatorname{deg}\left(v_i\right)$, 其中 1 的个数为 $\operatorname{deg}^{+}\left(v_i\right),-1$ 的个数为 $\operatorname{deg}^{-}\left(v_i\right)$; $M$ 的全部元素之和为 0 。

定义 15 设 $D=<V, E>$ 为有向图, $V=\left\{v_1, v_2, \Lambda, v_n\right\}$ 。令 $a_{i j}$ 是以 $v_i$ 为起点, $v_j$ 为终点的边数, 则称 $A=\left[a_{i j}\right]_{n \times n}$ 为 $D$ 的邻接矩阵。

任一图的关联矩阵和邻接矩阵都与其图解一一对应。显然, 若两个图的邻接矩阵相同,或可通过交换某些行和相应的列而相同, 则这两个图同构。邻接矩阵最大的作用在于判定图的连通性。通过幂运算可得 $A^l, A^l$ 中每个元素的图论意义见定理 10 。

定理 10 若图有结点集 $\left\{v_1, v_2, \Lambda, v_n\right\}$ 和邻接矩阵 $A$, 则 $A^l$ 中 $(i, j)$ 元素 $a_{i j}^{(l)}$ 是从 $v_i$到 $v_j$ 的长度为 $l$ 的通路数目。若 $i=j$, 则 $a_{i i}^{(l)}$ 是 $v_i$ 到自身的长度为 $l$ 的回路数目。
推论 $1 d\left(v_i, v_{\mathrm{j}}\right)$ 是使 $A^l$ 的 $(i, j)$ 元素 $a_{i j}^{(l)}$ 非零的最小整数 $l(i \neq j)$ 。
推论 2 令 $B_r=A+A^2+\Lambda+A^r$, 则 $B_r$ 的 $(i, j)$ 元素是从 $v_i$ 到 $v_j$ 的长度小于等于 $r$ 的通路数目。若 $B_n$ 的 $(i, j)$ 元素为 0 , 则不存在从 $v_i$ 到 $v_j$ 的通路, $v_i$ 和 $v_j$ 属于不同的分支。所以, 图是连通的或强连通的 $\Leftrightarrow B_n$ 除主对角线外全是非零元素。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：连通性

下一篇：最短路径问题

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