3.4 欧拉图与中国邮路

欧拉图与中国邮路

欧拉图

定义

• 欧拉通路：经过图中每条边一次且仅一次、行遍所有顶点的通路。
• 欧拉回路：经过图中每条边一次且仅一次、行遍所有顶点的回路。
• 欧拉图：具有欧拉回路的图。
• 半欧拉图：具有欧拉通路但无欧拉回路的图。

欧拉通路是生成的简单通路，欧拉回路是生成的简单回路。环不影响图的欧拉性。行遍所有顶点，同时经过每条边一次，顶点可以多次经过。

无向欧拉图的判定

定理：无向图 G 是欧拉图当且仅当 G 连通且无奇度数顶点。

定理：无向图 G 是半欧拉图当且仅当 G 连通且恰有两个奇度顶点。

定理：G 是非平凡的欧拉图当且仅当 G 是连通的且为若干个边不重的圈之并。

有向欧拉图的判定

定理：有向图 D 是欧拉图当且仅当 D 是强连通的且每个顶点的入度都等于出度。

定理：有向图 D 是半欧拉图当且仅当 D 是单向连通的，且 D 中恰有两个奇度顶点，其中一个的入度比出度大 1，另一个的出度比入度大 1，其余顶点的入度等于出度。

Fleury 算法

Fleury 算法用于在欧拉图中求出一条欧拉回路：

1. 任取 $v_0\in V(G)$，令 $P_0=v_0$。
2. 设 $P_i=v_0{e}_1{v}_1\dots e_i{v}_i$ 已行遍，按如下方法从 $E(G)-\{e_1,\dots ,e_i\}$ 中选取 $e_{i+1}$：
   • $e_{i+1}$ 与 $v_i$ 相关联；
   • 除非无别的边可供选择，否则 $e_{i+1}$ 不应为 $G_i=G-\{e_1,\dots ,e_i\}$ 中的桥。
3. 当第 2 步不能再进行时算法停止。所得简单通路即为 G 中一条欧拉回路。

中国邮路问题（管梅谷）

中国邮路问题：邮递员从邮局出发，每条街道至少走一次，最后回到邮局，求最短路径。

如果邮路图本身是欧拉图，那么由 Fleury 算法可得到行走路线。如果邮路图本身是非欧拉图，那么为得到行走环游，必须重复行走一些街道。

定理：若 W 是图 G 中一条包含所有边的回路，则 W 在这样的回路中具有最短的长度当且仅当：

1. 每一条边最多重复经过一次；
2. 在 G 的每一个回路上，重复经过的边的条数不超过回路长的一半。

求解思路

即先对原图进行处理，尝试通过加平行边使其中的奇度顶点变成偶度顶点，进而使其变成欧拉图。接着对于图中的每个回路，如果可以用更少的平行边，则进行替换。

特殊情形：如果只有两个奇度顶点 $u$ 与 $v$，那么找到这两个奇度顶点的最短路径，将最短路径上的每条边加一个平行边即可。

一般解法：

1. 用添加重复边的方法求 G 的一个赋权欧拉母图 $G^{\ast }$；
2. 用 Fleury 算法在 G* 中求出欧拉回路。

链接到

• 上一个知识点：3.3 连通性
• 下一个知识点：3.5 哈密顿图