算法导论24.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 5.9k 阅读时长 ≈ 5 分钟

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'(v,u)=c'(u,v)=0\)，因此\(f'(v,u)=f'(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{aligned} &\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'(u,v)-\sum_{v\in V_l(u)\cup V_e(u)}f'(v,u)\\ =&\sum_{v\in V}f(u,v)-\sum_{v\in V}f(v,u)+\sum_{v\in V}f'(u,v)-\sum_{v\in V}f'(v,u)\\ =&\left(\sum_{v\in V}f(u,v)-\sum_{v\in V}f(v,u)\right)+\left(\sum_{v\in V}f'(u,v)-\sum_{v\in V}f'(v,u)\right)\\ =&0 \end{aligned}\)

24.2-2

从\(S\)中的节点到\(T\)中的节点的所有边如下：

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

从\(T\)中的节点到\(S\)中的节点的所有边如下：

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

因此，切割\((S,T)的流大小\)为\(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'=\{s_1,s_2,\dots,s_m\},T'=\{t_1,t_2,\dots,t_n\}\)，即\(S'\)是\(G\)中的所有源点，\(T'\)是\(G\)中的所有原点。由于\(S'\cap T'=\varnothing,(S'\cup T')\subseteq V\)，因此可以构造出一个在图\(G\)上的切割\((S,T)\)，使得\(S'\subseteq S,T'\subseteq T\)。由于\(G'\)的网络容量是有限的，即\(\forall (u,v)\in E,c(u,v)<\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'\)是\(G\)中的所有原点。

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

最终所给定的流网络\(G'\)和容量函数\(c'\)为所求。

24.2-7

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

首先证明容量限制。按照\(c_f(p)\)的定义，可以得出\(\forall (u,v) \in p,c_f(p)\le c_f(u,v)\)。因此，对于\(\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\)。对于\(\forall (u,v)\not\in p\)，都有\(f_p(u,v)=0\)。因此容量限制得证。

接下来证明流量守恒。\(\forall v\not\in p\)，由于增广路径\(p\)不经过\(v\)，因此流入\(v\)的流量和与流出\(v\)的流量和均为\(0\)，因此\(v\)处满足流量守恒。\(\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'\)将不是\(G\)中的一个流。不过，\(f\uparrow f'\)仍然满足流量守恒，因为方程24.6的推导仅仅依赖于\(f'\)本身的定义，根据题目24.2-1的进一步形式化证明可知，\(f\uparrow f'\)仍然满足流量守恒。

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

graph LR
  s((s));t((t));
  s--1-->t

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

24.2-10

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)\)不连通意味着：\(\forall u\in V,\exists v\in V\)，使得从\(u\)节点不可到达\(v\)节点。因此，我们可以随机选定\(V\)中的一个节点作为源点\(s\)，枚举所有\(t\in V-\{s\}\)作为汇点，并且将\(G\)中的每一条无向边都替换成一对容量均为\(1\)的反平行边。接下来只需要对这个构造出来的流网络求解最大流（也就是这个流网络的最小割），那么求出来的值中，最小的一个恰好为答案。具体过程由EDGE-CONNECTIVITY给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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'\)则是所求流。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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\)都加上一个足够小的常数\(\epsilon\)得到\(c'\)，那么对于\(G\)中的以容量函数\(c\)得到的每一个最小割\((S,T)\)，如果其容量值为\(C\)，那么以容量函数\(c'\)为计算的切割\((S,T)\)的容量为\(C+\epsilon \cdot M_{S,T}\)，其中\(M_{S,T}\)是从\(S\)中的节点指向\(T\)中的节点的边数。那么，以容量函数\(c'\)运行最大流算法后，在残余网络\(G_{f'}\)中，从\(s\)可达的节点集合为\(S\)，其余节点在\(T\)中，那么切割\((S,T)\)为以容量函数\(c\)所求的最小割，并且切割的边数最小。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)