Problem Detail: Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order: $qquad displaystyle a leq b iff (a,b) in E lor left(exists, c in V. a leq c land c leq bright)$ For context, this came from an observation that the inductive construction in the above page seems to be equivalent to insertion sort using the given order. Is it possible to use other sorting algorithms?
Asked By : Tim Dumol
Answered By : Raphael
I assume that you intend $leq$ to be the reflexive and transitive closure of $E$, or directed reachability, that is $leq$ is really the smallest fixpoint of the equivalence you give: $qquad displaystyle a leq b iff exists, v_0 dots v_n. a to v_o to dots to v_n to b$ with $n geq 0$ and $v to u iff (v,u) in E$. The key argument here is that $leq$ is indeed a total order. If it is, you can use it for sorting, and the result is by definition of $leq$ a Hamiltonian path: consider the result of the sort $v_1 dots v_n$. If there were no edge between $v_i$ and $v_{i+1}$, by $V_s = v_i leq v_{i+1}$ there is $v in V$ such that $v_i leq v leq v_{i+1}$. This contradicts that $leq$ is a (total) order and $V_s$ is sorted with respect to $leq$. Unfortunately, $leq$ is not an order relation: it is not antisymmetric. Consider the small tournament based on $K_4$: 
[source] Here, $a leq d$ and $d leq a$ (directed cycles are the culprits!) but $a neq d$. So $leq$ is only a (well-)quasi-order and there is no such thing as a sorted node list.

[source] Here, $a leq d$ and $d leq a$ (directed cycles are the culprits!) but $a neq d$. So $leq$ is only a (well-)quasi-order and there is no such thing as a sorted node list.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2646 Ask a Question Download Related Notes/Documents