
Post by vsiap on Nov 22, 2014 16:07:05 GMT
a) The cycle b,a,e,b guarantees that these three vertices are in one strongly connected component. Since there is no path from c to any other vertex, and there is no path from any other vertex to d, these two vertices are in strong components by themselves. Therefore the strongly connected components are {a,b,e}, {c}, and {d}.
b) The cycle c,d,e,c guarantees that these three vertices are in one strongly connected component. The vertices a, b, and f are in strong components by themselves, since there are no paths both to and from each of these to every other vertex. Therefore the strongly connected components are {a}, {b} {c,d,e}, and {f}.
c) The cycle a,b,c,d,f,g,h,i,a guarantees that these eight vertices are in one strongly connected component. Since there is no path from e to any other vertex, this vertex is in a strong component by itself. Therefore the strongly connected components are {a,b,c,d,f,g,h,i} and {e}. Notice that, for instance, {a,b,h,i} is not a strongly component since this subgraph is contained in larger strongly connected subgraph, that is, the maximal strongly connected subgraph {a,b,c,d,f,g,h,i}.

