11.5 欧拉问题与哈密顿问题

第 11.3 与 11.4 节按照边数或总权重优化了路线或连接骨架。本节改问另一类问题：能否用一次行程恰好覆盖图中每个要求对象一次？

这个问题有两个本质不同的版本。欧拉路线覆盖所有边，哈密顿路线访问所有顶点。始终分清这两个对象，才能避免常见混淆。

欧拉迹覆盖每条边

欧拉迹是恰好使用图中每条边一次的迹。回忆一下：迹可以重复顶点，但不能重复边。

回到起点的欧拉迹称为欧拉回路，也就是恰好使用每条边一次的闭迹。

含有欧拉回路的连通图称为欧拉图。如果图中有孤立顶点，它们不会参与任何边路线；因此更精确地说，所有非孤立顶点必须属于同一个连通分量。

这一问题的经典来源是哥尼斯堡七桥问题：把每块陆地作为顶点，把每座桥作为边。每座桥恰好走一次是在寻找欧拉迹，而不是最短路径。

度的奇偶性决定欧拉路线

能被 $2$ 整除的整数称为偶数，否则称为奇数。在无向图中，顶点度的奇偶性决定欧拉路线是否存在。

设想在迹的中途到达某个顶点：一条尚未使用的关联边把我们带进来，还必须通过另一条未使用边离开。该顶点上被使用的边会按照“进入—离开”两两配对。

在欧拉回路中，起点的第一次离开与最终返回也形成一对，因此每个顶点的度都是偶数。

在不闭合的欧拉迹中，起点多一次离开，终点多一次进入。恰好这两个顶点具有奇数度，其余顶点都是偶数度。

由此得到完整的无向图判定条件：

• 当且仅当所有非孤立顶点位于同一连通分量，且每个顶点度数都是偶数时，存在欧拉回路；

• 当且仅当所有非孤立顶点位于同一连通分量，且恰好有两个奇数度顶点时，存在不闭合的欧拉迹；

• 若奇数度顶点多于两个，则不存在欧拉迹。

握手定理已经保证奇数度顶点数量为偶数，所以可能的数量从 $0,2,4,6,\ldots$ 开始。

构造欧拉路线

度数判定能告诉我们路线是否存在，但还要真正把路线构造出来。Hierholzer 算法按以下步骤工作：

1. 若有两个奇数度顶点，就从其中任意一个开始；否则从任一非孤立顶点开始；

2. 沿尚未使用的边继续前进，直到当前顶点没有未使用的关联边；

3. 若所有边都已经使用，则停止；

4. 否则，在当前路线中找到一个仍与未使用边关联的顶点；

5. 从该顶点构造另一条只使用未用边的闭迹，再把它拼接进原路线。

为什么尚未完成的回路不会困在另一个偶数度顶点？每次进入都会使用一条边，剩余的未使用关联边仍成对出现。只有允许的奇数度端点可能拥有无法配对的一次进入或离开。

考虑边集

所有度数都是偶数：$\deg(C)=4$，其余顶点的度都是 $2$。一条欧拉回路为

顶点 $C$ 出现两次是允许的，而每条边恰好出现一次。

亲手规划一次连续配送，让快递员恰好经过每条街道一次。走过的街道会立即封闭，顶点度闸门会预测合法起点；若局部选择把路线困住，还可以使用路线拼接工具恢复。

哈密顿路径覆盖每个顶点

哈密顿路径恰好访问每个顶点一次。哈密顿环恰好访问每个顶点一次并回到起点；只允许起点作为终点再出现一次。

哈密顿路线不必使用每条边。只要访问序列中相邻位置的顶点之间有边，未使用的边并不重要。

对比两类目标：

当 $n\ge3$ 时，含 $n$ 个顶点的环图既有欧拉回路，也有哈密顿环。其他图可能只拥有其中一种。至少有三片叶子的星形图虽然可以反复经过中心来覆盖多条边，却没有哈密顿路径：从一片叶子经过中心到达第二片叶子后，若不重复中心，就无法再到达其他叶子。

必要条件不是完整判定

下面的观察可以证明某张图不可能有哈密顿环：

• 哈密顿环经过每个顶点时会使用两条关联的环边，所以度小于 $2$ 的顶点会排除哈密顿环；

• 从哈密顿环删除任一顶点后，剩余路线仍是一条路径，因此删除一个顶点不能把其余图分成多个非空部分；

• 桥不可能位于任何环上，所以一张图若含有桥，就不可能存在同时访问桥两侧顶点的哈密顿环。

这些都是必要条件：拥有哈密顿环的图一定满足它们，但满足它们并不保证一定存在哈密顿环。

这与欧拉问题形成鲜明对比：欧拉度数条件既必要又充分。

用回溯搜索哈密顿路线

对规模较小的图，可以系统搜索哈密顿路径：

1. 选择起点并标记为已使用；

2. 把当前路径延伸到一个相邻且未使用的顶点；

3. 若所有顶点都已使用，就找到了一条哈密顿路径；

4. 若过早出现没有未使用邻居的情况，就撤销最近一次选择；

5. 尝试另一个未使用邻居。

撤销选择并尝试另一分支的过程称为回溯，它与第 7 章的递归树相呼应。

若寻找哈密顿环，最后一个顶点还必须与起点相邻。当一条部分路径让某个未访问顶点失去所有可用连接，或者让剩余未访问顶点分裂成路径无法重新接合的几部分时，可以提前放弃该分支。

最坏情况下，搜索可能检查大量顶点排列。第 6 章已经说明 $n$ 个不同对象共有 $n!$ 种排列，因此暴力哈密顿搜索会快速增长。欧拉问题可以用奇偶规则完整解决，但哈密顿问题没有同样简单的通用规则。

一个构造示例

令

边集为

从 $A$ 开始，部分选择 $A,B,C$ 可以继续到 $D$，再到 $E$，最后由边 $EA$ 闭合。因此

是一条哈密顿环。它只使用了图中八条边的五条，因为哈密顿要求针对顶点，而不是边覆盖。

规划一次每个场馆只到访一次的节庆之旅：在地图上构造访问顺序，撤销会困住剩余场馆的分支，启用叶子或割点瓶颈等结构障碍，并把成功的哈密顿路线与欧拉边覆盖进行对比。

两种覆盖问题，两类推理方法

欧拉问题询问边，拥有完整的度数奇偶判定和高效构造算法。哈密顿问题询问顶点；简单条件可以排除一部分图，但仍可能需要构造性搜索。

第 11.6 节将从路线转向资源冲突与图的绘制。顶点着色会把相邻对象分开，平面性则会询问能否在不交叉的条件下画出所有边。