路与圈 | Codeboy's Blog

形式陈述

在本条的有限简单无向图约定下，路是顶点互异的序列

$$ v_0,v_1,\ldots,v_k $$

v_{0}, v_{1}, \dots, v_{k}

使每个 $v_{i-1}v_i$ $v_{i - 1} v_{i}$ 都是边；其长度为 $k$ $k$ 。圈是

$$ v_0,v_1,\ldots,v_{k-1},v_0, \qquad k\ge3, $$

v_{0}, v_{1}, \dots, v_{k - 1}, v_{0}, k \geq 3,

其中 $v_0,\ldots,v_{k-1}$ $v_{0}, \dots, v_{k - 1}$ 互异且相邻项成边。

允许重复顶点和边的序列称为游走；不重复边的游走称为迹。不同教材有时用 path 指游走，使用定理前应核对约定。

路是在图中不重复访问顶点的简单路线；圈是一条首尾闭合、内部不重复的路线。它们捕捉图结构中的可达性和循环性。

三角形构成长度 $3$ $3$ 的圈。序列 $u,v,u$ $u, v, u$ 在简单图中不是本条定义的圈，因为需要至少三个不同顶点；在多重图允许平行边时可能出现长度 $2$ $2$ 的圈，约定会改变。任意两个顶点间的最短游走必可删去重复段得到路。

路定义连通与距离，圈刻画树、二分性和反馈结构。很多图算法先生成一棵搜索树，再用非树边识别圈；有向图中的路和圈还必须保持边方向。

参考资料

Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，§1.3。
Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，Ch. 12。