95 views

Was solving the GO 2019 pdf when I encountered this question asked in TIFR 2017. Although I have understood this question, I have one doubt-

It is mentioned in the question that for a 3-bit number, the ordering (000, 100, 101, 111, 110, 010, 011, 001) is one of the possible Gray codes.

Then, how many such orders are there for an n-bit number?

| 95 views
0

It will look like this and we have to find hamiltonian cycles possible right ?

assume $\rightarrow$ is bidirectional

0
I don't think there should be an edge between node(01) and node (10) as they differ by 2 bits.
0

like this right ?

0
Yes, this one is correct.
0
So, if I am not mistaken, the problem reduces to finding the no. of distinct directed Hamiltonian cycles for such a graph where nodes (that represent the Gray codes) have an edge between them only if they differ by 1-bit position.
0
Yes just 1 mistake

we have to find hamiltonian paths and not hamiltonian cycles

In the above graph there is only 1 cycle possible starting from 00 i.e. 00-01-11-10-00 and all other cycles are just its rotation.

but there are 2 hamiltonian paths starting from 00 i.e. 00-01-11-10 or 00-10-11-01
0
every time the hamiltonian paths will be different right , there is not any general formula ?

we can't generalize it as it will vary from graph to graph

$\therefore$ we have to do it by brute force technique if we are using graph method.
+1
Yeah, you are right. Here, we are trying to find the no. of Hamiltonian paths and not Hamiltonian cycles. Also, such graphs are actually a special type of graphs called Hypercubes (somehow I completely forgot about them ?). Also, finding the no. of Hamiltonian paths in an arbitrary graph is an np-complete problem. So, no other option apart from brute-force.
0
I think hamiltonian cycles also correct if we consider undirected edges. Isn't it?
0
No, the problem reduces to finding the no. of different Hamiltonian paths. For example, if we consider a 1-bit no., the hypercube will be a simple edge connecting two nodes (i.e. no cycles).

If we model as hypercube then we can convert it to bipartite graph. And from bipartite graph we can get number of hamiltonian cycles. For 3-bit,

V1                                       V2

000 (4-possibilities)        001(3-possibilities)

011  (3-possibilities)        111 (2)

101 (2)                                100(1)

110(1)                                 010(1)

Total = 4*3*3*2*2 =144 but as they are cycles divide by 2. So total = 72.

Please let me know if there is any wrong wit this method.
by (127 points)
0
What do the possibilities represent?
0
It represents the no. Of ways it can connect to vertices in other set. If we want hamiltonian cycles, we can work out in this way.
0
How does the node (000) connect to 4 vertices in the other set. The hypercube for 3-digit no. is a cube and each node k connects to only 3 other nodes. This is because there are only 3 other nodes that differ from the node k by a single bit position.

Also, in the bipartite graph, node (000) won't have an edge to node (111).
0
Yes you are right. Need to it is three possibilities only for each node. Thanks for pointing this.

1
2