Gray Code

2. In the recursive definition for the Gray code, G+1, given in the text, and assuming G, satisfies the properties of a Gray code, explain concisely: (a) Why the string in position n and the string in position n+1 differ only in one bit (b) Why, for i 1...n-1, the string in position i and the string in position i+ 1 differ only in one bit. (c) Why, for i n +1...2n-1, the string in position i and the string in position i+ 1 differ only in one bit. Fortunately, our solution will apply to the n-cube for any positive value of n. A Hamiltonian circuit of the n-cube can be described recursively. The circuit itself, called the Gray Code, is not the only Hamiltonian circuit of the n-cube, but it is the easiest to describe. The standard way to write the Gray Code is as a column of strings, where the last string is followed by the first string to complete the circuit. Basis for the Gray Code (n = 1): The Gray Code for the 1-cube is G = CHAPTER 9. GRAPH THEORY 221 ). Note that the edge between 0 and 1 is used twice in this circuit. That doesn't violate any rules for Hamiltonian circuits, but can only happen if a graph has two vertices. Recursive definition of the Gray Code: Given the Gray Code for the n-cube. n 1. then G +1 is obtained by (1) listing G, with each string prefixed with 0. and then (2) reversing the list of strings in with each string prefixed with 1. Symbolically, the recursion can be expressed as follows, where is the reverse of list G . OG GEGE The Gray Codes for the 2-cube and 3-cube are 000 001 011 010 110 01 10 2. In the recursive definition for the Gray code, G+1, given in the text, and assuming G, satisfies the properties of a Gray code, explain concisely: (a) Why the string in position n and the string in position n+1 differ only in one bit (b) Why, for i 1...n-1, the string in position i and the string in position i+ 1 differ only in one bit. (c) Why, for i n +1...2n-1, the string in position i and the string in position i+ 1 differ only in one bit. Fortunately, our solution will apply to the n-cube for any positive value of n. A Hamiltonian circuit of the n-cube can be described recursively. The circuit itself, called the Gray Code, is not the only Hamiltonian circuit of the n-cube, but it is the easiest to describe. The standard way to write the Gray Code is as a column of strings, where the last string is followed by the first string to complete the circuit. Basis for the Gray Code (n = 1): The Gray Code for the 1-cube is G = CHAPTER 9. GRAPH THEORY 221 ). Note that the edge between 0 and 1 is used twice in this circuit. That doesn't violate any rules for Hamiltonian circuits, but can only happen if a graph has two vertices. Recursive definition of the Gray Code: Given the Gray Code for the n-cube. n 1. then G +1 is obtained by (1) listing G, with each string prefixed with 0. and then (2) reversing the list of strings in with each string prefixed with 1. Symbolically, the recursion can be expressed as follows, where is the reverse of list G . OG GEGE The Gray Codes for the 2-cube and 3-cube are 000 001 011 010 110 01 10