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

通路与回路

## 结点、边的删除、边的收缩
设图 $G=<V, E>$ 。设 $v \in V, G-v$ 或 $G-\{v\}$ 表示从 $G$ 中删除 $v$ 及所关联的边; 设 $V^{\prime} \subset V$, $G-V^{\prime}$ 表示从 $G$ 中删除 $V^{\prime}$ 中各结点及所关联的边; 设 $e \in E, G-e$ 或 $G-\{e\}$ 表示从 $G$ 中删除 $e$; 设 $E^{\prime} \subset E, G-E^{\prime}$ 表示从 $G$ 中删除 $E^{\prime}$ 中各边; 设 $e \in E, G-e$ 表示从 $G$ 中删除 $e$,并将 $e=(u, v)$ 的端点 $u$ 和 $v$ 变为一个结点 $w$, 使 $w$ 关联除 $e$ 外的 $u$ 和 $v$ 所关联的所有边; $G \mathrm{Y}(u, v)$ 或 $G+(u, v)$ 表示在 $G$ 中结点 $u$ 和 $v$ 之间加边 $(u, v)$ 。
## 通路与回路
定义 6 设图 $G=\left\langle V, E>, G\right.$ 中结点和边的交替序列 $P=v_0 e_1 v_1 e_2 v_2 \Lambda v_1$, 其中 $e_{\mathrm{i}}$ 与 $v_{\mathrm{i}-1}$和 $v_i$ 关联, 即 $e_i=\left(v_{i-1}, v_i\right)$, 或 $e_i=<v_{i-1}, v_i>, 1 \leq i \leq l, P$ 称为 $v_0$ 到 $v_l$ 的通路。 $v_0$ 和 $v_1$ 分别称为通路的起点和终点, 边的数目称为通路长度。若 $v_0 \neq v_l$, 则称 $\mathrm{P}$ 为开 (通) 路; 若 $v_0=v_l$, 则称 $P$ 为闭 (通) 路或回路; 所有边均不同的通路称为简单通路或迹; 所有边均不同的回路称为简单回路或闭迹; 所有结点均不同（从而所有边也均不同）的通路称为基本通路 (或初等通路、初级通路或路径); 除起点和终点外, 所有结点和所有边均不同的回路称为基本回路（或初等回路、初级回路或圈)。

显然, 基本通路必为简单通路, 基本回路必为简单回路; 反之, 则不然。在不引起误解的情况下, 可以只用边序列 $e_1, e_2, \Lambda, e_l$ 表示通路或回路; 在简单图中, 也可只用结点序列 $v_1, v_2, \Lambda, v_l$ 表示通路或回路。若 $G$ 中存在从 $u$ 到 $v$ 的通路, 则从 $u$ 到 $v$ 长度最短的通路称为 $u$ 到 $v$ 的短程线, 其长度称为 $u$ 和 $v$ 之间的距离, 记作 $d(u, v)$ 。若 $G$ 中不存在从 $u$ 到 $v$的通路, 则规定 $d(u, v)=\infty$ 。距离满足如下性质: $d(u, v) \geq 0 ; d(u, u)=0$; $d(u, v)+d(v, w) \geq d(u, w)$ （无向图的距离还满足对称性, 即 $d(u, v)=d(v, u)$ )。
定理 2 图 $G$ 为二部图的充要条件是 $G$ 中所有基本回路长都是偶数。
定理 3 在 $n$ 阶图 $G$ 中, 若存在从 $u$ 到 $v$ 的开通路, 则必存在从 $u$ 到 $v$ 长度小于等于 $n-1$ 的基本通路。

定理 4 在 $n$ 阶图 $G$ 中, 若存在 $v$ 到自身的简单回路, 则必存在 $v$ 到自身长度小于等于 $n$ 的基本回路。

刷题

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

上一篇：图的重构与运算

下一篇：连通性

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