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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Why do you say the sink? There may be multiple sinks, or none at all... $\endgroup$
    – Steven
    Mar 8, 2021 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, 2021 at 11:35
  • $\begingroup$ Cross-posted to cstheory.stackexchange.com/q/48550 $\endgroup$
    – Emil Jeřábek
    Mar 8, 2021 at 14:50

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So they are sometimes but not always? $\endgroup$
    – rsonx
    Mar 26, 2021 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, 2021 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, 2021 at 14:47

Your Answer

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

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