9.1
- 反设在遍历v点时发现BE，连向黑色的节点w，则之前在bfs中，队列弹出w时，会发现v为w的未访问过的邻居，则之前的BE实际上是TE的二次遍历，矛盾。
- 反设在遍历v点时发现DE，连向遍历树中v的后继节点w，但v的后继节点在v刚出队列时必然都是白色节点，即未被访问过。此时该DE实际上还是TE，在遍历树中，w是v的孩子，矛盾。
9.2
不成立，反例：五边形。不唯一。
9.3
DFS可以判断是否为二部图。 优劣分析的答案比较开放，有理即可，参考回答如下： + dfs不需要队列的空间开销；更适合深度大，节点度数小的图。 + bfs不需要进行递归；更适合深度小，节点度数大的图。
9.4
- DFS
- 有向图，遇到灰色节点（BE）
- 无向图，遇到灰色节点（BE）
- BFS
- 有向图，发现黑色的祖先（BE），但注意发现邻居是黑色节点不一定代表遇到BE，也可能是CE，还要额外检查是不是祖先。
- 无向图，遇到灰色节点（CE）
答案中只需要给出：DFS检测有向图的环、BFS检测无向图的环即可。
9.5
判断是否能去掉一条边，使得图还连通，本质就是无向图找环。 + DFS发现灰色邻居，即BE，则返回True；找不到则返回False + BFS发现灰色邻居，即CE，则返回True；找不到则返回False
复杂度都是O(V)，但怎么证明？ + 无向图的DFS只有TE和BE，BFS只有TE和CE + 算法没停止，说明遍历的点都是白色的邻居，边都是TE。 + O(V+E)=O(2V)=O(V)
也有同学在课本找桥的算法基础上修改，也是可以的。注意说明复杂度。
9.8
(1)
深度优先遍历树或宽度优先遍历树就是最小生成树
(2)
- BFS找无向图的圈，9.5问已经说明过，线性代价
- 删除圈上权重最大的边，此时不改变图的连通性，线性代价
- 将上述两个步骤重复11次，即删除11条边，剩下的边数m是点数减1，此连通图即最小生成树
- 复杂度线性
(3)
- 首先只考虑权重为1的边，用BFS框架进行遍历，得到宽度优先遍历森林。如果森林中只有一颗树，则该树就是原图的最小生成树，开销线性。
- 否则构造一个新图，对森林的每棵树初始化一个顶点。遍历权重为2的边，如果边的两端点不在森林的同一颗树上，则把这两颗树所对应的新图的两个顶点之间连上权重为1的边，并记录该边对应哪一条权重为2的边（如果对应多条，只需要记录其中一条）。开销线性。
- 用BFS框架遍历该新图，得到新图的最小生成树。开销线性。
- 宽度优先遍历森林的所有边（权重为1）在最小生成树上。
- 新图的最小生成树上的边所对应的（权重为2）边在最小生成树上。
- 总时间开销是线性的。
9.11
- 根据相识关系构造无向图，顶点表示候选的被邀请人，边表示两者相识
- 修改109页的求5度子图的算法5-DEGGREE-SUBGRAPH（简称5DS），原本删除点方式是，该点度小于5则删去，现在删除方式是，该点在原图的度小于5或在补图的度小于5都需要删去。
- 在第7-10行关于邻点的处理完成后还要再进行非邻点的处理。
- 算法复杂度是O(V^2)的。
- 注意，有同学串行的进行对原图和补图求五度子图是不对的，因为对补图删点后，原图可能不一定还满足五度子图的条件。
