Let $G$ be an arbitrary directed graph. Does $G$ always have the same strongly connected components on $G$ as on $G^*$? Here, $G^*$ is the inverted graph of $G$ (i.e., $(u,v)\in E \rightarrow (v,u) \in E^*$).

I'm thinking yes because otherwise the algorithm of Kosaraju would not work at all? But do not have another explanation for this.

  • 2
    $\begingroup$ Have you tried proving your suspicion? Try using the definition of strongly connected component. $\endgroup$ – Yuval Filmus Aug 20 '19 at 20:29
  • 1
    $\begingroup$ Your title said the graph is regular but the question says it's arbitrary. I deleted "regular" from the title, since requiring th graph to be regular doesn't change the answer. $\endgroup$ – David Richerby Aug 21 '19 at 9:19

Two vertices $x,y$ lie in the same strongly connected component if there is a directed path from $x$ to $y$ and a directed path from $y$ to $x$.

There is a directed path from $x$ to $y$ in $G$ iff there is one from $y$ to $x$ in $G^*$. This easily implies that $G$ and $G^*$ have the same strongly connected components.


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.