2
$\begingroup$

Let's assume that DAG is complete: there is directed edge among every to nodes. Does topological sort of vertices exist for any such graph? I.e. is it possible to make linear list of nodes in which the left node has edge into the right node. Maybe this is the question about existence of Hamiltonian path in every complete DAG?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ From Wiki: "A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG)". You can easily prove this fact by induction on the number of vertices in DAG $\endgroup$
    – 3cnf
    Commented Oct 21, 2019 at 7:50

1 Answer 1

Reset to default
2
$\begingroup$

Yes it exists and the existence of a linear ordering not only shows the existence of the topological oredering over the vertices but also that this ordering is unique. It is not hard to prove that the graph represents a linear ordering using the facts that the graph is complete and acyclic. That should be a good exercise for you (proving a relation is a linear ordering means to prove it is reflexive, asymmetric and transitive).

Improve this answer
$\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.