1
$\begingroup$

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 ).

$\endgroup$
  • $\begingroup$ The tournament with vertices $\{1,\ldots,n\}$ and an arc from $i$ to $j$ if $i<j$ does not have a Hamilton cycle. $\endgroup$ – Chris Godsil Aug 7 '13 at 11:49
  • $\begingroup$ Is your graph directed or maybe undirected? $\endgroup$ – dtldarek Aug 7 '13 at 12:25
  • $\begingroup$ it is a directed graph $\endgroup$ – user2128547 Aug 7 '13 at 12:38
  • 3
    $\begingroup$ Then you should have an assumption that the graph is strongly connected, otherwise it's not Hamiltonian. $\endgroup$ – dtldarek Aug 7 '13 at 12:43
  • $\begingroup$ It is strongly connected $\endgroup$ – user2128547 Aug 7 '13 at 12:53
4
$\begingroup$

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:

  1. Remove any vertex $v$ from $G$.
  2. In each strongly-connected component recursively calculate Hamilton cycles.
  3. 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).
  4. 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).
  5. 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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I need a path in which there is an edge between any two consecutive vertexes there is an edge and THERE IS AN EDGE BETWEEN THE LAST VERTEX AND THE FIRST ONE! $\endgroup$ – user2128547 Aug 11 '13 at 12:54
0
$\begingroup$

This can also be done in O(n+m) time with n vertexes and m edges using depth-first search (DFS).

  • take a non-discovered point and create a DFS tree
  • after processing all child vertexes, put the parent vertex in a stack
  • repeat the process until all vertexes have been been discovered
  • finally, pop the items from the stack to get the required order

Why is this O(n+m)? Each vertex is processed no more than once and each edge - no more than twice.

Why is it correct? Let's analyze vertex post-processing in the DFS tree:

  1. all vertexes from outgoing edges are in the stack, the top-of-the-stack being one of them (by induction)
  2. both undiscovered and the parent vertex are from incoming edges (because this is post-processing)
  3. since the parent vertex will be put in the stack before any other vertex from the DFS, the current vertex can be correctly be placed in the stack
  4. if there are vertexes left after a DFS tree is processed, they will all have outgoing edges to all vertexes in the stack
$\endgroup$

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.