*49. Mostre que existe um código de Gray de ordem n sempre que n for um inteiro positivo ou, equivalentemente, mostre que o n-cubo Q_{n}, n>1, sempre tem um ciclo hamiltoniano. [Dica: Use indução matemática. Mostre como produzir um código de Gray de ordem n a partir de um de ordem n-1.]

Passo 1

O enunciado pede para mostrar, por indução em n, que sempre existe um código de Gray de ordem n, isto é, uma lista cíclica de todas as palavras binárias de comprimento n em que palavras consecutivas diferem em exatamente um bit. Equivalentemente, isso diz que o n-cubo Q_n tem um ciclo hamiltoniano para todo inteiro n\ge1. Vamos usar o método refletido de construção de código de Gray.

Passo 2

Base da indução n=1. Um código de Gray de ordem 1 é simplesmente
G^{(1)} = (0,1),
pois há 2^1=2 palavras de comprimento 1 e 0 e 1 diferem em um bit. Além disso, fechando o ciclo, o último elemento 1 volta para o primeiro 0 com uma única mudança de bit.

Passo 3

Passo indutivo: suponha que já exista um código de Gray de ordem n-1, ou seja, uma sequência cíclica
G^{(n-1)} = \bigl(c_{1},c_{2},\dots,c_{2^{\,n-1}}\bigr),
onde cada c_i é uma palavra binária de comprimento n-1, palavras consecutivas diferem em um bit, e também c_{2^{\,n-1}} difere de c_{1} em apenas um bit.

Passo 4

Construção do código de Gray de ordem n. Definimos
G^{(n)} = \bigl(\,0c_{1},0c_{2},\dots,0c_{2^{\,n-1}},\;1c_{2^{\,n-1}},1c_{2^{\,n-1}-1},\dots,1c_{1}\bigr).
Aqui em cada palavra estamos apenas concatenando um bit extra à esquerda: primeiro todas as palavras de G^{(n-1)} com prefixo 0 e depois as mesmas, em ordem reversa, com prefixo 1.

Passo 5

Verificação de que G^{(n)} é um código de Gray cíclico de ordem n:
  1. Dentro do bloco 0c_{1},0c_{2},\dots,0c_{2^{\,n-1}}, cada par consecutivo difere em um bit, porque eram consecutivos em G^{(n-1)} e o prefixo 0 é o mesmo.
  2. A transição de 0c_{2^{\,n-1}} para 1c_{2^{\,n-1}} muda somente o bit de prefixo (de 0 para 1).
  3. Dentro do bloco reverso 1c_{2^{\,n-1}},1c_{2^{\,n-1}-1},\dots,1c_{1}, cada par consecutivo difere em um bit, pois em G^{(n-1)} os códigos reversos consecutivos diferiam em um bit, e o prefixo 1 é constante.
  4. Fechando o ciclo, de 1c_{1} de volta para 0c_{1} muda só o prefixo.
Logo, em toda a sequência cíclica entre palavras vizinhas há exatamente uma mudança de bit, o que dá um código de Gray de ordem n.

Resposta

Pela indução, acabamos de mostrar que para todo inteiro positivo n existe um código de Gray de ordem n e, portanto, o n-cubo Q_n sempre possui um ciclo hamiltoniano.

Exercícios de Livros Relacionados