注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。‘ ## 8.2 + 所有点染成白色 + 对于每一个调用如图算法
本题要注意顶点出栈的时机，以保证染色的行为和递归实现是一致的。染色行为如下： + 顶点白色表示之前未访问过 + 顶点灰色表示访问到了，但是子节点还未访问完 + 顶点黑色表示以该顶点出发的深度遍历子树都已经访问完了
8.5
8.7
- 强连通片是极大的强连通子图（不是任何强连通片的真子图）
- 假设收缩图有环，则环上的任意两个强连通片之间的任意两个顶点相互可达
- 则环上所有的强连通片构成了一个更大的强连通片，矛盾
- 故有向图的收缩图是无环的
8.8
- 先复习并理解好SCC算法
- 收缩图是无环的
- 强连通算法的本质是希望找到收缩图的最下游，从最下游出发，按任意规则，遍历到的就是一个强连通片
- DFS算法，当完成节点的遍历时把节点压入栈，此时栈顶节点一定在收缩图中最上游的强连通片中（反证法，思考为什么）
- 对于转置图，栈顶节点一定在转置图的收缩图的最下游的强连通片中！
因此本题答案如下： + 第一次DFS不能换成BFS，因为需要找到收缩图的最上游或者最下游。DFS是在顶点所在子树全部遍历完成后再进栈，此时栈顶自然是栈中最上游的；BFS是在顶点的孩子进队列后就可以进栈，此时该顶点的孩子还没有进栈，栈顶可能是栈中其他某个顶点的孩子，故栈顶不是最上游（而且也不一定是最下游，比如先对下游的顶点BFS，再对上游的顶点BFS）。 + 第二次DFS可以换成BFS，因为只确定能遍历到的顶点即可，任何遍历规则都可以。
8.9
v是割点的充要条件是v的深度优先遍历树有至少两个子节点a,b + 充分性：已知v的dfs树有至少两个子节点，则删除v后,a和b之间没路径。反设a和b存在不经过v的路径，则dfs建树时a和b将在v的同一个子树中，矛盾。故v是割点。 + 必要性：已知v是割点，显然v的深度优先遍历树不可能没有子节点，否则v不是割点。那么反设v的深度优先遍历树只有一个子节点，删去v之后剩下的图还是连通图，矛盾。故v的深度优先遍历树至少有两个子节点。
8.10
- 仍然正确。
- 原算法是课本的96页的算法27。
- 证明方法还是按95页的定理8.5的证明
8.11
引理8.9证明
: 已知uv是桥，则删去该边，图中存在两个点a,b不连通。现在要证以v为根的子树中没有BE指向v的祖先（包括u）。反设存在BE指向v的祖先。则断开uv以后，图上任意点都和root有路径。则a和b连通，故矛盾。 : 已知以v为根的子树中没有BE指向v的祖先，则删去uv边之后，uv不再连通。故uv是桥
定理8.6证明
根据引理8.9，即证明从TE uv回退时，如果v.back>u.discoverTime，则以v为根的子树中没有BE指向v的祖先（包括u）。反证法证明：根据back值的更新方法，反设以v为根的子树中存在BE指向v的祖先，则v的祖先的discoverTime会被赋值给以v为子树的某个节点的back值，并且随着遍历结束的回退过程，这一discoverTime会以back变量的方式传递到v.back。由于祖先节点具有更小的discoverTime，所以这样一条BE存在，则v.back一定小于v.discoverTime（即v.back小于等于u.discoverTime），矛盾。
补充说明： + 课本的关于割点的证明（95页），实际上是逆否证法，证明其逆否问题，这里我们用反证法 + 把97页的算法28的第9行，v.back>u.discoverTime替换为v.back>=v.discoverTime，再和算法27的第8行进行比较，发现了什么。
8.14
- 最外层for循环，遍历每个白色的顶点
- 循环体中第一次dfs找BE，若找不到则算法返回无解；若找到则以BE的任意端点作为顶点进行第二次dfs，遍历边时进行定向。
- 每个顶点最多访问2次，复杂度线性。
算法正确性 + 若没有BE，则边数小于点数，入度必然小于点数，不可能定向成功 + 若有BE，则非根节点的入边来自于父亲，根节点的入边来自于BE
8.15
(1)
因为G中存在桥，则桥去掉后图中产生两个连通分支，桥这个边只能进行一种定向，故无论怎么定向，两个连通分支都不可能相互能到达。
(2)
从任意节点开始进行DFS即可，DFS访问边的方向即为边的定向，复杂度线性。
证明没有桥的图，按上述方法可以得到一个SCC定向，即定向图强连通。 + 对于原无向图的DFS树，只有TE和BE。对于定向后的图中任何一个顶点，都有BE直连到根，否则根连向这个顶点所在子树的边，在无向图中是割边。 + 故定向图任意顶点能到达根节点，故定向图强连通。
8.19
- 找入度为0的顶点，即找源点，也就是最上游的顶点。
- 回忆找强连通片的SCC算法，可以用一遍DFS，在节点遍历完成时入栈，则在压缩图中，栈顶的节点一定不在栈中任何其他节点的下游。
- 对于有向无环图，压缩图就是本身，为什么。
- 故该方法，找度为0的点来拓扑排序，本质上和书上的一遍DFS加栈结构进行拓扑排序有着相同的原理。
- 对于书上dfs的方法，若图中有回路，则DFS时会发现BE。
- 对于该方法，若图中有回路，算法结束后会出现非空的无法继续删除的子图。
- 复杂度线性
8.20
(1)
以该点为根进行深度优先搜索即可，搜索结束时若有没搜到的节点，则不能到达其他所有节点，反之可以。
(2)
- dfs和栈结构，找到一个最上游的节点，即该节点在压缩图中的入度为0。
- 对该点调用第一问的方法。
- 复杂度线性。
8.22
- 两次dfs计算压缩图
- 压缩图中每个点的权重为该点所对应原图的强连通片的顶点数
- 压缩图中每个点的影响力为该点在压缩图中能到达的顶点的权重之和（包括自己），用dfs框架计算
- 压缩图中影响力最小的点对应原图的强连通片，该强连通片中都是影响力最小的点
- 压缩图中影响力最大的点对应原图的强连通片，该强连通片中都是影响力最大的点
8.24
- 遍历一遍图中的边，找到入度为0的点，加入到第一个学期的课程集合
- 如果已知当前学期的课程，下学期的课程按如下方式确定
- 对于当前学期的所有点，遍历其邻居，删除对应的边（一定是出边，因为已经没有入边了），并把该邻居的入度减1
- 若某邻居的入度减为0，则将其加入到下学期的课程集合中
- 算法复杂度为线性，因为找第一个学期的课程需要O(V)，后续操作中每个边会且只会被删一次，即O(E)
此外也有同学使用了关键路径的方法，也是可以的。
8.26
(1)
- 如果a恨b，则a要放在b前面；如果a是b的先修课则a要放在b前面。我们发现本小问思路类似于8.24
- 遍历一遍图中的边，找到入度为0的点，加入到候选队首集合中（集合中的元素都可以作为队首，因为不被人恨）。
- 接下来进行循环，循环的每次任意从候选队首集合中确定一个队首，并且需要删除该点的所有边（一定是出边），并更新这些出边对应的端点的入度
- 如果某个顶点的入度更新为0，则加入候选队首集合中。
- 如果候选队首集合为空集，而还有顶点未排入队伍，则输出不存在符合条件的排队方法
- 如果候选队首集合为空集，且所有顶点都入了队伍，则输出排队结果。
- 如果候选队首集合不为空集，则继续下了一轮循环
- 复杂度O(V+E)，理由同8.24。
(2)
- 遍历一遍图中的边，找到入度为0的点，加入到候选队首集合中（集合中的元素都可以放在第一行，因为不被人恨）。
- 接下来进行循环，循环的每次将候选队首集合中所有顶点放在第一排，并且需要删除各个点的所有边（一定是出边），并更新这些出边对应的端点的入度
- 如果某个顶点的入度更新为0，则加入候选队首集合中。
- 如果候选队首集合为空集，而还有顶点未排入队伍，则输出不存在符合条件的排队方法
- 如果候选队首集合为空集，且所有顶点都入了队伍，则输出排队结果。
- 如果候选队首集合不为空集，则继续下了一轮循环
- 复杂度O(V+E)，理由同8.24。
8.28
(1)
(2)
答案不唯一，例如：
(3)
按定义画图即可
(4)
图中的边表示着布尔变量间的蕴涵关系，有传递性。假设有一个强连通片同时包含
- 若
为真，则可以按从 到 的路径，推出 为真，矛盾 - 若
为真，则可以按从 到 的路径，推出 为真，矛盾
故无论
(5)
要证明实例I是可满足的，就是要找到一种对每个布尔变量的真假状态的设置，即在图中标记n个顶点（对应于n个变量的真假状态），使得图中每个顶点，其能到达的顶点都是被标记了的。具体算法和正确性的证明见下一问。
(6)
算法：
- 线性时间确定原图的压缩图，SCC算法，得到的是有向无环图
- 设置该图的逆拓扑序，具体来说，在压缩图中，如果a到b有边，则b的逆拓扑序较大。复杂度线性。
- 原图中每个点的序号即其所在强连通片的逆拓扑序
- 最后遍历一遍每个布尔变量，确定其真假状态
- 如果该布尔变量的真和假对应的点的序号相同，代表其真假状态出现在了同一个强连通片中，此时输出无解。
- 否则把该布尔变量真和假对应的点的序号中较大的那个点进行标记。
复杂度和正确性：
- 复杂度是线性的显然
- 对于每个布尔变量，在最后遍历的时候都确定其要么为真要么为假，现在就是要证明该实例就是满足条件的。
- 即证明对于图中每个标记的顶点，其能到达的顶点都是标记的
- 不失一般性的，反设存在点
和 被标记，而 和 没有被标记，且 可到达 ，由逆否性质， 必然到达 。 - 因为被标记的点的序号较大，故
的序号大于 。 - 因为
可由 到达，故 序号大于等于 - 因为被标记的点的序号较大，故
的序号大于 。 - 因为
可由 到达，故 序号大于等于 序号大于 序号，故矛盾
- 因为被标记的点的序号较大，故
- 由此证明按该算法，能在线性时间能对每个布尔变量设置真假，并且是没有冲突的合法设置。
