If you want to make money online : Register now

[Solved]: Strongly connected components in graph

, , No Comments
Problem Detail: 

Statement:SCC in G is same as Rev(G)

Ex:Consider the following graph g

0->1

1->2

2->4

3->1

4->3

The strong components set would be S={0,1,2,3,4}

If I reverse the above graph (i.e)

1->0

1->3

2->1

3->4

4->2

Then the strong components set would be S'1={0} S'2={1,2,3,4}

Which shows that strong components in G is not same as strong components in Rev(g)

Asked By : vikiyouvb

Answered By : Hoopje

In a strongly connected component of a graph, all nodes of the SCC must be reachable from all other nodes in the SCC. So, if $x$ and $y$ are nodes of the SCC, then there is a path from $x$ to $y$ and a path from $y$ to $x$. Clearly, if we reverse all edges in the graph, then there is still a path from $x$ to $y$ (the old path from $y$ to $x$) and still a path from $y$ to $x$ (the old path from $x$ to $y$).

Your mistake in determining the SCCs of the first graph $G$: there is no edge going into node $0$, thus $0$ is not reachable from any of the other nodes. Therefore the SCCs of $G$ are $\{0\}$ and $\{1,2,3,4\}$, which are also the SCCs of $\mathit{Rev}(G)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32291

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback