算法导论20.5 Exercises 答案

发表于 2023-04-24 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 2.6k 阅读时长 ≈ 2 分钟

20.5-1

增加一条边会使得图\(G\)中的强连通数量减少或者不变。

不变时有\(3\)种情况：

这条边被加在了强连通分量内部。
\(u\in C_i,v\in C_j\)，并且从\(u\)到\(v\)已经有一条路径。
\(u\in C_i,v\in C_j\)，并且\(C_i\)和\(C_j\)在\(G^{SCC}\)对应的\(v_i,v_j\)没有特定的拓扑序。

减少时有\(1\)种情况：

\(u\in C_i,v\in C_j\)，并且\(C_j\)中的所有点都可以到达\(C_i\)。这条边被加入后，从\(C_i\)到\(C_j\)中的所有强连通分量都会被合并成一个强连通分量。

20.5-2

题目20.3-2给出了如下关于图\(G\)的遍历信息：

\(\begin{array}{|l|l|l|}\hline v&v.d&v.f\\ \hline q&1&16\\ \hline r&17&20\\ \hline s&2&7\\ \hline t&8&15\\ \hline u&18&19\\ \hline v&3&6\\ \hline w&4&5\\ \hline x&9&12\\ \hline y&13&14\\ \hline z&10&11\\ \hline \end{array}\)

到此完成了算法STRONGLY-CONNECTED-COMPONENTS的第\(1\)行。接下来则是按照完成时间从大到小遍历\(G^T\)的每个强连通分量：\((r),(u),(q,y,t),(x,z),(s,w,v)\)。

20.5-3

如果\(G\)中有两个强连通\(C_1,C_2\)，并且\(C_1\)中的节点有通过\(C_2\)的节点，那么如果遍历时\(C_1\)中有节点已经完成，那么在第二次DFS的过程将会导致\(C_1\)与\(C_2\)被合并在一起。

具体而言，令\(G=(V,E),V=\{a,b,c\},E=\{(a,b),(b,a),(b,c)\}\)，可以知道两个强连通分量分别为\((a,b),(c)\)。如图所示：

如果第1次DFS按照\(b,a,c\)的顺序遍历这个图，那么\(a\)最先完成。在第二次DFS中，强连通分量\(\{a,b\}\)最先被遍历，由于\(\{c\}\)仍未遍历，因此第2次DFS将会合并这2个强连通分量，从而得出错误的解。

20.5-4

对于两个图\(G\)和其转置\(G^T\)，按照SCC的定义，\(u,v\)同属一个强连通分量当且仅当\(u,v\)相互可达，这在两个图中是显而易见的，因此有\((V^T)^{GCC}=V^{GCC}\)。转置操作不会影响点集的变化，因此有\(((V^T)^{GCC})^T=V^{GCC}\)。

接下来证明\(((E^T)^{GCC})^T=E^{GCC}\)，对于\(\forall (v_i,v_j)\in((E^T)^{GCC})^T\)，可以知道\((v_j,v_i)\in (E^T)^{GCC}\)。也就是说，如果\(v\in C_j ,u\in C_i\)，那么有\((v,u)\in E^T\)，也就是有\((u,v)\in E\)。因此有\((v_i,v_j)\in E^{GCC}\)，即\(((E^T)^{GCC})^T=E^{GCC}\)。

因此可以得出，\(((G^T)^{GCC})^T=G^{GCC}\)。

20.5-5

最简便的做法是，先使用算法STRONGLY-CONNECTED-COMPONENTS'为图\(G\)的每个节点\(u\)生成一个scc属性，表示\(u\)所在的强连通分量。然后再枚举\(E\)中的每一条边\(e\)，通过scc属性转化成边\(e_{SCC}\)，再将其存在一个集合中即可（基于哈希表实现）。整个过程将会达到\(O(V+E)\)的时间复杂度。这个算法由GEN-COMPONENT-GRAPH给出。

// 假设算法STRONGLY-CONNECTED-COMPONENTS'(G) 对图$G$中的所有节点都附带上了一个属性scc，表示它所属的强连通分量。

GEN-COMPONENT-GRAPH(G)
  STRONGLY-CONNECTED-COMPONENTS'(G)
  let V, E be hash-sets
  for each u in G.V
    for each v in G.Adj[u]
      if u.scc != v.scc
        INSERT(E, (u.scc, v.scc))
    INSERT(V, u.scc)
  return V, E

20.5-6

本题的做法与20.5-5类似。为了保证最少的边数，对于强连通分量内部的所有边，先进行删除，然后将内部所有一共\(n\)个节点首尾相接成一个环。而强连通分量之间的边和20.5-5一样，仅保留一条（在\(G\)上保留\(E\)中的边）。这个算法由程序GEN-COMPONENT-GRAPH给出，时间复杂度为\(O(V+E)\)。


// 该算法将L中（强连通分量内部C的所有点串接成一个环，并插入数组E中）
GEN-CYCLE(E, C)
  n = C.size
  for i = 0 to n - 1
    INSERT(E, (C[i], C[(i + 1) % n])) // L是强连通分量内部的所有节点。
GEN-COMPONENT-GRAPH(G)
  STRONGLY-CONNECTED-COMPONENTS'(G)
  let edges be hash-set
  let vscc be hash-map
  let E be new array
  for each u in G.V
    INSERT(vscc[u.scc], u)
    for each v in G.Adj[u]
      if u.scc != v.scc
        if (u.scc, v.scc) not in edges
          INSERT(edges, (u.scc, v.scc))
          INSERT(E, (u, v))
  for each key, value in vscc
    GEN-CYCLE(E, value)
  return G.V, E

20.5-7

我们首先将求出\(G\)的分量图\(G^{SCC}\)，再判断\(G^{SCC}\)是否半连通即可。因为强连通分量内部的所有节点都是相互可达的，内部节点可以视作一个整体。由于\(G^{SCC}\)是一个有向无环图，因此如果它也是一个半连通图，那么\(V^{SCC}\)中的所有节点必须处在同一条“链”上，也就是说，拓扑序列是唯一的。因此我们求出\(G^{SCC}\)的拓扑序列后，判断拓扑序列的相邻两个节点所得到的边是否在\(E^{SCC}\)中即可。这个算法由程序IS-SEMICONNECTED给出，整个过程的时间复杂度为\(O(V+E)\)。

IS-SEMICONNECTED(G)
  H = GEN-COMPONENT-GRAPH(G)
  order = TOPOLOGICAL-SORT(H)
  n = order.size
  for i = 0 to n - 2
    if (order[i], order[i + 1]) not in H.E
      return False
  return True

20.5-8

我们首先将求出\(G\)的分量图\(G^{SCC}\)。由于强连通分量内部节点相互可达，因此只保留强连通分量内部的最大值和最小值，也就是\(\displaystyle{v_{k\max}=\max_{u\in C_k}\{l(u)\},v_{k\min}=\min_{u\in C_k}\{l(u)\}}\)。

那么使用动态规划算法即可完成本题。考虑状态\(f_G(v_k)\)表示在\(G^{SCC}\)中，对于所有能够到达节点\(v_k\)的\(v_{i \min}\)的最小值。那么可以写出\(f_G(v_k)\)的状态转移方程：

\[f_G(v_k)=\min\{v_{k\min},\min_{(v_i,v_k)\in E^{SCC}}\{f_G(v_l)\}\}\]

在计算\(f_G(v_k)\)时，需要先处理好\(G^{SCC}\)的拓扑序列。

那么，最终问题的答案为

\[\max_{v_k\in V^{SCC}}\{v_{k\max}-f_G(v_k)\}\]

整个问题的算法由CAL-MAX-DELTA-L程序给出，其时间复杂度为\(O(V+E)\)。

CAL-MAX-DELTA-L(G)
  H = GEN-COMPONENT-GRAPH(G)
  for each u in H.V
    u.max-l = max{l(v) | v ∈ G.V, v.scc = u}
    u.f = u.min-l = min{l(v) | v ∈ G.V, v.scc = u}
  ans = -∞
  order = TOPOLOGICAL-SORT(H)
  for u in order
    ans = max{ans, u.max-l - u.f}
    for v in H.Adj[u]
      v.f = min{v.f, u.f}
  return ans