13.3 Embedding of Arrays and Trees g-1)-bit O Gray code 0000...000 0000...001 Ng((x) 0000...011 0100...000 q-Dcube 0 (q-1]ube 1 1:100...000 Fig. 13.3 Hamiltonian cycle in the g-cube Alternate inductive proof: Hamiltonicity of the q-cube 000...011 is equivalent to the existence of a g-bit Gray code 1000...010 000...000 Basis: q-bit Gray code beginning with the all-Os codeword (9-1)-bit and ending with 10q-1 exists for g= 2: 00, 01, 11, 10 Gray code In reverse Fa2010 Parallel Processing, Low-Diameter Architectures Slide 11Fall 2010 Parallel Processing, Low-Diameter Architectures Slide 11 13.3 Embedding of Arrays and Trees Alternate inductive proof: Hamiltonicity of the q-cube is equivalent to the existence of a q-bit Gray code Fig. 13.3 Hamiltonian cycle in the q-cube. (q ?1)-cube 0 x (q ?1)-cube 1 N (x) k N (x) q? N (N (x)) q? k (q – 1)-bit Gray code 000 . . . 000 000 . . . 001 000 . . . 011 . . . 100 . . . 000 0 0 0 0 1 1 1 1 100 . . . 000 . . . 000 . . . 011 000 . . . 010 000 . . . 000 (q – 1)-bit Gray code in reverse Basis: q-bit Gray code beginning with the all-0s codeword and ending with 10q–1 exists for q = 2: 00, 01, 11, 10 q （q -1） q （q -1）