算法导论24 Problems 答案

发表于 2023-06-23 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 14k 阅读时长 ≈ 13 分钟

24-1

a

本题的做法和24.1-7完全一致，其中\(l(v)\)是节点的流量限制。

将图\(G\)中的每个节点\(v\)拆分成两个节点\(v_{in},v_{out}\)，并且从\(v_{in}\)到\(v_{out}\)只需要连一条容量为\(l(v)\)的边即可。对图\(G'=(V',E')\)更正式的描述如下：

\(\forall v\in V,v_{in},v_{out}\in V'\)均成立。
\(\forall v\in V,(v_{in},v_{out})\in E'\)均成立，其中\(c'(v_{in},v_{out})=l(v)\)。
\(\forall (u,v)\in E,(u_{out},v_{in})\in E'\)均成立，其中\(c'(u_{out},v_{in})=c(u,v)\)。

那么假设图\(G\)上对应的源点和汇点分别为\(s,t\)，那么在图\(G'\)上的源点和汇点分别为\(s_{in},t_{out}\)。

因此，图\(G'\)上一共有\(2|V|\)个节点，\(|V|+|E|\)条边。

b

令\(P\)表示这\(m\)个起点的数组，每个元素具有属性\(x\)和\(y\)，用于表示坐标。

令图\(G=(V,E)\)表示这个流网络。将每个格点（一共\(n^2\)个）以及源点\(s\)和汇点\(t\)加入\(V\)中。对网格中的每条相邻边，都转化成一对容量为\(1\)的反平行边（此处忽略处理反平行边的细节），并加入\(E\)中。枚举\(P\)中的每个节点，从\(s\)向其连接一条容量为\(1\)的边；枚举正方形边缘中的每个顶点，从其向\(t\)连接一条容量为\(1\)的边。最终运行FORD-FULKERSON算法，判断最大流的值是否等于\(m\)即可。

接下来分析这个算法的时间复杂度：\(V\)中一共有\(n^2+2\)个节点，网格中每条边在流网络中对应了\(3\)条有向边，因此这部分有\(6n(n-1)\)条有向边。从\(s\)出发的边一共有\(m\)条，以\(t\)为终点的边一共有\(4(n-1)\)条。

因此有\(|V|=n^2+2=O(n^2),|E|=6n(n-1)+m+4(n-1)=O(n^2)\)。由于FORD-FULKERSON算法的时间复杂度为\(O(VE^2)\)，因此解决该问题的时间复杂度为\(O(n^6)\)。具体过程由ESCAPE-GRID给出。

ESCAPE-GRID(n, P, m)
  let s, t be new vertexes
  let V = {s, t}, E be new sets
  for i = 1 to n
    for j = 1 to n
      let v_{i, j} be a new vertex
      INSERT(V, v_{i, j})
  for each p in P
    INSERT(E, (s, v_{p.x, p.y}))
  for i = 1 to n
    for j = 1 to n
      if (i == 1 or i == n) and (j == 1 or j == n)
        INSERT(E, (v_{i, j}, t))
      if j < n
        let z be a new vertex
        INSERT(v_{i, j}, v_{i, j + 1})
        INSERT(v_{i, j + 1}, z)
        INSERT(z, v_{i, j})
      if i < n
        let z be a new vertex
        INSERT(v_{i, j}, v_{i + 1, j})
        INSERT(v_{i + 1, j}, z)
        INSERT(z, v_{i, j})
  for each (u, v) in E
    c_f(u, v) = 1
  let G = (V, E) be a new flow network
  f = FORD-FULKERSON(G, s, t)
  return |f| == m

24-2

a

以题目中给定好的\(G'\)进行说明。\(\forall (u,v)\in E,c(u,v)=1\)，并且以\(x_0\)为源点，\(y_0\)为汇点运行FORD-FULKERSON算法后得到最大流\(f\)后，那么所需要的路径数为\(n-|f|\)。

对于图\(G'=(V',E')\)，如果所求最大流\(f\)满足\(f(x_i,y_j)= 1\)，其中\(1\le i,j\le n\)，那么\((i,j)\)为\(G\)所求最小路径集合中的一条边。假设最终所求边集为\(E_0\)，那么也就是有\(|E_0|=n-|f|\)。

接下来说明这个算法是正确的。由于所有边的容量都为\(1\)（且都是整数），因此对于每个节点\(v\in V-\{x_0,y_0\}\)，最多只一条边流入这些\(v\)；如果有流入，根据流量守恒，也有一条边对应流出（只流向某个节点）。对于边\((x_0,x_i)\)，每个节点最多只有一次成为起点的机会；同样对于边\((y_j,y_0)\)，每个节点最多只有一次成为终点的机会。由于\(c(x_i,y_j)=1\)，因此对于\(\forall i\in V\)，考虑如下\(4\)种情况：

\(f(x_0,x_i)=0,f(y_i,y_0)=0\)，这说明\(i\)是一个孤立点；
\(f(x_0,x_i)=1,f(y_i,y_0)=0\)，这说明\(i\)是某一条路径的起点；
\(f(x_0,x_i)=0,f(y_i,y_0)=1\)，这说明\(i\)是某一条路径的终点；
\(f(x_0,x_i)=1,f(y_i,y_0)=1\)，这说明\(i\)是某一条路径的中间节点。

因此，\(n-|f|\)计算出了这个图中有多少个终点（即有多少条路径）。

由于计算出来的\(f\)已经是最大流，它无法再继续增加\((x_i,y_j)\)的基数，因此此时求出的边集\(E_0\)是一个最小路径覆盖；每找到一条边\((x_i,y_j)\)，这个操作就相当于将一条以\(i\)为终点和以\(j\)为起点的边拼接在一起，从而将最小路径数减少\(1\)。

可以注意到，当令\(L=\{x_i\mid i\in[1,n]\},R=\{y_i\mid i\in[1,n]\}\)时，上述问题的解决相当于是求解一个二分图最大匹配，因此这个算法的时间复杂度为\(O(VE)\)。

b

这个算法不能正确地工作在有环图上。令\(G=(V,E),V=\{1,2,3\},E=\{(1,2),(2,3),(3,1)\}\)。那么由此构造出来的图\(G'=(V',E')\)为：

\(V'=\{x_0,x_1,x_2,x_3,y_0,y_1,y_2,y_3\}\)
\(E'=\{(x_0,x_1),(x_0,x_2),(x_0,x_3),(y_1,y_0),(y_2,y_0),(y_3,y_0),(x_1,y_2),(x_2,y_3),(x_3,y_1)\}\)

最终，对图\(G'\)运行FORD-FULKERSON算法得到\(|f|=3\)，只需要花费\(0\)条路径即可覆盖这\(3\)个节点，这是不正确的。

24-3

本题的b和c题都参考了如下链接中的内容。

a

考虑使用反证法证明。如果\(\exists J_i\in T\)，使得\(\exists C_k\in R_i,C_k\not\in T\)成立。那么说明\(C_k\in S\)。考虑计算切割\(c(S,T)\)的容量，那么有

\(\begin{aligned} c(S,T)&=\sum_{u\in S}\sum_{v\in T} c(u,v)\\ &\ge c(C_k,J_i)\\ &=\infty \end{aligned}\)

这和\((S,T)\)是一个有限容量的切割这个假设是矛盾的。因此原结论成立。

b

首先定义一个有效计划组\(P'=(C',J')\)，这个有效计划组的定义是：\(\forall J_i\in J'\)，如果\(C_k\in R_i\)，那么\(C_k\in C'\)。此时，这个有效计划组\(P'\)的盈利值为\(\displaystyle{v(P')=\sum_{J_i\in J'}p_i-\sum_{C_k\in C'}e_k}\)。

那么定义一个引理：流网络\(G\)中存在一个有限容量的割\((S,T)\)，当且仅当存在一个有效计划组\(P'\)，使得\(\displaystyle{v(P')=\sum_{J_i\in J}p_i -c(S,T)}\)。

首先证明充分性。令\((S,T)\)是\(G\)中的一个有限容量割。那么可以构造如下计划组\(P'=(C',J')\)：如果\(C_k\in T\)，那么\(C_k\in C'\)；如果\(J_i\in T\)，那么\(J_i\in J'\)。按照题目24-3-a的结论，计划组\(P'\)是一个有效计划组，因为\(c(S,T)\)是有限的，条件\(J_i\in T\)（即\(J_i\in J'\)），确保了\(\forall C_k\in R_i\)，都有\(C_k\in T\)，从而保证了\(J_i\in J'\)。

由于\((S,T)\)是一个有限容量割，因此割的容量\(c(S,T)\)不可能来自形如\((C_k,J_i)\)的边，这意味着\(C_k\in S,J_i\in T\)。最终\(c(S,T)\)的值只能由形如\((s,C_k)\)和\((J_i,t)\)的边构成。更正式的，\(c(S,T)\)可以写成：

\[c(S,T)=\sum_{C_k\in T} c(s,C_k)+\sum_{J_i\in S} c(T_i,t)\]

考虑上述形如\((s,C_k),C_k\in T\)的边，这意味着\(C_k\)是被雇佣的专家，并且由于\(c(s,C_k)=e_k\)，因此可以写出\(\displaystyle{\sum_{C_k\in T} c(s,C_k)=\sum_{C_k\in C'}e_k}\)。同样的，对于形如\((J_i,t),J_i\in S\)的边。这意味着\(J_i\)不在有效计划组\(P'\)中，并且由于\(c(J_i,t)=p_i\)，因此可以写出\(\displaystyle{\sum_{J_i\in S} c(J_i,t)=\sum_{J_i\not\in J'}p_i}\)。计算这个有效工作组\(P'\)的盈利值\(v(P')\)，有

\(\begin{aligned} v(P')&=\sum_{J_i\in J'}p_i-\sum_{C_k\in C'}e_k\\ &=\sum_{J_i\in J'}p_i+\sum_{J_i\not\in J'}p_i-\sum_{C_k\in C'}e_k-\sum_{J_i\not\in J'}p_i\\ &=\left(\sum_{J_i\in J'}p_i+\sum_{J_i\not\in J'}p_i\right)-\left(\sum_{C_k\in C'}e_k+\sum_{J_i\not\in J'}p_i\right)\\ &=\sum_{J_i\in J}p_i-\left(\sum_{C_k\in C'}e_k+\sum_{J_i\not\in J'}p_i\right)\\ &=\sum_{J_i\in J}p_i-\left(\sum_{C_k\in T} c(s,C_k)+\sum_{J_i\in S} c(J_i,t)\right)\\ &=\sum_{J_i\in J}p_i-c(S,T) \end{aligned}\)

由此充分性成立。

接下来证明必要性。对于一个有效计划组\(P'=(C',J')\)，按如下方式构造流网络\(G\)上的一个割\((S,T)\)：\(\forall J_i\in J'\)，都有\(J_i\in T\)，并且对于\(\forall C_k\in R_i\)，都有\(C_k\in T\)。对于其它不在\(V-\{s,t\}\)，都在\(S\)中。可以证明，\(c(S,T)\)是一个有限容量的割，因为只要\(J_i\in T\)，那么对应的专家都有\(C_k\in T\)，并不存在\(C_k\in R_i\land C_k\in S\land J_i\in T\)的情况，因此割\((S,T)\)的容量是有限的。

和之前的分析一致，割\((S,T)\)的容量为\(\displaystyle{c(S,T)=\sum_{J_i\in J}p_i-c(S,T)}\)。由此必要性成立。

因此根据上面证明的引理，我们可以只凭借最小割的容量\(c(S,T)\)以及给定的\(p_i\)值，求出其最大盈利值\(\displaystyle{\sum_{J_i\in J}p_i-c(S,T)}\)。

c

按照题目中给定的流网络\(G\)，源点\(s\)和汇点\(t\)运行Ford-Fulkerson算法，得到最大流\(f\)及其对应的残余网络\(G_f\)后，\(\displaystyle{\sum_{J_i\in J}p_i-|f|}\)即为最大盈利值，对于从\(s\)不可达的节点\(C_k\)，则是需要应聘的专家；对于从\(s\)不可达的节点\(J_i\)，则是需要完成的任务。

可以知道流网络\(G=(V,E)\)满足\(|V|=n+m+2,|E|=n+m+r\)。由于FORD-FULKERSON算法的运行的时间复杂度为\(O(VE^2)\)，因此这个决定最优有效计划组的算法\(P'\)的时间复杂度为\(O((n+m)(n+m+r)^2)\)。

24-4

a

如果当前边使用的容量\(f(u,v)\)仍然不满，那么为这条边加上\(1\)个单位的容量仍然不会增加最大流（因为\((u,v)\)还有容量剩余，此前就可以使用）。否则，尝试通过BFS寻找一条增广路径\(p\)，如果找得到，这条路径必定经过\((u,v)\)。接下来只需要对\(p\)上的所有边的流量增加\(1\)即可。由于核心过程仅仅是一次BFS找到增广路径\(p\)，因此其时间复杂度为\(O(V+E)\)。大概过程由INCREASE-CAPICITY-UPDATE-FLOW给出。

INCREASE-CAPICITY-UPDATE-FLOW(G, s, t, u, v)
  (u, v).c_{f} = (u, v).c_{f} + 1
  // 增加并不会产生效果
  if (u, v).c_{f} > (u, v).f + 1
    return
  if there exists a path p from s to t in the residual network G_f
    for each edge (u, v) in p
      if (u, v) ∈ G.E
        (u, v).f = (u, v).f + 1
      else
        (v, u).f = (v, u).f - 1

b

如果当前边使用的容量\(f(u,v)\)仍然不满，那么为这条边减去\(1\)个单位的容量仍然不会减少最大流。否则，尝试通过对\(u\)进行反向BFS，对\(v\)进行正向BFS，找到一条路径\(p:s\rightsquigarrow u\rightarrow v\rightsquigarrow t\)。接下来只需要对\(p\)上的所有边的流量减少\(1\)即可。由于核心过程仅仅是两次BFS找到一条完整的增广路径\(p\)，因此其时间复杂度为\(O(V+E)\)。大概过程由DECREASE-CAPICITY-UPDATE-FLOW给出。

DECREASE-CAPICITY-UPDATE-FLOW(G, s, t, u, v)
  if (u, v).c_{f} > (u, v).f
    (u, v).c_{f} = (u, v).c_{f} - 1
    return
  run BFS twice (forward and back) to get the path p from s to t through (u, v)
  for each edge (u, v) in p
    if (u, v) ∈ G.E
      (u, v).f = (u, v).f - 1
    else
      (v, u).f = (v, u).f + 1
  (u, v).c_{f} = (u, v).c_{f} - 1

24-5

a

假设当前某个最小割为\((S,T)\)，按照切割容量的定义\(c(S,T)\)，可以得到

\(\begin{aligned} c(S,T)&=\sum_{u\in S}\sum_{v\in T} c(u,v)\\ &=\sum_{(u,v)\in E\land u\in S\land v\in T} c(u,v)\\ &\le\sum_{(u,v)\in E} c(u,v)\\ &\le\sum_{(u,v)\in E} C\\ &=C|E| \end{aligned}\)

因此原结论成立。

b

基本思想是，忽略掉所有满足\(c_f(u,v)<K\)的所有边，在剩下的边中以\(s\)为起点进行BFS，如果能够到达\(t\)，那么说明找到了一条从\(s\)到\(t\)且流量值至少为\(k\)的增广路径。由于核心是进行一次BFS，因此这个过程的时间复杂度为\(O(E)\)。具体过程由AUGMENTING-PATH-AT-LEAST-K给出。

AUGMENTING-PATH-AT-LEAST-K(G, s, t, K)
  for each vertex u ∈ G.V - {s}
    u.d = ∞
    u.π = NIL
    u.color = WHITE
  s.d = 0
  s.π = NIL
  s.color = GRAY
  Q = ∅
  ENQUEUE(Q, s)
  while Q != ∅ 
    u = DEQUEUE(Q)
    for each vertex v in G.Adj[u]               // search the neighbors of u
      if v.color == WHITE and (u, v).c_{f} >= K // is v being discovered now?
        v.d = u.d + 1
        v.π = u
        v.color = GRAY
        ENQUEUE(Q, v)                     // v is now on the frontier
    u.color = BLACK                       // u is now behind the frontier
  if t.p == NIL
    return NIL
  let P be a new array
  z = t
  while t != NIL
    INSERT(P, z)
    z = z.p
  REVERSE(P)
  // 增广路径存在数组P中
  return P

c

在算法MAX-FLOW-BY-SCALING的第3行定义了\(K\)的值是\(2\)的幂。在第4行的while循环尚未结束时，\(K\)仍然是一个\(2\)的幂，因此可以取到\(K=1\)。在此时，第5行代码将寻找到所有容量至少为\(1\)的增广路径\(p\)，这意味着存在一条从\(s\)到\(t\)的路径\(p\)，并将\(p\)扩增到流\(f\)中。此时第5行while循环如果结束了，就意味着不再有增广路径（因为容量必定是整数，所以流也是整数），此时已经完成求解最大流。

因此算法MAX-FLOW-BY-SCALING能够正确地求出最大流。

d

首先使用循环不变量证明，在每轮外层while循环的循环体执行前，都不存在大小至少为\(2K\)的增广路径，整个过程都是如此。

初始化：不难发现，\(2K=2^{\lfloor\lg C\rfloor+1}>2^{\lg C}=C\)，然而\(C\)已经是图中容量的最大值，因此此时最大的增广路径容量不超过\(2K\)。

保持：当本轮外层while循环体结束时，已经没有增广路径的长度至少为\(K\)，此时第7行将当\(K\)被除至一半后，变成\(K'(K=2K')\)时，此时就没有增广路径的长度至少为\(2K'\)，这个\(K'\)将作为下一轮的\(K\)使用，因此原结论成立。

终止：最终外层while循环终止，\(K<1\)，此时算法终止。

总之，整个过程中，都不存在容量至少为\(2K\)的增广路径。那么令\(G'=(V,E'),E'=\{(u,v)\mid (u,v)\in E_f,c_f(u,v)\ge 2K\}\)，可见\(G'\)中，从\(s\)不能到达\(t\)。令\(S\)是\(G'\)中从\(s\)可达的节点的集合，\(T=V-S\)。我们将证明所求切割\((S,T)\)的容量\(c(S,T)\)满足\(c(S,T)< 2K|E|\)，从而说明\(G'\)的最小割的容量小于\(2K|E|\)。可以按照定义计算\(c(S,T)\)，得：

\(\begin{aligned} c(S,T)&=\sum_{u\in S}\sum_{v\in T} c_f(u,v)\\ &=\sum_{(u,v)\in E\land u\in S\land v\in T} c_f(u,v)\\ &<\sum_{(u,v)\in E\land u\in S\land v\in T} 2K&\qquad(A)\\ &\le\sum_{(u,v)\in E} 2K\\ &=2K|E| \end{aligned}\)

其中，步骤\((A)\)使用了事实：\(c_f(u,v)<2K\)，否则\((u,v)\in E'\)，节点\(v\)将会在\(S\)中。

因此原结论成立。

e

按照题目24-5-d的结论，每轮外层while循环的循环体执行前，最小割的容量少于\(2K|E|\)。每次内层循环执行后，流大小至少增加\(K\)。因此根据引理24.5，内层while循环的执行次数至多为\(\dfrac{2K|E|}{K}=2|E|\)，即\(O(E)\)。

f

由于\(K=2^{\lfloor\lg C\rfloor}\)，因此外层while只会执行\(O(\lg C)\)次。按照题目24-5-d的结论，内层while循环最多执行\(O(E)\)次，每次循环中，使用题目24-5-b的算法找到一条容量至少为\(K\)的路径所花费的时间为\(O(E)\)。因此，整个MAX-FLOW-BY-SCALING算法的时间复杂度为\(O(\lg C)\cdot O(E)\cdot O(E)=O(E^2\lg C)\)。

24-6

a

可以对Dijkstra进行如下修改：用\(x.d\)表示能够到达当前节点\(x\)的最大流的值，并且这条路径的上一个节点为\(x.p\)。此外，使用最大优先队列来处理节点。再初始化节点时，需要将所有节点的\(d\)属性初始化成\(0\)，而源点\(s\)属性则初始化成\(\infty\)。修改后的算法如DIJKSTRA-AUGMENTING-PATH所示，其时间复杂度和原始的Dijkstra算法一致，为\(O(E\lg V)\)。

INITIALIZE-SINGLE-SOURCE-AUGMENTING-PATH(G, s)
  for each vertex v ∈ G.V
    v.d = 0
    v.π = NIL
  v.s = ∞

RELAX-AUGMENTING-PATH(u, v, w)
  if v.d < min(u.d, w(u, v))
    v.d = min(u.d, w(u, v))
    v.π = u

DIJKSTRA-AUGMENTING-PATH(G, s, t)
  INITIALIZE-SINGLE-SOURCE-AUGMENTING-PATH(G, s)
  S = Ø
  Q = Ø
  s.mark = True
  for each vertex u ∈ G.V
    INSERT(Q, u)
  while Q ≠ Ø
    u = EXTRACT-MAX(Q)
    S = S ∪ {u}
    for each vertex v in G.Adj[u]
      RELAX-AUGMENTING-PATH(u, v, c_f)
      if the call of RELAX increased v.d
        INCREASE-KEY(Q, v, v.d)
  if t.p == NIL
    return NIL
  let P be a new array
  z = t
  while t != NIL
    INSERT(P, z)
    z = z.p
  REVERSE(P)
  // 增广路径存在数组P中
  return P

b

本题和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|\)条增广路径。

大致过程为题目24.2-10的AUGMENTING-PATHS-BOUNDS，其迭代轮数至多为\(|E|\)轮。

因此，只需要进行最多\(|E|\)次从\(s\)到\(t\)的扩增，就能得到\(G\)的最大流。

c

在当前的残余网络\(G_f\)中，仍然有\(|f^{\ast}|-|f|\)单位的流未被处理出来。也就是说，令流网络\(G_f\)为全新的图\(G'\)，那么可知，\(G'\)的最大流值为\(|f^{\ast}|-|f|\)，其中对于每一对反平行边\((u,v)\)，要么\(f(u,v)>0\)，要么\(f(v,u)>0\)。因此\(G'\)中的最大流最多只有\(|E|\)条边满足\(f(u,v)>0\)。按照题目24-2-b的结论，\(G'\)最大流最多可以拆分成最多\(|E|\)条增广路径，设这个增广路径序列为\(P\)。那么令\(p\)是这些增广路径中容量最大的一条，那么必定有\(c_f(p)\ge (|f^{\ast}|-|f|)/|E|\)。因为如果这些增广路径的容量都小于\((|f^{\ast}|-|f|)/|E|\)，那么它们的容量之和就小于\(|f^{\ast}|-|f|\)，这和\(G'\)的最大流是\(|f^{\ast}|-|f|\)是矛盾的。因此原结论得证。

d

由于原来的流是\(f_{i-1}\)，对其使用最宽增广路径\(p\)进行扩增，得到\(f_i\)。因此根据引理24.1，\(|f_i|=|f_{i-1}|+c_f(p)\)。代入题目24-6-c的结论，得到\(|f_i|-|f_{i-1}|\ge (|f^{\ast}|-|f_{i-1}|)/|E|\)。因此可以得到\(|f_i|\ge (1-1/|E|)|f_{i-1}|+|f^{\ast}|/|E|\)

接下来使用归纳法进行证明本题结论。

当\(i=0\)时，可以验证不等式两侧的值均为\(|f^{\ast}|\)，因此原结论成立。

当\(i>0\)时，假设对于\(j=0,1,2,\dots,i-1\)，都满足\(|f^{\ast}|-|f_{j}|\le|f^{\ast}|(1-1/|E|)^j\)均成立。那么考虑缩放\(|f^{\ast}|-|f_i|\)的值，有

\(\begin{aligned} |f^{\ast}|-|f_i|&\le |f^{\ast}| -((1-1/|E|)|f_{i-1}|+|f^{\ast}|/|E|)\\ &=(1-1/|E|)|f^{\ast}| - (1-1/|E|)|f_{i-1}|\\ &=(1-1/|E|)(|f^{\ast}|-|f_{i-1}|)\\ &\le (1-1/|E|)\cdot |f^{\ast}|(1-1/|E|)^{i-1}\\ &=|f^{\ast}|(1-1/|E|)^{i} \end{aligned}\)

因此，原结论得证。

e

使用题目24-6-d的结论\(|f^{\ast}|-|f_{i}|< |f^{\ast}|(1-1/|E|)^i\)，结合证明\(1-1/|E|\le e^{-1/|E|}\)，即可得证\(|f^{\ast}|-|f_{i}|< |f^{\ast}| e^{-i/|E|}\)。

接下来证明\(1-1/|E|\le e^{-1/|E|}\)，只需要从方程3.14中，令\(x=-1/|E|\)即可导出此式，因此原结论成立。

f

令\(i_0=|E|\ln |f^{\ast}|\)，那么从题目24-6-e的结论可以得到：

\(\begin{aligned} |f^{\ast}|-|f_{i_0}|&< |f^{\ast}| e^{-i_0/|E|}\\ &=|f^{\ast}| e^{-\ln |f^{\ast}|}\\ &=1 \end{aligned}\)

由于容量\(c\)都是整数，因此按照定理24.10，使用Ford-Fulkerson方法计算出的\(|f_{i_0}|\)一定是一个整数，那么按照上面的约束，得到\(|f_{i_0}|=|f^{\ast}|\)，此时\(f_{i_0}\)是一个最大流。也就是说，对原始空流增广至多\(i_0=|E|\ln |f^{\ast}|\)次后，得到的流是最大流。

24-7

为求方便，本题将多重边\((u,v)\)转化成一个权值\(w(u,v)\)来表示。即如果原图\(G'=(V,E')\)中，有\(k(k>0)\)条无向边\((u,v)\)，那么在图\(G=(V,E)\)中，有一条无向边\((u,v)\)，且有边权函数\(w(u,v)=k\)。

a

该题目和24.2-11一致，区别在于当前的图\(G\)是多重图，枚举\(G\)中每一对节点\((s,t)\)，其中一个座位源点，另一个作为汇点，将\(G\)中的每一条无向边都替换成一对容量均为\(c(u,v)\)的反平行边。接下来只需要对这个构造出来的流网络求解最大流（也就是这个流网络的最小割），那么求出来的值中，最小的一个恰好为答案。

由于枚举的点对有\(\dbinom{|V|}{2}\)个，因此相当于解决\(\dbinom{|V|}{2}\)个最大流问题。大概过程由GLOBAL-MINIMUM-CUT-NAIVE给出。

GLOBAL-MINIMUM-CUT-NAIVE(G, c)
  Let V, E be new sets
  V = G.V
  for each edge (u, v) ∈ G.E
    Let x be a new vertex
    INSERT(V, x)
    INSERT(E, (u, v))
    (u, v).c_f = c(u, v)
    INSERT(E, (v, x))
    (v, x).c_f = c(u, v)
    INSERT(E, (x, u))
    (x, u).c_f = c(u, v)
  mu = ∞
  for each vertex s ∈ G.V
    for each vertex t ∈ G.V - {s}
      if s < t
        // 避免t作为汇点，s作为源点的情况。
        Let G' = (V, E) be a new flow net work
        FORD-FULKERSON(G', s, t)
        mu = min{mu, |f|}
  return mu

b

该题目和24.2-11一致，区别同样在于当前的\(G\)是多重图。一个无向图\(G=(V,E)\)不连通意味着：\(\forall u\in V,\exists v\in V\)，使得从\(u\)节点不可到达\(v\)节点。因此，我们可以随机选定\(V\)中的一个节点作为源点\(s\)，枚举所有\(t\in V-\{s\}\)作为汇点，并且将\(G\)中的每一条无向边都替换成一对容量均为\(c(u,v)\)的反平行边。接下来只需要对这个构造出来的流网络求解最大流（也就是这个流网络的最小割），那么求出来的值中，最小的一个恰好为答案。具体过程由GLOBAL-MINIMUM-CUT-NAIVE'给出。

GLOBAL-MINIMUM-CUT-NAIVE'(G, c)
  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 = c(u, v)
    INSERT(E, (v, x))
    (v, x).c_f = c(u, v)
    INSERT(E, (x, u))
    (x, u).c_f = c(u, v)
  mu = ∞
  for each vertex t ∈ G.V - {s}
    Let G' = (V, E) be a new flow net work
    FORD-FULKERSON(G', s, t)
    mu = min{mu, |f|}
  return mu

由于这里相当于解决了\(|V|-1\)个最大流问题，每个最大流问题需要花费\(O(VE^2)\)的时间，因此这个算法的时间复杂度为\((|V|-1)\cdot O(VE^2)=O(V^2E^2)\)。

c

题目应该想证明的是\(\mu(G/(u,v))\ge \mu(G)\)。

我们首先证明，对于\(G\)中某一条边\((u,v)\)进行收缩后得到图\(G'=G/(u,v)\)。在图\(G/(u,v)\)中的每个割\(C'\)，都能在\(G\)中找到一个对应的割\(C\)，使得\(|C'|\ge |C|\)，从而证明\(\mu(G/(u,v))\ge \mu(G)\)成立。

对于\(G'\)中的每一个割\((S',T')\)，考虑如下一个关于\(G\)的割\((S,T)\)：对于\(\forall w\in V-\{u,v\}\)，如果\(w\in S'\)，那么\(w\in S\)，否则\(w\in T\)。不失一般性，假设\(x\in S'\)。接下来考虑\(u,v\)所处的集合。

如果\(u\in S,v\in S\)，那么说明上式的等号成立。因此原结论\(\mu(G/(u,v))\ge \mu(G)\)成立。

当\((u,v)\)是\(G\)中所有全局最小割的共同边时，那么满足\(\mu(G/(u,v))>\mu(G)\)。

d

由于\(G\)的全局最小割至少为\(\mu(G)\)，因此对于所有节点\(v\in V\)，它们的度数都至少为\(\mu(G)\)（这意味着如果\(\exists v\in V\)，使得节点\(v\)的度数小于\(\mu (G)\)，那么\((\{v\},V-\{v\})\)是一个小于\(\mu(G)\)的割，与\(\mu\)的定义矛盾）。因此最终有\(\mu(G)\cdot |V|\le 2|E|\)，从而得到\(\mu(G)\le 2|E|/|V|\)。

e

对于其中某个特定的全局最小割\(C\)，一共有\(\mu(G)\)条边，即\(|C|=\mu(G)\)。从这\(|E|\)条边均匀随机选择出一条属于\(C\)的边的概率为\(\dfrac{\mu(G)}{|E|}\)。按照题目24-7-d的结论，有\(\dfrac{\mu(G)}{|E|}\le \dfrac{2}{|V|}\)，因此原结论得证。

f

接下来在算法的每一轮中，都会随机选择一条边，将两个节点合并成一个节点。也就是说，进行合并一次操作中，节点数将会减少\(1\)。

如果最终最小割\(C\)中的所有边都得以保留下来，那么接下来在这\(n-1\)轮迭代中，最小割\(C\)的这\(|C|\)条边都不允许被选到。令事件\(A_i(1\le i<n-1)\)表示，在第\(i\)轮迭代选择的边是不属于\(C\)中的边。在前\(i-1\)轮都没有选中\(C\)中的边的情况下，第\(i\)轮也没有选中最小割的边的事件为\(\displaystyle{A_i|\bigcap_{j=1}^{i-1} A_j}\)。在第\(i\)轮迭代中，迭代前一共有\(|V|-i+1\)个节点，因此按照题目24-7-e的结论，有\(\displaystyle{\Pr\left\{A_i|\bigcap_{j=1}^{i-1} A_j\right\}}\ge 1-\dfrac{2}{|V|-i+1}\)。

由于原图\(G\)的最小割不一定只有\(C\)，因此有\(\Pr\{\mu(G)=c(u,v)\}\ge \Pr\{\mu(G)=c(u,v)\land \text{the minimum cut is } C\}\)。因此可以得到

\(\begin{aligned} \Pr\{\mu(G)=c(u,v)\}&\ge \Pr\{\mu(G)=c(u,v)\land \text{the minimum cut is } C\}\\ &=\Pr\left\{\bigcap_{i=1}^{|V|-2} A_i\right\}\\ &=\Pr\{A_1\}\cdot \prod_{i=2}^{|V|-2} \Pr\left\{A_i|\bigcap_{j=1}^{i-1} A_j\right\}\\ &\ge\prod_{i=1}^{|V|-2}\left(1-\dfrac{2}{|V|-i+1}\right)\\ &=\prod_{i=0}^{|V|-3}\dfrac{|V|-i-2}{|V|-i}\\ &=\dfrac{2}{|V|(|V|-1)}\\ &=1/\dbinom{|V|}{2}\\ \end{aligned}\)

因此得到\(\Pr\{\mu(G)=c(u,v)\}=\Omega\left(1/\dbinom{|V|}{2}\right)\)。

g

按照题目24-7-f的结论，求解一次最小割失败的概率至多为\(1-1/\dbinom{|V|}{2}\)。假设\(p\)为按照题目中所提供的算法重复求取\(\dbinom{|V|}{2} \ln|V|\)次全局割后，没有一个是全局最小割的概率。那么考虑\(p\)值，有

\(\begin{aligned} p&\le \left(1-1/\dbinom{|V|}{2}\right)^{\binom{|V|}{2}\ln |V|}\\ &<\left(\dfrac{1}{e}\right)^{\ln |V|}&\qquad(A)\\ &\le \dfrac{1}{|V|} \end{aligned}\)

其中。步骤\((A)\)是基于如下事实：\(\forall x>0,\left(1-\dfrac{1}{x}\right)^x<\dfrac{1}{e}\)。

从而得知，这个算法能够成功求取一个最小割的概率为\(1-p\)，即以至少\(1-1/|V|\)的概率至少求出一个最小割。

h

在每一次循环中，以\(O(1)\)的时间选好边\((u,v)\)后，需要花费\(O(V)\)的时间来用新节点\(x\)关联原本和\(u,v\)关联的所有节点。并且维护好边数函数\(c\)。

由于需要进行\(|V|-2\)次循环才能将\(|V|\)个顶点缩减成\(2\)个顶点，因此产生一个全局割的时间复杂度为\(V\cdot O(V)=O(V^2)\)。具体过程由GEN-GLOBAL-CUT给出。

GEN-GLOBAL-CUT(G, c)
  n = |G.V|
  for i = 1 to n - 2
    select edge (u, v) from E randomly weighted by c
    c(u, v) = 0
    let x be a new vertex
    INSERT(G.V, x)
    for each w in G.Adj[u]
      if w != v
        INSERT(G.Adj[x], w)
        c(x, w) = c(x, w) + c(u, w)
        c(u, w) = 0
        replace u in G.Adj[w] by x
      else
        DELETE(G.Adj[u], w)
    
    for each w in G.Adj[v]
      if w != u
        INSERT(G.Adj[x], w)
        c(x, w) = c(x, w) + c(v, w)
        c(v, w) = 0
        replace v in G.Adj[w] by x
      else
        DELETE(G.Adj[v], w)

    DELETE(G.V, u)
    DELETE(G.V, v)    
  
  return c

i

按照题目24-7-g的结论，哪怕是图\(G\)的全局最小割不唯一，只需要按照24-7-h的算法求出\(|V|^2\ln |V|\)个全局割后，至少有\(1-1/|V|\)的概率找到\(1\)个全局最小割。然而，题目24.7-h求取一个全局割的时间复杂度为\(O(V^2)\)。最终，这个算法可以在时间\(O|V|^2\ln |V|\cdot O(V^2)=O(V^4\lg V)\)以内，以至少\(1-1/|V|\)的概率求出一个全局最小割。