5
$\begingroup$

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 b\right)$

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?

$\endgroup$
  • 1
    $\begingroup$ Perhaps my question about random orders may be relevant. It depends on what you mean by work, but it was decided most would actually get something done. $\endgroup$ – edA-qa mort-ora-y Jul 8 '12 at 5:16
  • $\begingroup$ do you need make a tree that each node is reachable with(O(1)) in your tournament graph? $\endgroup$ – amin k Jul 10 '12 at 12:26
8
$\begingroup$

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$:

counter example
[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.

$\endgroup$
  • $\begingroup$ Thanks for the comprehensive answer! It was really helpful. $\endgroup$ – Tim Dumol Jul 9 '12 at 13:57

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.