|
Post by vsiap on Nov 22, 2014 16:45:25 GMT
The hardest part of this exercise is figuring out what we need to prove. It is enough to prove that if the strong components of u and v are not disjoint then they are the same. So suppose that w is a vertex that is in both the strong component of u and the strong component of v. (It is enough to consider the vertices in these components, because the edges in a strong component are just all the edges joining the vertices in that component.) This means that there are directed paths (in each direction) between u and w and between v and w. It follows that there are directed paths from u to v and from v to u, via w. Suppose x is a vertex in the strong component of u. Then x is also in the strong component of v, because there is a path from x to v (namely the path from x to u followed by the path from u to v) and vice versa.
|
|