World's most popular travel blog for travel bloggers.

Confusion regarding DAGs

, , No Comments
Problem Detail: 

I've a question regarding DAGs. 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. Then a path from u to v exists as well as a path from v to u. This creates a cycle thus contradicting our assumption. Correct me if I'm wrong? :')

Asked By : muqsitnawaz
Answered By : Luke Mathieson

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).

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback