5.8.2 无向图的遍历

5.8.2.1 边序列或路

1. 边序列或路

在一个无向图 $G=\left(V,E\right)$ 中,每个 $E$ 的元素的序列

$$F=\left(\left\{v_1,v_2\right\},\left\{v_2,v_3\right\},\cdots ,\left\{v_s,v_{s+1}\right\}\right)$$

称作长 $s$ 的边序列.

如果 $v_1=v_{s+1}$ ,那么序列称为一个圈,不然它是一个开边序列. 一个边序列称作路,当且仅当 $v_1,v_2,\cdots ,v_s$ 是两两不同的顶点. 闭路是指一个环道. 迹是指一个没有重复边的边序列.

在图 5.38 中, $F_1=\left(\{1,2\},\{2,3\},\{3,5\},\{5,2\},\{2,4\}\right)$ 是一个长为 5 的边序列, $F_2=\left(\{1,2\},\{2,3\},\{3,4\},\{4,2\},\{2,1\}\right)$ 是一个长为 5 的圈, $F_3=(\{2,3\},\{3,5\}$ , $\{5,2\},\{2,1\})$ 是一条路, $F_4=\left(\{1,2\},\{2,3\},\{3,4\}\right)$ 是一条路. $F_5=(\{1,2\},\{2,5\}$ , $\{5,1\})$ 给出一个基本圈.

2. 连通图、分量

如果在图 $G$ 中,每对不同的顶点 $v,w$ 之间至少存在一条路,那么 $G$ 称为连通的. 如果图 $G$ 不连通,那么它可以分解为分量,即分解为具有极大个数顶点的诱导连通子图.

3. 顶点间的距离

无向图中两个顶点 $v,w$ 间的距离 $\delta \left(v,w\right)$ 是指具有极小个数的连接 $v$ 和 $w$ 的边的路的长. 如果这样的路不存在,那么令 $\delta \left(v,w\right)=\mathrm{\infty }$ .

4. 最短路问题

设 $G=\left(V,E,f\right)$ 是一个加权简单图,并且对于每个 $e\in E,f\left(e\right)>0$ . 对于 $G$ 的两个顶点 $v,w$ 确定从 $v$ 到 $w$ 的最短路,即一条从 $v$ 到 $w$ 的路,其中边和弧的权之和分别极小.

有一个解决此问题的丹齐格有效算法, 它是对有向图叙述的, 并且也可类似地应用于无向图 (参见第 551 页 5.8.6).

每个图 $G=\left(V,E,f\right)$ ,其中 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ ,有一个(n, n)型的距离矩阵$D$ :

$$\begin{array}{}\text{(5.320)}& \mathbf{D}=\left(d_{ij}\right),\text{ 其中 }{d}_{ij}=\delta \left(v_i,v_j\right)\left(i,j=1,2,\cdots ,n\right).\end{array}$$

在每条边的权都为 1 的情形,即 $v$ 和 $w$ 的距离等于在图中从 $v$ 到达 $w$ 所需要的边的极小个数,那么可以应用关联矩阵确定两个顶点间的距离: 设 $v_1,v_2,\cdots ,v_n$ 是 $G$ 的顶点. $G$ 的关联矩阵是 $\mathbf{A}=\left(a_{ij}\right)$ ,并且将关联矩阵关于通常矩阵乘法 (参见第 365 页 4.1.4,5.) 的幂表示为 ${\mathbf{A}}^m=\left(a_{ij}^m\right),m\in \mathbb{N}$ .

存在从顶点 $v_i$ 到顶点 $v_j\left(i\ne j\right)$ 的长为 $k$ 的最短路,当且仅当

$$\begin{array}{}\text{(5.321)}& a_{ij}^k\ne 0\text{,并且 }{a}_{ij}^s=0\left(s=1,2,\cdots ,k-1\right).\end{array}$$

图 5.39 中给出的加权图有距离矩阵 $\mathbf{D}$ (在图的旁边).

图 5.40 中给出的图有关联矩阵 $\mathbf{A}$ (在图的旁边),并且当 $m=2$ 或 $m=3$ 时得到矩阵 ${\mathbf{A}}^2$ 和 ${\mathbf{A}}^3$ . 长为 2 的最短路连接顶点 1 和3,1和4,1和5,2和6,3和 4, 3 和 5,4 和 5 . 此外, 顶点 1 和 6,3 和 6, 以及最后, 4 和 6 之间的最短路的长为 3 .

$$\mathbf{D}=\left(\begin{array}{llllll}0& 2& 3& 5& 6& \mathrm{\infty }\\ 2& 0& 1& 3& 4& \mathrm{\infty }\\ 3& 1& 0& 2& 3& \mathrm{\infty }\\ 5& 3& 2& 0& 1& \mathrm{\infty }\\ 6& 4& 3& 1& 0& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)$$

$${\mathbf{A}}^2=\left(\begin{array}{llllll}1& 1& 1& 1& 1& 0\\ 1& 5& 1& 1& 1& 1\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 1& 1& 2& 0\\ 0& 1& 0& 0& 0& 1\end{array}\right),{\mathbf{A}}^3=\left(\begin{array}{llllll}1& 5& 1& 1& 1& 1\\ 5& 9& 5& 5& 6& 1\\ 1& 5& 1& 1& 1& 1\\ 1& 5& 1& 1& 1& 1\\ 1& 6& 1& 1& 1& 2\\ 1& 1& 1& 1& 2& 0\end{array}\right).$$

5.8.2.2 欧拉迹

1. 欧拉迹、欧拉图

含有图 $G$ 的每条边的迹称为 $G$ 的开或闭的欧拉迹.

含有闭欧拉迹的连通图是一个欧拉图.

图 $G_1$ (图 5.41) 没有欧拉迹. 图 $G_2$ (图 5.42) 有一个欧拉迹,但它不是欧拉图. 图 $G_3$ (图 5.43) 有一个闭欧拉迹,但它不是欧拉图. 图 $G_4$ (图 5.44) 是一个欧拉图.

2. 欧拉-希尔霍尔策 (Euler-Hierholzer) 定理

有限连通图是欧拉图, 当且仅当它的所有顶点的次数都是正偶数.

3. 闭欧拉迹的构造

如果 $G$ 是一个欧拉图,那么我们可以选取 $G$ 的任意一个顶点 $v_1$ ,并且由 $v_1$ 开始遍历 $G$ 直到它不再可能继续下去,这就构造一条迹 $F_1$ . 如果 $F_1$ 还没有含 $G$ 的所有边,那么我们构造另外一条含有不在 $F_1$ 中的边的路 $F_2$ ,但它从某过顶点 $v_2\in F_1$ 开始并且直到它不再可能继续下去. 然后我们应用 $F_1$ 和 $F_2$ 组成 $G$ 中一个闭迹: 从 $v_1$ 开始遍历 $F_1$ 直到到达 $v_2$ ,然后继续遍历 $F_2$ ,并且最后在以前没有用过的 $F_1$ 的边上结束. 重复这个方法在有限步骤内可得到一个闭欧拉迹.

4. 开欧拉迹

图 $G$ 中存在开欧拉迹,当且仅当 $G$ 中恰存在两个有奇次数的顶点. 图 5.45 给出一个图, 它没有闭欧拉迹, 但有一个开欧拉迹. 各边是相对于欧拉迹相继顺序标号的. 图 5.46 中有一个具有欧拉迹的图.

5. 中国邮递员问题

问题是: 邮递员必须至少一次通过他的服务区的所有街道且回到出发地, 并且要使路程尽可能短; 这个问题可以用图论术语叙述如下: 设 $G=\left(V,E,f\right)$ 是一个加权图,并且对于每条边 $e\in E,f\left(e\right)\ge 0$ . 确定边序列,使得它具有极小总长

$$\begin{array}{}\text{(5.322)}& L=\sum _{e\in F}f\left(e\right).\end{array}$$

这个问题的命名源于中国数学家管梅谷, 他首先研究此问题. 为解此问题要区分两种情形:

(1) $G$ 是欧拉图,那么每个闭欧拉迹是最优的;

(2) $G$ 没有闭欧拉迹.

解这个问题的一个有效算法是埃德蒙兹 (Edmonds) 和约翰逊 (Johnson) 给出的 (见 [5.49]).

5.8.2.3 哈密顿圈

1. 哈密顿圈

哈密顿圈是覆盖图中所有顶点的基本圈.

在图 5.47 中, 粗线条表示一个哈密顿圈.

在面为五边形的十二面体的图中构造哈密顿圈游戏的想法可以追溯到哈密顿爵士.

注 刻画有哈密顿圈的图的问题导致一个经典的 NP 完全问题. 因此在此不能给出确定哈密顿圈的有效算法.

2. 狄拉克定理

如果简单图 $G=\left(V,E\right)$ 至少有 3 个顶点,并且对于 $G$ 的每个顶点 $v,d_G\left(v\right)\ge$ $\left|V\right|/2$ ,那么 $G$ 有哈密顿圈. 这是哈密顿圈存在的一个充分而非必要的条件. 下面具有更一般的假设的定理也是哈密顿圈存在的一个充分而非必要的条件.

图 5.48 给出一个图, 它有一个哈密顿圈, 但并不满足下述奥尔定理的假设.

3. 奥尔 (Ore) 定理

如果简单图 $G=\left(V,E\right)$ 至少有 3 个顶点,并且对于每对非邻接的顶点 $v$ 和 $w,d_G\left(v\right)+d_G\left(w\right)\ge \left|V\right|$ ,那么 $G$ 有哈密顿圈.

4. 波萨 (Posa) 定理

设简单图 $G=\left(V,E\right)$ 至少有 3 个顶点. 如果满足下列条件:

(1) 对于 $1\le k\le \left(\left|V\right|-1\right)/2$ ,次数不超过 $k$ 的顶点的个数小于 $k$ ;

(2) 若 $\left|V\right|$ 是奇数,则次数不超过 $\left(\left|V\right|-1\right)/2$ 的顶点的个数小于或等于 $(\left|V\right|-$ $1)/2$ ,那么 $G$ 有哈密顿圈.