-1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Have you tried proving your suspicion? Try using the definition of strongly connected component. $\endgroup$ Commented Aug 20, 2019 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$ Commented Aug 21, 2019 at 9:19

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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