[Def]关于图(graph)的基本概念---路径(path),道路(trail),通路(walk)
所谓的路径(path)是指一个图 $P$, 满足
\[
V(P)=\{x_0,x_1,\ldots,x_{\ell}\},\quad E(P)=\{x_0x_1, x_1x_2,\ldots,x_{\ell-1}x_{\ell}\}.
\]
这里 $x_i\neq x_j$, $\forall\ i\neq j$.
这条路径 $P$ 通常记为 $x_0x_1x_2\ldots x_{\ell}$. 顶点 $x_0$ 和 $x_{\ell}$ 是路径 $P$ 的两个端点. 而 $\ell=e(P)$ 是路径 $P$ 的长度.
我们称 $P$ 是从 $x_0$ 到 $x_{\ell}$ 的一条路径(path), 或简记为 $x_0-x_{\ell}$ path. 当然 $P$ 也是一条从 $x_{\ell}$ 到 $x_0$ 的路径, 或简记为 $x_{\ell}-x_0$ path.
有时, 我们将强调 $P$ 是从 $x_0$ 到 $x_{\ell}$ 的, 并且称 $x_0$ 为起点（或始点）(initial vertex), $x_{\ell}$ 为终点(terminal vertex).
以 $x$ 为起点的道路称为 $x$-path.
大多数路径可以视为某给定图 $G$ 的一个子图. 图 $G$ 的一条通路(walk)是指一条由顶点与边组成的交错序列:
\[
x_0,\alpha_1,x_1,\alpha_2,x_2,\ldots,\alpha_{\ell},x_{\ell}.
\]
其中 $\alpha_i=x_{i-1}x_i$, $i=1,2,\ldots,\ell$. 这里顶点和边都可以重复.
$\ell$ 称为这条通路(walk)的长度.
如果通路(walk)中限定边不能重复, 顶点可以重复, 则称这条通路为道路(trail).
因此, 所谓的路径, 实际上就是顶点和边均不重复的通路.
若道路(trail)的两端点重合（也即是一条闭合道路 a closed trail），则称其为一个回路(circuit).
设 $W=x_0x_1\ldots x_{\ell}$ 是一条通路(walk), 满足 $\ell\geqslant 3$, $x_0=x_{\ell}$. 并且诸 $x_i(0 < i < \ell)$ 互不相同, 也不同于 $x_0$, 则称 $W$ 是一个 圈(cycle).
为简单起见, 这个 cycle 记为 $x_1x_2\ldots x_{\ell}$. 注意到这里的记号不同于之前的, 这里 $x_1x_{\ell}$ 也是该 cycle 的一条边. 进一步的, $x_1x_2\ldots x_{\ell}$, $x_{\ell}x_{\ell-1}\ldots x_1$, $x_2x_3\ldots x_{\ell}x_1$, $x_ix_{i-1}\ldots x_1x_{\ell}x_{\ell-1}\ldots x_{i+1}$ 都指的是同一个 cycle.
记号:
| 符号 | 涵义 |
|---|---|
| $P^{\ell}$ | 长度为 $\ell$ 的一条路径(path) |
| $C^{\ell}$ | 长度为 $\ell$ 的一个圈 (cycle) |
我们称 $C^3$ 是一个三角形(triangle), $C^4$ 是一个四边形(quadrilateral), $C^5$ 是一个五边形(pentagon), 等等.
一个 cycle 被称为是 even (或 odd) 的, 如果它的长度是 even (或 odd) 的.
给定顶点 $x,y$, 它们之间的距离 $d(x,y)$ 指连接这两点的所有路径中长度最短的那条路径的长度.
\[
d(x,y)=\min\{\text{length of } x-y\ \text{path}\}
\]
若 $x,y$ 之间不存在 $x-y$ path, 则令 $d(x,y)=\infty$.
一个图称为是连通的(connected), 如果对于任意两个不同点组成的点对 $\{x,y\}$, 都存在一条从 $x$ 到 $y$ 的路径(path).
设无向图 $G(V,E)$ 是连通的, 设边集 $E_1\subset E$. 在图 $G$ 中删除 $E_1$ 中所有的边后得到的子图是不连通的, 而删除了 $E_1$ 的任一真子集后得到的子图是连通图, 则称 $E_1$ 是 $G$ 的一个割边集.
若割边集仅由一条边组成, 则称这条边为割边, 或桥(bridge).
References:
Béla Bollobas, Graph Theory, An introductory course. GTM 63.