通路与回路

给定 $G=<V,E>$, $G$ 中顶点与边的交替序列 $\Gamma =v_0{e}_1{v}_1{e}_2...e_l{v}_l$, 其中 $v_{i-1},v_i$ 为 $e_i$ 的端点, $\Gamma$ 为通路.

若 $v_0=v_l$, 则 $\Gamma$ 为回路, $l$ 为回路长度.

简单通路与回路

所有边各异的通路与回路称为简单通路与简单回路.

指向原始笔记的链接

路径

$\Gamma$ 中除首末点外所有顶点各异且所有边各异, 则称为初级通路或路径.

指向原始笔记的链接

圈

$\Gamma$ 中 $v_0=v_l$, 其他所有顶点各异且所有边各异, 则称为初级回路或圈.

指向原始笔记的链接

有边重复出现的通路为复杂通路.

定理 在 $n$ 阶图 $G$ 中, 若 $v_i,v_j$ 存在通路, 则从 $v_i$ 到 $v_j$ 存在长度小于等于 $n-1$ 的通路. (初级通路)

定理 在 $n$ 阶图 $G$ 中, 若存在 $v_i$ 到自身的回路, 则一定存在 $v_i$ 到自身长度小于或等于 $n$ 的回路. (初级回路)