通路与回路

基本定义

设 G 为无向标定图，G 中顶点与边的交替序列 $Γ = v_{0} e_{1} v_{1} e_{2} \dots v_{l - 1} e_{l} v_{l}$ 称为 $v_{0}$ 到 $v_{l}$ 的通路，其中 $v_{i - 1}$ 与 $v_{i}$ 为 $e_{i}$ 的端点。 $v_{0}$ 、 $v_{l}$ 分别称为始点与终点，边的条数称为通路的长度。若 $v_{0} = v_{l}$ ，则称通路为回路。

表示方法

只用边的序列表示： $e_{1}, e_{2}, \dots, e_{l}$
在简单图中只用顶点序列： $v_{0}, v_{1}, \dots, v_{l}$
混合表示法：在非简单标定图中，可在顶点序列中加入边以区分平行边或环。

重要定理

定理：在 n阶图 G中，若从顶点 u到 v（ $u \neq = v$ ）存在通路，则从 u到 v存在长度小于等于 $n - 1$ 的通路。

推论：在 n阶图 G中，若从 u到 v（ $u \neq = v$ ）存在通路，则一定存在长度小于等于 $n - 1$ 的初级通路（路径）。

定理：在 n 阶图 G 中，若存在 v 到自身的回路，则一定存在 v 到自身长度小于等于 n 的回路。

推论：在 n 阶图 G 中，若存在 v 到自身的简单回路，则一定存在 v 到自身长度小于等于 n 的初级回路。

图的矩阵表示

关联矩阵

无向图的关联矩阵 $M (G)$ 是 $n \times m$ 矩阵，其中 $m_{ij}$ 为顶点 $v_{i}$ 与边 $e_{j}$ 的关联次数。

有向图（无环）的关联矩阵 $M (D)$ 中， $m_{ij} = 1$ 若 $v_{i}$ 为 $e_{j}$ 的始点， $- 1$ 若为终点， $0$ 若不关联。

邻接矩阵

有向图 $D = ⟨ V, E ⟩$ 的邻接矩阵 $A = (a_{ij})_{n \times n}$ ，其中 $a_{ij}$ 为顶点 $v_{i}$ 邻接到 $v_{j}$ 的边的条数。

性质：A 的 l 次幂 $A^{l}$ 中元素 $a_{ij}^{(l)}$ 为 D 中 $v_{i}$ 到 $v_{j}$ 长度为 l 的通路数，其中 $a_{ii}^{(l)}$ 为 $v_{i}$ 到自身长度为 l 的回路数。

可达矩阵

有向图 D 的可达矩阵 $P = (p_{ij})_{n \times n}$ ，其中 $p_{ij} = 1$ 若 $v_{i}$ 可达 $v_{j}$ ，否则为 0。

链接到

上一个知识点：3.1 图的基本概念
下一个知识点：3.3 连通性

📚 Study Notes

📂 笔记目录

3.2 通路与回路