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

Ex:Consider the following graph g






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

If I reverse the above graph (i.e)






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)

  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Oct 25 '14 at 8:29
  • $\begingroup$ You got the SCC of $G$ wrong. $\endgroup$ – FrankW Oct 25 '14 at 8:30

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.