Hamiltonian cycle in tournament I am new to graph theory and I've just learnt about Hamiltonian cycle in a graph which is a NP-complete problem. But I have to find a Hamiltoninan cycle in a graph with N*(N-1)/2 edges which I believe it is called a tournament. I saw an algorithm on Wikipedia which I din not understand properly( the one in which you have  v1, ... , vk ham path and when you add a vertex v you search for two other vertexes and reverse something ). So can someone please explain me an algorithm with has the time O(N^2) and which finds a hamiltonian cyclein a tournament ( I believe that in the ham cycle the last vertex and the first one must be connected ).
Well, I am not sure about which algorithm you are talking about (there's no link and I could not find it at Wikipedia's tournamet page, nor Hamilton cycle page), but you can do something like this:


Remove any vertex $v$ from $G$.
In each strongly-connected component recursively calculate Hamilton cycles.
If there are at least two SCCs, let $G_\top$ and $G_\bot$ be the top and bottom respectively; find vertices $u_\top \in G_\top$ and $u_\bot \in G_\bot$ such that $u_\bot \to v \to u_\top$ (we know that such vertices exist because $G$ was strongly connected).
If there is exactly one SCC, find two vertices $u_\top, u_\bot \in G\setminus \{v\}$ such that
$u_\bot$ is a successor of $u_\top$ in the Hamilton cycle of $G \setminus \{v\}$ we previously found, and $u_\top \to v \to u_\bot$ (again, we know that such vertices exist because $G$ was strongly connected).
Patch it all together.


This might take $O(n^3)$ time, but if you were to go backwards, i.e. constructing the graph, rather than deconstructing it, then SCCs calculation can be done on-line using find-union, and then it would take about $O(n^2\alpha(n))$ which is almost the same as a square.

I hope this helps $\ddot\smile$
A tournament is a complete directed graph (hence $n(n-1)/2$ edges). You can think about it as $n$ teams where each one played against each other and there is an edge going from $v$ to $w$ only if $v$ beat $w$ in the match (other wise a there is an edge in the reverse direction).

Now, we can construct an Hamiltonian path (not cycle) where each vertex "beat" the adjacent vertex on the right (and so the graph indeed as a corresponding directed edge). If we can "line up" the vertices  in such way then it corresponds to Hamilonian path.

Start with a single vertex - a path of length 1. For each remaining vertex travese the path from left to right, trying to find a place where you can fit it in, kind of like insertions sort. If the vertex beat the leftmost vertex in the path, place the new vertex as the new leftmost. Otherwise it lost to it, so you can go on to the next vertx and check again if it can fit in. The only case you wouldn't find a place between existing vertices in the path is if the new vertex lost to every one of them - hence you can put it rightmost.

Following this idea, you can easily write a "formal" proof by induction for the statement.