Post by vsiap on Nov 22, 2014 16:26:53 GMT
In each case we want to look for large sets of vertices all which of which have paths to all the others. For these graphs, this can be done by inspection. These will be the strongly connected components.
a) Clearly {a,b,f} is a set of vertices with paths between all the vertices in the set. The same can be said of {c,d,e}. Every edge between a vertex in the first set and a vertex in the second set is directed from the first, to the second. Hence there are no paths from c, d, or e to a, b, or f , and therefore these vertices are not in the same strongly connected component. Therefore these two sets are the strongly connected component.
b) The circuits a, e, d, c, b, a and a, e, d, h, a show that these six vertices are all in the same component. There is no path from f to any of these vertices, and no path from g to any other vertex. Therefore f and g are not in the same strong component as any other vertex. Therefore the strongly connected components are {a,b,c,d,e,h}, {f}, and {g}.
c) It is clear that a and i are in the same strongly connected component. If we look hard, we can also find the circuit b, h, f, g, d, e, d, b, so these vertices are in the same strongly connected component. Because of edges ig and hi, we can get from either of these collections to the other. Thus {a,b,d,e,f,g,h,i} is a strong component. We cannot travel from c to any other vertex, so c is in a component by itself.
a) Clearly {a,b,f} is a set of vertices with paths between all the vertices in the set. The same can be said of {c,d,e}. Every edge between a vertex in the first set and a vertex in the second set is directed from the first, to the second. Hence there are no paths from c, d, or e to a, b, or f , and therefore these vertices are not in the same strongly connected component. Therefore these two sets are the strongly connected component.
b) The circuits a, e, d, c, b, a and a, e, d, h, a show that these six vertices are all in the same component. There is no path from f to any of these vertices, and no path from g to any other vertex. Therefore f and g are not in the same strong component as any other vertex. Therefore the strongly connected components are {a,b,c,d,e,h}, {f}, and {g}.
c) It is clear that a and i are in the same strongly connected component. If we look hard, we can also find the circuit b, h, f, g, d, e, d, b, so these vertices are in the same strongly connected component. Because of edges ig and hi, we can get from either of these collections to the other. Thus {a,b,d,e,f,g,h,i} is a strong component. We cannot travel from c to any other vertex, so c is in a component by itself.