1
$\begingroup$

My instructor asked me to prove that strongly connected component of a DAG is also a DAG. I don't get it. How can a graph be DAG and strongly connected at the same time?

Consider a graph on two vertices "u" and "v" and assume that it is strongly connected as well as a DAG. A path from u to v exists as well as a path from v to u which creates a cycle. No?

$\endgroup$
1
$\begingroup$

This is difficult to answer because in part we have to guess what your instructor actually meant, but that said, I can't see a way to reconcile the statement.

You could ask if the components that are strongly connected in the underlying undirected graph are DAGs, but this is trivial, any subgraph of a DAG is also a DAG - we're not adding any edges, so we can't introduce a cycle.

Alternatively, we could ask for strongly connected components of a DAG, but here your observation is correct, there are no non-trivial strongly connected components in a DAG. The trivial ones are just each vertex by itself, which is trivially a DAG too, so that kind of works, if your instructor is looking to test your understanding of the definitions.

The last thing I can think of is that if you take a directed graph (not necessarily acyclic), and shrink each strongly connected component to a single vertex, the resulting graph is a DAG (called the "condensation" of the original graph). The condensation of a DAG is the DAG itself (we're back to the trivial strongly connected components again).

$\endgroup$

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.