4.4.3

题

利用标号法求下图的容量网络中的最大 $(x,y)$ 流

设 $G$ 是 Euler 图。求 $G$ 中 Euler 回有下列有效 Fleury 算法

1.令 $P_0=x_0$

2.假设 $P_i=x_0e_1x_1\dots x_{i-1}e_ix_i$ 已确定，取 $e_{i+1}\in E(G)\backslash{e_1,\dots,e_i}$ 使得

(i) $e_{i+1}=x_ix_{i+1}$

(ii) 除非无别的边选择，$e_{i+1}$ 不是 $G_i=G-{e_1,\dots,e_i}$ 的割边

3.当第 2 步不能再执行时，停止

(a) 证明：若 $G$ 是 Euler 图，则由 Fleury 算法构造出的迹 $P$ 是 $G$ 中 Euler 回

算法构造出的肯定是回，因为 Euler 图每个点都是偶数，假设终止在 $x_m\neq x_0$，则此 $x_m$ 在 $P$ 中的点度为奇数，这说明与 $x_m$ 关联的边至少还有一条不在 $P$ 中，这样算法可以继续，矛盾

假设 $P$ 不是 Euler 回，故 $G-P$ 是偶度图，每个连通分支是 Euler 图。考虑 $P$ 最后经过 $G-P$ 上的连通分支为 $C$，点为 $x_i$

断言：$e_{i+1}$ 是割边

若不是，则之后还会经过 $C$，与最后性矛盾

然而 $C$ 有一个 Euler 回，故删去 $C$ 中与 $x_i$ 关联的一边 $e^\prime$ 不会破坏 $C$ 的连通性，故 $e^\prime$ 不是割边，算法应该选择 $e^\prime$ 而不是 $e_{i+1}$，矛盾，故 $P$ 是 Euler 回