UVa 775

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]



Given a dense graph, find a hamiltonian cycle of this graph, that is, a cycle that visits each vertex exactly once, if it has one.


Determining whether a hamiltonian cycle exists in a graph is NP-complete. But in this problem, the constraints of the given graph allow us to find such a cycle in O(n^2). Dirac's Theorems denote that if a given graph satisfy that for each pair of vertexs u,v, if degree(u)+degree(v) >= V, we can determine whether a hamiltonian cycle exists and find it in O(V^2), here V is the number of vertexs in the graph, see Reference for more details


The steps of the algo :

1.Find two adjacent vertex S and T. Based on the path S-T, extend a path that contains no duplicate vertex as long as possible. That is, if S is adjacent to vertex v and v is not in the path S-T, then we can extend the path to v-S-T and now v becomes the new S. Extend the path in both direction (v-S-T and S-T-v) till no vertex can be added. Now all the vertex adjacent to S or T is in the path S-T.

2.If S is adjacent to T, the "path" S->T will form a cycle.

3.If not, we can construct one. Let the current path be (S-v1-v2-...-vk-T). We can prove with Pigeonhole Principle that there must be a vertex vi,1<=i<=k, such that vi is adjacent to T and vi+1 is adjacent to S. Once such a vi is found, we can change the origin path to a cycle (S - vi+1 - T - vi - S)

4.Now we have constructed a cycle without duplicate vertex. If the length of the cycle is N, we've got the hamilton cycle. If not, because the entire graph is connected, there must be a vertex vi in the cycle adjacent to a vertex q outside the cycle. Then we break the cycle in vi and it becomes a path again. Go to step 1 to extend the path as long as possible, and now at least one new vertex will be added in the path.

Here is the code:



1 2
2 3
2 4
3 4
3 1
1 2
1 3
1 6
3 2
3 4
5 2
5 4
6 5
6 4


1 2 4 3 1
1 3 2 5 4 6 1