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?

$\endgroup$
  • 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$ – diplodoc Oct 21 '19 at 7:50
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).

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