0
$\begingroup$

I am stumped on the following question:

For any depth first search of a directed graph, is it true that the strongly connected component containing the vertex with the lowest post order number also contains a sink?

I know that the sink has the highest post-order number, so I am inclined to say False, but I do not know if that reasoning is accurate.

$\endgroup$
3
  • $\begingroup$ Why do you say the sink? There may be multiple sinks, or none at all... $\endgroup$ – Steven Mar 8 at 11:08
  • $\begingroup$ @Steven I mean that it contains a sink. Yes, there can be multiple sinks in the entire graph, but as long as it contains the strongly connected component contains a sink, the statement holds. $\endgroup$ – Adam Lee Mar 8 at 11:35
  • $\begingroup$ Cross-posted to cstheory.stackexchange.com/q/48550 $\endgroup$ – Emil Jeřábek Mar 8 at 14:50
0
$\begingroup$

The statement is false. Consider the directed graph $G=(V,E)$ where $V=\{1,2\}$ and $E=\{(1,2), (2,1)\}$.

The graph only contains a single strongly connected component, namely $G$ itself. However no vertex in $V$ is a sink.

$\endgroup$
3
  • $\begingroup$ So they are sometimes but not always? $\endgroup$ – rsonx Mar 26 at 14:31
  • $\begingroup$ I meant if there is no looping edge then the vertex with lowest postorder is a sink, right? $\endgroup$ – rsonx Mar 26 at 14:33
  • $\begingroup$ What's a looping edge? The graph I provided is loop-free... You mean that the graph is acyclic? If so, each vertex belong strongly to its own strongly connected component. $\endgroup$ – Steven Mar 26 at 14:47

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.