Problem 22-4

1. Transpose G into G’
2. DFS in G’ from minimum number.

If u is reachable from v in G’, then v is reachable from u in G. Since we start the DFS with minimum number, we can find the minimum node which is reachable from u.

Problem 22-3

It is a classical problem in graph theory. It is called Fleury’s algorithm. See reference.

Problem 22-2

This is the classical problem in graph theory. See reference.

Problem 22-1

Exercises 22.5-7

1. Construct component graph.
2. Topological sort
3. Check whether it has a linear chain, if yes then return “Yes”.

The running time is O(|V|+|E|).
If u and v are in the same component, then there is a path from u to v. If u and v are in different component, since the component graph is a linear chain. There is one path from u to v or v to u.

Exercises 22.5-6

We can reduce the subgraph in one component to a cycle. Then this graph has the same component graph and has fewest edges.

Exercises 22.5-5

In the SCC’s algorithm, we can compute the component’s numbering. Then we can find all edges which endpoints are in different components. These edges are the edges in the component graph. But the graph is not simple graph, we must transform it into simple graph.

Exercises 22.5-4

G’s transpose’s component graph, is G’s component graph’s transpose. Hence they are equivalent.

Exercises 22.5-3

Incorrect. Let G=(V,E), V={0,1,2}, E={<0,1>,<0,2>,<1,0>}. If we start DFS with node 0, then the result is incorrect.

Exercises 22.5-2