The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
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? 

in Digital Logic by (499 points) | 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).

1 Answer

0 votes
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.

Related questions

0 votes
1 answer
2
asked Jan 5, 2016 in Digital Logic by Himanshu1 Boss (15.4k points) | 155 views
0 votes
0 answers
4
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,807 questions
54,711 answers
189,259 comments
79,680 users