算法导论 24.2 Exercises 答案

24.2-1

对于 $u$ 的所有非出边，根据定义，都有 $c(u,v)=0$，因此 $f(u,v)=c(u,v)=0$，也就是有 ${\displaystyle \sum _{v\in V_l(u)}f(u,v)=\sum _{v\in V}f(u,v)}$。

对于 $u$ 的所有非入边，根据定义，都有 $c(v,u)=0$，因此 $f(v,u)=c(v,u)=0$，也就是有 ${\displaystyle \sum _{v\in V_e(u)}f(v,u)=\sum _{v\in V}f(v,u)}$。

对于 $u$ 的所有非关联边，无论之后的流变化如何，根据定义，都有 $c^{\prime }(v,u)=c^{\prime }(u,v)=0$，因此 $f^{\prime }(v,u)=f^{\prime }(v,u)=0$，也就是有 ${\displaystyle \sum _{v\in V_l(u)\cup V_e(u)}f(v,u)=\sum _{v\in V}f(v,u),\sum _{v\in V_l(u)\cup V_e(u)}f(u,v)=\sum _{v\in V}f(u,v)}$。

因此，最终有

$\begin{array}{rl}& \sum _{v\in V_l(u)}f(u,v)-\sum _{v\in V_e(u)}f(v,u)+\sum _{v\in V_l(u)\cup V_e(u)}{f}^{\prime }(u,v)-\sum _{v\in V_l(u)\cup V_e(u)}{f}^{\prime }(v,u)\\ =& \sum _{v\in V}f(u,v)-\sum _{v\in V}f(v,u)+\sum _{v\in V}{f}^{\prime }(u,v)-\sum _{v\in V}{f}^{\prime }(v,u)\\ =& (\sum _{v\in V}f(u,v)-\sum _{v\in V}f(v,u))+(\sum _{v\in V}{f}^{\prime }(u,v)-\sum _{v\in V}{f}^{\prime }(v,u))\\ =& 0\end{array}$

24.2-2

从 $S$ 中的节点到 $T$ 中的节点的所有边如下：

$\begin{array}{|ccc|}\hline e& f& c\\ (s,v_1)& 11& 16\\ (v_2,v_1)& 1& 4\\ (v_4,v_3)& 7& 7\\ (v_4,t)& 4& 4\\ \hline\end{array}$

从 $T$ 中的节点到 $S$ 中的节点的所有边如下：

$\begin{array}{|ccc|}\hline e& f& c\\ (v_3,v_2)& 4& 9\\ \hline\end{array}$

因此，切割 $(S,T)\mathrm{的}\mathrm{流}\mathrm{大}\mathrm{小}$ 为 $11+1+7+4-4=19$，容量为 $16+4+7+5=31$。

24.2-3

接下里将使用残余网络来表示这个流网络。一开始残余网络如下：

随后运行 BFS，找到了一条增广路径 $(s,v_1,v_3,t)$，其流量值为 $12$。由此可以对残余网络进行更新：

随后找到了一条增广路径 $(s,v_2,v_4,t)$，其流量值为 $4$。由此可以对残余网络进行更新：

最后找到了一条增广路径 $(s,v_2,v_4,v_3,t)$，其流量值为 $7$。由此可以对残余网络进行更新：

此后，再也不存在增广路径，因此最大流 $|f|=23$。

24.2-4

令 $S=\{s,v_1,v_2,v_4\},T=\{v_3,t\}$ 为所求。图 24.6 (c) 中路径上的边 $(v_1,v_2)$ 抵消了图 24.6 (b) 所传输的流；图 24.6 (c) 中路径上的边 $(v_2,v_3)$ 抵消了图 24.6 (a) 所传输的流。

24.2-5

令 $G=(V,E)$ 是一个具有多源点多汇点的流网络，并令 $S^{\prime }=\{s_1,s_2,\dots ,s_m\},T^{\prime }=\{t_1,t_2,\dots ,t_n\}$，即 $S^{\prime }$ 是 $G$ 中的所有源点，$T^{\prime }$ 是 $G$ 中的所有原点。由于 $S^{\prime }\cap T^{\prime }=\varnothing ,(S^{\prime }\cup T^{\prime })\subseteq V$，因此可以构造出一个在图 $G$ 上的切割 $(S,T)$，使得 $S^{\prime }\subseteq S,T^{\prime }\subseteq T$。由于 $G^{\prime }$ 的网络容量是有限的，即 $\mathrm{\forall }(u,v)\in E,c(u,v)<\mathrm{\infty }$，因此横跨切割 $(S,T)$ 中的所有边的容量都是有限的，那么切割 $(S,T)$ 的容量 $c(S,T)$ 是有限的。

这个流网络转换后，那么令新流网络为 $G_1=(V_1,E_1)$，其中 $V_1=V\cup \{s,t\}$，并且 $s$ 是超级源点，$t$ 是超级汇点。那么对流网络构造切割 $(S_1,T_1)$ 满足 $S_1=S\cup \{s\},T_1=T\cup \{t\}$，那么可见，图 $G_1$ 上切割 $(S_1,T_1)$ 的容量 $c(S_1,T_1)$ 和 $c(S,T)$ 是相等的的（因为横跨这两个切割的都是相同的边），因此按照推论 26.5，$G_1$ 中的所有流都受限于 $c(S_1,T_1)$，即任何一个流的值都是有限的。

24.2-6

思路和第 24.1 节时构造超级源点和超级汇点相似。令 $G=(V,E)$ 是题目所提供的流网络，并令 $S=\{s_1,s_2,\dots ,s_m\},T=\{t_1,t_2,\dots ,t_n\}$，即 $S$ 是 $G$ 中的所有源点，$T^{\prime }$ 是 $G$ 中的所有原点。

那么令新转化后的流网络为 $G^{\prime }=(V^{\prime },E^{\prime })$，其中 $V^{\prime }=V\cup \{s,t\}$，并且 $s$ 是超级源点，$t$ 是超级汇点。并且 $\mathrm{\forall }(u,v)\in E,(u,v)\in E^{\prime }$ 均成立，$c^{\prime }(u,v)=c(u,v)$。对于 $\mathrm{\forall }{s}_i\in S,(s,s_i)\in E^{\prime }$，并且有 $c^{\prime }(s,s_i)=p_i$；对于 $\mathrm{\forall }{t}_i\in T,(t_i,t)\in E^{\prime }$，并且有 $c^{\prime }(t_1,t)=q_i$。

最终所给定的流网络 $G^{\prime }$ 和容量函数 $c^{\prime }$ 为所求。

24.2-7

令这条简单路径 $p$ 表示为 $v_1,v_2,\dots ,v_m$，其中 $v_1=s,v_m=t$。

首先证明容量限制。按照 $c_f(p)$ 的定义，可以得出 $\mathrm{\forall }(u,v)\in p,c_f(p)\le c_f(u,v)$。因此，对于 $\mathrm{\forall }(u,v)\in p,f_p(u,v)=c_f(p)\le c_f(u,v)$。由于边的容量是正数，因此可以得出 $c_f(p)>0$。也就是说，$f_p(u,v)\ge 0$。对于 $\mathrm{\forall }(u,v)\notin p$，都有 $f_p(u,v)=0$。因此容量限制得证。

接下来证明流量守恒。$\mathrm{\forall }v\notin p$，由于增广路径 $p$ 不经过 $v$，因此流入 $v$ 的流量和与流出 $v$ 的流量和均为 $0$，因此 $v$ 处满足流量守恒。$\mathrm{\forall }v\in p-\{s,t\}$，仅有一条边流入 $v$ 和一条边流出 $v$，并且它们的流量值均为 $c_f(p)$，因此 $v$ 处满足流量守恒。

故 $f_p$ 是 $G_f$ 中的一个流。对于 $s$，仅有一条边从它流出，其大小为 $c_f(p)$，因此 $|f_p|=c_f(p)>0$。

24.2-8

可见，算法 FORD-FULKERSON 的第 3 行是求解了一条增广路径，即从 $s$ 到 $t$ 的简单路径。由于这是一条以 $s$ 为起点的简单路径，因此这条路径不可能从某处重新到达 $s$，因此残余网络中，指向 $s$ 的反向边是不必要的，它不会影响第 3 行的求解增广路径求取算法。因此原结论成立。

24.2-9

如此增广后的 $f\uparrow f^{\prime }$ 将不是 $G$ 中的一个流。不过，$f\uparrow f^{\prime }$ 仍然满足流量守恒，因为方程 24.6 的推导仅仅依赖于 $f^{\prime }$ 本身的定义，根据题目 24.2-1 的进一步形式化证明可知，$f\uparrow f^{\prime }$ 仍然满足流量守恒。

接下来说明 $f\uparrow f^{\prime }$ 不满足容量限制。令 $G=(V,E),V=\{s,t\},E=\{(s,t)\},c(s,t)=1$。如图所示：

那么，令 $f,f^{\prime }$ 是两个流，其中 $f(s,t)=f^{\prime }(s,t)=1$，那么可以计算出 $(f\uparrow f^{\prime })(s,t)=f(s,t)+f^{\prime }(s,t)-f^{\prime }(t,s)=1+1-0=2>c(s,t)$，从而违反了容量限制。

24.2-10

首先求出流网络 $G=(V,E)$ 的其中一个最大流 $f$。那么令 $c^{\prime }(u,v)=f(u,v)$。并且，如果 $c^{\prime }(u,v)>0$，那么 $(u,v)\in E^{\prime }$。由此可知，$E^{\prime }\subseteq E$。

这个算法将进行多次迭代，每次迭代的过程中，找到 $E^{\prime }$ 中 $c^{\prime }$ 值最小的边 $(u,v)$，并且通过在 $G^{\prime }=(V,E^{\prime })$ 上对 $u$ 进行反向 BFS，对 $v$ 进行正向 BFS，找到一条路径 $p:s⇝u\to v⇝t$。可见，$p$ 是一条增广路径，并存入数组中，接下来令 $c_f^{\prime }(p)=c^{\prime }(u,v)$。那么对 $p$ 中的所有边，都减去值 $c_f^{\prime }(p)$。这轮迭代结束后，边 $(u,v)$ 必定从 $E^{\prime }$ 中删除。因此，这个算法最多迭代 $|E^{\prime }|\le |E|$ 次，也就是说，最多只有 $|E|$ 条增广路径。

大致过程由 AUGMENTING-PATHS-BOUNDS 给出，其迭代轮数至多为 $|E|$ 轮。

AUGMENTING-PATHS-BOUNDS(G, s, t)
  Let P be a new array
  Let E' be a new set
  FORD-FULKERSON(G, s, t)
  for each edge (u, v) ∈ G.E
    if (u, v).f > 0
      (u, v).c' = (u, v).f
      INSERT(E', (u, v))
  while E' != ∅
    let (u, v) be the edge s.t. (u, v).c' is minimum in E'.
    run BFS twice (forward and back) to get the path p from s to t through (u,v)
    INSERT(P, p)
    c' = (u, v).c'
    for each edge (u, v) ∈ E'
      (u, v).c' = (u, v).c' - c'
      if (u, v).c' == 0
        DELETE(E', (u, v))
  return E

24.2-11

首先，一个无向图 $G=(V,E)$ 不连通意味着：$\mathrm{\forall }u\in V,\mathrm{\exists }v\in V$，使得从 $u$ 节点不可到达 $v$ 节点。因此，我们可以随机选定 $V$ 中的一个节点作为源点 $s$，枚举所有 $t\in V-\{s\}$ 作为汇点，并且将 $G$ 中的每一条无向边都替换成一对容量均为 $1$ 的反平行边。接下来只需要对这个构造出来的流网络求解最大流（也就是这个流网络的最小割），那么求出来的值中，最小的一个恰好为答案。具体过程由 EDGE-CONNECTIVITY 给出。

EDGE-CONNECTIVITY(G)
  Let V, E be new sets
  V = G.V
  select vertex s ∈ G.V randomly
  for each edge (u, v) ∈ G.E
    Let x be a new vertex
    INSERT(V, x)
    INSERT(E, (u, v))
    (u, v).c_f = 1
    INSERT(E, (v, x))
    (v, x).c_f = 1
    INSERT(E, (x, u))
    (x, u).c_f = 1
  edge-connectivity = |G.V| - 1
  for each vertex t ∈ G.V - {s}
    Let G' = (V, E) be a new flow net work
    FORD-FULKERSON(G', s, t)
    edge-connectivity = min{edge-connectivity, |f|}
  return edge-connectivity

我们构造了 $|V|-1$ 个流网络，每个流网络一共有 $|V|+|E|=O(V+E)$ 个节点，一共有 $3|E|=O(E)$ 条边。因此如上算法为所求。

24.2-12

由于所有增广路径都是从 $s$ 开始的，因此如果存在一条边 $(v,s)$，使得 $f(v,s)=1$，那么这意味着节点 $s$ 在某个环上（也就是说，边 $(v,s)$ 也在环上）。我们可以考虑对流 $f$ 进行 DFS，处理出这个环，并且将这个环上的所有边的流大小减去 $1$，得到的新流 $f^{\prime }$ 则是所求流。

不难证明所求流 $f^{\prime }$ 满足容量限制，因为环上的所有边的流大小都超过 $1$，将它们都减去 $1$ 不会使得流大小变成负数。流量守恒也不难证明，因为这个环上的所有节点，减去的流入流量和流出流量都为 $1$，因此由于原来的流 $f$ 满足流量守恒，$f^{\prime }$ 也满足流量守恒；对于 $s$ 也如此，因此有 $|f^{\prime }|=|f|$。

整个具体过程由 SIMPLIFY-FLOAT-1 给出，由于是对一次 DFS 进行修改，因此其时间复杂度为 $O(E)$。

SIMPLIFY-FLOAT-DFS(G, s, u)
  u.color = GRAY
  for each vertex v in G.Adj[u]
    if (u, v).f > 0
      if v.color == WHITE
        v.π = u
        SIMPLIFY-FLOAT-DFS(G, s, v)
      else if v.color == GRAY and v == s and (u, s).f == 1
        (u, s).f = (u, s).f - 1
        z = u
        while z != NIL
          (z.p, z).f = (z.p, z).f - 1
          z = z.p
        exit                      // 算法结束，从此退出。
  u.color = BLACK

SIMPLIFY-FLOAT-1(G, s, t)
  for each vertex u ∈ G.V
    u.color = WHITE
    u.π = NIL
  SIMPLIFY-FLOAT-DFS(G, s, s)

24.2-13

假设对流网络 $G=(V,E)$ 所有边的容量 $c$ 都加上一个足够小的常数 $ϵ$ 得到 $c^{\prime }$，那么对于 $G$ 中的以容量函数 $c$ 得到的每一个最小割 $(S,T)$，如果其容量值为 $C$，那么以容量函数 $c^{\prime }$ 为计算的切割 $(S,T)$ 的容量为 $C+ϵ\cdot M_{S,T}$，其中 $M_{S,T}$ 是从 $S$ 中的节点指向 $T$ 中的节点的边数。那么，以容量函数 $c^{\prime }$ 运行最大流算法后，在残余网络 $G_{f^{\prime }}$ 中，从 $s$ 可达的节点集合为 $S$，其余节点在 $T$ 中，那么切割 $(S,T)$ 为以容量函数 $c$ 所求的最小割，并且切割的边数最小。

这个常数 $ϵ$ 必须足够小，以至于对最大流的值产生的影响是微不足道的（产生的影响小于 $1$ 个单位的流）。因此，$ϵ={\displaystyle \frac{1}{|E|+1}}$ 是一个合适的取值，哪怕所有边都做出了贡献，对最大流的贡献总共也只有 ${\displaystyle \frac{|E|}{|E|+1}}$，不超过 $1$。

当然，为了确保流的容量仍然是整数，我们可以考虑对容量函数 $c$ 进行放缩。将 $c$ 所有的容量全部都扩大到原来的 $|E|+1$ 倍，那么求出来的最大流也是原来的 $|E|+1$ 倍。接下来再对所有边容量都加上 $1$，运行最大流算法后，从 $s$ 可达的节点集合为 $S$，其余节点在 $T$ 中，切割 $(S,T)$ 为所求。更正式的定义，则是 $\mathrm{\forall }(u,v)\in E$，取 $c^{\prime }(u,v)=c(u,v)\cdot (|E|+1)+1$。

这个算法的过程由 MINIMIN-CUT-MINIMUM-EDGES 给出。

MINIMIN-CUT-MINIMUM-EDGES(G, s, t)
  for each edge (u, v) ∈ G.E
    (u, v).{c'_f} = (u, v) * (|G.E| + 1) + 1
    run FORD-FULKERSON(G, s, t) using c_'f as capacity.
  let E, S, T be a new set
  for each edge (u, v) ∈ G.E
    if (u, v).f > -
      INSERT(E, (u, v))
  let G' = (G.V, E) be a new graph
  BFS(G', s)
  for each vertex u ∈ G.V
    if u.color == BLACK
      INSERT(S, u)
    else
      INSERT(T, u)
  return (S, T)