ToInfinityAndBeyond - 1 year ago 69

Python Question

A tournament is a complete, directed graph, such that given any two vertices, u and v, there exists a directed edge between them (if u won over v, then the edge is from u to v).

A Hamiltonian Path always exists in a tournament. So given adjacency lists in the form {u:[v,w],v:[w]} where there is a directed edge from u to w, u to v, and v to w, how do I find what the Hamiltonian Path is and print the veritces in order?

Even if you don't know python or whatever, just the algorithm would be very helpful. I've thought about it, and I suppose I have to start with the vertex of highest out degree? Then add the vertex with the second highest degree etc till the vertex with the lowest degree. But I don't see how this is a fail safe method, the vertex with the highest degree could have been beaten by the vertex with the second highest.

Thank you for any help in advance!

Answer

You can solve this problem recursively. Suppose you have `n+1`

vertices named `v_0`

to `v_n`

. `v_1`

to `v_n`

and edges between them for a tournament of size n, so we can suppose that we have a hamiltonian path containing `v_1`

to `v_n`

. Rename them in accordance with that path as `u_1`

to `u_n`

. Now find `u_i`

such that `u_i`

has won over `v_0`

and `v_0`

has won over `u_i+1`

(Here you should take care of marginal nodes: `v_0`

has won over `u_1`

or `u_n`

has won over `v_0`

). After finding such `i`

, the overall hamiltonian path can be constructed as:

```
u_1 , ... , u_i , v_0 , u_i+1 , ... , u_n
```

This algorithm has runtime of O(n^2). There exists O(nlogn) algorithm for this problem.