0
$\begingroup$

I am trying to prove that given a DAG. There exists a valid topological ordering that has v in front of u iff there is no path from u to v. The proof is related to the fact that reverse DFS post visit order satisfies the condition of topological order. How do I construct a proof?

$\endgroup$

1 Answer 1

0
$\begingroup$

Assume that there is path $u \rightarrow v$ as well. Then we have a cycle. What does this mean in terms of topological order? Can there be such an order? Whether u comes first or v comes first depends on where you start!

$\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.