Gray Code (Self Doubt)

Question

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? 

Comments

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.

---

I think hamiltonian cycles also correct if we consider undirected edges. Isn't it?

---

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

Answer 1

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.

Comments

What do the possibilities represent?

---

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.

---

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

---

Yes you are right. Need to it is three possibilities only for each node. Thanks for pointing this.

Answer 2

we have a unique gray code for each binary combination which is obtained by Exoring in some manner,

since we have 2^n binary combinations for n-bits similarly,we have 2^n combinations of gray code for n-bits