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 ).
[Math] Hamiltonian cycle in tournament
graph theory
Related Solutions
Let's call your tournament $T$, and write $a \rightarrow b$ when there is an arc from $a$ to $b$. Write $a \rightarrow B$ when $B$ is a vertex set and $a$ has an arc to all members of $B$. Finally write $B \rightarrow a$ when all members of a set $B$ have an arc to $a$.
1) is straightforward enough. If $T$ has a cycle of length 3, then it can't be transitive by definition. Conversely, suppose $T$ is not transitive. Then $\forall a,b,c \in V(T) [a \rightarrow b, b \rightarrow c \Rightarrow a \rightarrow c]$ is false. What do you get by negating this expression ?
2) There's probably a better way for the tougher direction, but here goes. One way is to suppose $T$ has no Hamiltonian cycle and get that $T$ is not strongly connected. Let $C = c_1c_2 \ldots c_k c_1$ be a directed cycle of $T$ with the largest number of vertices.
Let $x \in V(T)$ such that $x \notin C$. If $c_i \rightarrow x$ for some $c_i \in C$, then $c_{i + 1} \rightarrow x$ as otherwise, $x \rightarrow c_{i+1}$ and $C' = c_1c_2 \ldots c_i x c_{i + 1} \ldots c_k c_1$ would be a bigger cycle (but $C$ is a largest cycle by assumption). Applying this reasoning inductively, we have that $C \rightarrow x$ when some $c_i \rightarrow x$.
So what do you get for any $x$ outside $C$ ? Either $C \rightarrow x$ or $x \rightarrow C$. Let $X = \{x : C \rightarrow x\}$ and $Y = \{y : y \rightarrow C\}$. Take $x \in X, y \in Y$. If $x \rightarrow y$, then you can extend the $C$ cycle by deviating with $c_ixyc_{i + 1}$. So $y \rightarrow x$, for all $x \in X, y \in Y$. From this, you can deduce that there is no way to go from $x \in X$ to $c_i \in C$, hence $T$ is not strongly connected.
What's left for you to do is to argue that $C$ exists, and handle the cases when $X$ or $Y$ is empty (and tell us why both can't be empty).
This can be proven using strong induction. Let $n$ be the number of vertices. When $n \le 2$, a hamiltonian path clearly exists. Now, for any given $n > 2$, pick any arbitrary vertex $v$. Partition all other vertices other than $v$ into the sets $V_{out}$ and $V_{in}$ -- $V_{out}$ contains all other vertices $u$ such that the edge $(v, u)$ exists, while $V_{in}$ contains all other vertices $u$ such that the edge $(u, v)$ exists.
Clearly $|V_{out}| < n$ and $|V_{in}| < n$, so by the inductive hypothesis, there is a hamiltonian path in both sets. Let $H_{out}$ be any hamiltonian path in $V_{out}$ and $H_{in}$ be any hamiltonian path in $V_{in}$. You can then form a hamiltonian path for all vertices by concatenating $H_{in}$, $v$, and $H_{out}$.
Best Answer
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:
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$