最后更新: 2025-01-22 09:17 查看: 33 次反馈刷题

路与回路

定义 8.14 （路径，链，路）图 $G$ 的一个有限点边交替序列 $\left(v_0, e_1, v_1, e_2, \cdots, e_m, v_m\right.$ ），使得对 $1 \leqslant i \leqslant m, e_i$ 的端点是 $v_{i-1}$ 和 $v_i$ ，称该序列为一条路径。边 $e_1, e_2, \cdots, e_m$ 互不相同的路径称为链，$m$ 被称为链的长度。顶点都不相同的链称为路，$m$ 被称为路的长度。 $v_0=v_m$ 的路径（或链）
 ![图片](/uploads/2025-01/a3f398.jpg)
图 8.8被称为闭路径（或闭链）。除首尾两点外其余顶点都不相同的闭链称为回路。长度为偶（奇）数的路或者回路称为偶（奇）路或偶（奇）回路。

例如在图 8.8 中有路径： $1 a 2 b 3 c 4 d 2 b 3$ ；链： $1 a 2 b 3 c 4 d 2$ ；路： $1 a 2 b 3 c 4$ ；回路： $1 a 2 b 3 c 4 e 1$ 。

有时点边交替序列可用边序列或点序列代替。
显然，一条路也是一条链，一条回路也是一条闭链，并且自环和两条多重边都自成一条回路。一条回路上每个顶点度数为 2, 一条路除了起点和终点外，每个顶点的度数也为 2 。

一个图在什么条件下有回路呢？有如下定理。
定理8．10 若图 $G$ 中每个顶点度数至少为 2 ，则 $G$ 包含一条回路。
证明：若图 $G$ 包含自环或多重边，则定理结论显然成立。若图 $G$ 是简单图，在图 $G$ 中任意选取一个顶点 $v_0$ ，从 $v_0$ 出发，构造一个顶点序列，从 $v_0$ 的相邻点中任取一个顶点 $v_1$ ，由于每个顶点度数至少为 $2, v_1$ 的相邻点除 $v_0$ 外还有另外顶点，因此必定可以任意选另一个顶点 $v_2$ 。同理，对于 $v_i(i \geqslant 2)$ 的相邻点除 $v_{i-1}$ 外必可选另一个顶点 $v_{i+1}$ 。因为 $G$ 中只有有限个顶点，所以必定选到一个顶点 $v_k$ ，它是第一个以前被选过的顶点，于是得到 $\left(v_0, v_1, \cdots, v_k, v_{k+1}, \cdots, v_k\right)$ ，其中从 $v_k$ 到 $v_k$ 这一顶点序列 $\left(v_k, v_{k+1}, \cdots, v_k\right)$ 是 $G$ 中的一条回路。

对于有向图，可以类似地定义有向路径，有向链和有向路。
定义8．15（有向路径，有向链，有向路）有向图 $G$ 的一个有限点弧交替序列（ $v_0, e_1, v_1$ ， $\left.e_2, \cdots, e_m, v_m\right)$ ，使得 $1 \leqslant i \leqslant m, e_i=\left(v_{i-1}, v_i\right)$ ，称该序列为一条有向路径。若 $e_1, e_2, \cdots, e_m$ 互不相同，称该序列为一条有向链；$m$ 被称为有向链的长度。顶点都不相同的有向链称为有向路；$m$被称为有向路的长度。

类似地可以定义有向闭路径，有向闭链和有向回路。

刷题

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

上一篇：有向图无向图

下一篇：连通

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