Question

22.5-1

不变或减少

22.5-2

第一次 DFS 结果：

r u q t y x z s v w

G 转置的结果：

q:y

r:

s:q w

t:q

u:r

v:s

w:q v

x:t z

y:r t u

z:x

第二次 DFS 的结果：

r

u

q y t

x z

s w v

22.5-3

简化后的算法不可行，证明如下。

在原算法中，过程总结为这样几步

（1）对图 G 作 DFS，计算每个点的结束时间 f

（2）将结点以 f 递减排序

（3）对图作转置，得到 GT

（4）以 f 递减顺序对 GT 作 DFS

（5）第二次 DFS 后得到的一个树里的点都属于同一个强联通分支

如果以 DFS 后的 f 递减排序，排序的结点有规律呢？

假设 f[u]>f[v]，那么 u 和 v 的关系可能有几下四种情况

（1）u 和 v 互相不可达

（2）u 和 v 互相可达，即在同一个联通分支内

（3）u 到 v 可达 && v 到 u 不可达

（4）u 到 v 不可达 && v 到 u 可达 && (v,u) 不是 G 中的边 && 存在另一个结点 w && w 与 v 在同一个联通分支 && w 到 u 可达 && f[w]>f[u]>f[v]

以下将针对这四种情况做第（3）（4）操作，看是否能得到第（5）的结果

对 G 做 DFS 后，f[u]>f[v]，u 和 v 的关系	在 GT 中 u 和 v 的关系	在 GT 中对 u 做 DFS，v 是否会成为 u 的后继
u 和 v 互相不可达	u 和 v 互相不可达	不会
u 和 v 互相可达，即在同一个联通分支内	u 和 v 互相可达，即在同一个联通分支内	会
u 到 v 可达 && v 到 u 不可达	u 到 v 不可达 && v 到 u 可达	不会
u 到 v 不可达 && v 到 u 可达 && (v,u) 不是 G 中的边 && 存在另一个结点 w && w 与 v 在同一个联通分支 && w 到 u 可达 && f[w]>f[u]>f[v]	u 到 v 可达 && v 到 u 不可达 && (u,v) 不是 G 中的边 && 存在另一个结点 w && w 与 v 在同一个联通分支 && u 到 w 可达	不会。 虽然 u 到 v 可达。但由于 f[w]<f[v]，会先对 w 做 DFS，v 已经是 w 的后继了，所以不会成为 u 的后继

由此可以知道，以 f 递减的顺序对 GT 作 DFS，同一个连通分支的点会到一棵不树上，不是同一个连通分支的点不会到一棵树上。

再看本题的算法过程，总结为以下几步：

（1）对图 G 作 DFS，计算每个点的结束时间 f

（2）将结点以 f 递增排序

（3）以 f 递增的顺序对 GT 作 DFS

（4）第二次 DFS 后得到的一个树里的点都属于同一个强联通分支

与上述步骤类似，我们先分析 f 递增排序后结点的关系，然后针对这些关系做第（3）步，分析是否能得到第（4）步的结果

对 G 做 DFS 后，f[u]<f[v]，u 和 v 的关系	在 G 中对 u 做 DFS，v 是否会成为 u 的后继
u 和 v 互相不可达	不会
u 和 v 互相可达，即在同一个联通分支内	会
u 到 v 不可达 && v 到 u 可达	不会
u 到 v 可达 && v 到 u 不可达 && (u,v) 不是 G 中的边 && 存在另一个结点 w && w 与 u 在同一个联通分支 && w 到 v 可达 && f[w]>f[v]>f[u]	会。 此处不对。u 和 v 不属于同一个联通分支，但 v 会成为 u 的后继

因此该算法不可行。

22.5-5

见 算法导论 22.5-5 O(V+E) 求有向图的分支图

22.5-6

待解决，题目的意思不太懂，网上找了个答案，主要是其中的第四步不懂。

令所求图为 G2，翻译一下：
STEP1：使用 22.5 中的算法计算出所有的强连通分支
STEP2：使用 22.5 中和算法计算出分支图 G|SCC
STEP3：将 G2 的边集初始化为空
STEP4：将每个强连通分支中的顶点构成环。比如强连通分支 a 中有 ea1,ea2,ea3,ea4 这四个顶点，就在 G2 中加入边 ea1->ea2,ea2->ea3,ea3->ea4,ea4->ea1
STEP5：把分支图的边加到 G2 中。比如分支图中有一条强连通分支 a 到强连通分支 b 的边，就在 G2 中加入一条 ea 到 eb 的边。其中 ea 是 a 中的任意一个顶点，eb 是 b 中的任意一个顶点
解释：
强连通分支：

分支图：

G 与 G2 有相同的强连通分支 ===> G2 的顶点与 G 的顶点相同
G 与 G2 有相同的分支图 ===> G2 至少有着 G|SCC 中的边 ===> STEP5
G2 有最小的边 ===> 具有最少边的强连通图是一个环，边的个数与顶点的个数相同 ===> STEP4

22.5-7

STEP1：使用 22.5-5 中的算法得到 SCC。

STEP2：对 SCC 求拓扑序列(v1, v2, ……, vk)

STEP3：若在边 SCC 中存在边(v1,v2),(v2,v3),……,(vk-1,vk)，则图 G 为半连通。