Please explain How to derive formula for number of hamiltonian cycles in a complete undirected graph. at wikipedia it is given that it is (n-1)!/2 but when I calculated K3 has only one cycle and K4 has 5. Or I am wrong. Please elaborate
+8
A:
Since the graph is complete, any permutation starting with a fixed vertex gives an (almost) unique cycle (the last vertex in the permutation will have an edge back to the first, fixed vertex. Except for one thing: if you visit the vertices in the cycle in reverse order, then that's really the same cycle (because of this, the number is half of what permutations of (n-1) vertices would give you).
e.g. for vertices 1,2,3, fix "1" and you have:
123 132
but 123 reversed (321) is a rotation of (132), because 32 is 23 reversed.
There are (n-1)! permutations of the non-fixed vertices, and half of those are the reverse of another, so there are (n-1)!/2 distinct Hamiltonian cycles in the complete graph of n vertices.
wrang-wrang
2009-09-07 04:20:50
a nice explanation
avd
2009-09-07 04:40:24
I asked this questions in relation to a last year Code Jam Question. But I am still not able to figure out the algorithmCan u please explain this Code Jam questionhttp://code.google.com/codejam/contest/dashboard?c=32004#s=p2
avd
2009-09-07 04:45:53
I'd generate all the permutations of 2...n where 2 comes in the first half, and skip over those that give one of the forbidden edges, i.e. if your permutations is 4235 (meaning the cycle 142351...) then skip it if 14 42 23 35 or 51 are forbidden. You can do this as you generate the permutations e.g. if 14 was forbidden, then you would have stopped at "4..."
wrang-wrang
2009-09-07 05:16:27
But if number of vertices is very large say 30 then generating all permutations i.e. 29!/2 is computationally very expensive
avd
2009-09-07 05:21:52
One more thing why did u say "where 2 comes in the first half"? What does this mean?
avd
2009-09-07 05:27:20
Well, I just wanted some way of distinguishing the permutation p from reverse(p). One way to do that is to pick an element (I picked 2) and ensure that it occurs in the first half.
wrang-wrang
2009-09-07 05:39:16
You're right that my suggestion for a 30 or 300 node graph is impractical. It seems like a tricky problem. Did you know you can download people's source code who've solved it?
wrang-wrang
2009-09-07 05:40:29
All the vertices not adjacent to one of the prohibited 0-15 edges are indistinguishable, so there's no need to actually generate the permutations of those indistinguishable vertices. Just using that fact should make it tractable.
wrang-wrang
2009-09-07 05:56:41