2
$\begingroup$

I've been straggling a little proving the argument "a hamiltonian directed acyclic graph has a single topological sort".

This is pretty much the idea of what I've come along:

  • lets prove by contradiction. so lets assume a hamiltonian DAG has at least 2 topological sorts.
  • If there're few topological sorts - it means one of the following options:
  • either there're at least 2 vertices that aren't dependent. meaning both of these vertices could be with 0 in-degree. but it contradicts the fact that the graph is hamiltonian (there's a hamilton path in G)
  • either there exists a vertex that splits to 2 branches. such that the neighboring vertices could appear in different order in the topological sort. but it contradicts that the graph is hamiltonian because in such a case - after choosing a branch, we won't be able to visit the vertices of the second branch. however if we do have this possibility, we have come to a cycle that ends in the vertex that split to 2 branches. (contradiction to the graph being a DAG)
  • Finally we get contradiction to our assume - thus the original statement is correct.

Would appreciate your thoughts and suggestions about the idea of proof.

$\endgroup$
2
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Mar 22 '17 at 22:08
  • $\begingroup$ @sgrmshrsm7, it's great that you want to edit the question to improve it. However, when making edits, we prefer that you try to improve as many aspects as possible. I'd discourage an edit that only changes the capitalization in the first word of the title, and makes no other change -- that bumps the question to the top of the front page and can take attention away from other worthy posts, and takes up time from three other community members to review the edit suggestion. See meta.stackexchange.com/q/74430/160917 and meta.stackexchange.com/a/82895/160917. $\endgroup$
    – D.W.
    Mar 26 '17 at 23:26
0
$\begingroup$

Let $G$ be a DAG with $G = (V, E)$. Recall that every DAG has at least one topological ordering.

Assume $G$ is Hamiltonian, i.e. there exists a path of length $|V|$, e.g. $p = [v_1, \ldots, v_n]$ where $n = |V|$. Note that there's a path from $v_i$ to $v_j$ whenever $i < j$. Thus $p$ is a topological ordering: if there is any edge from $v_j$ to $v_i$ with $i < j$ then $G$ contains a cycle but we assumed it to be a DAG.

But note also that $v_i$ must come before each of $v_1, \ldots, v_{i-1}$ in every topological ordering, since each of those have a path to $v_i$ (name some suffix of a prefix of $p$). Likewise, $v_{i+1}, \ldots, v_n$ must come after $v_i$ in every topological ordering since $v_i$ has a path to each of those.

But then $v_i$ occurs in position $i$ in every topological ordering, i.e. every topological ordering is equal to $p$ so it must be the only topological ordering.

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