*49. Mostre que existe um código de Gray de ordem
sempre que
for um inteiro positivo ou, equivalentemente, mostre que o
-cubo
, sempre tem um ciclo hamiltoniano. [Dica: Use indução matemática. Mostre como produzir um código de Gray de ordem
a partir de um de ordem
.]
Passo 1
O enunciado pede para mostrar, por indução em
, que sempre existe um código de Gray de ordem
, isto é, uma lista cíclica de todas as palavras binárias de comprimento
em que palavras consecutivas diferem em exatamente um bit. Equivalentemente, isso diz que o
-cubo
tem um ciclo hamiltoniano para todo inteiro
. Vamos usar o método refletido de construção de código de Gray.
Passo 2
Base da indução
. Um código de Gray de ordem
é simplesmente
pois há
palavras de comprimento 1 e
e
diferem em um bit. Além disso, fechando o ciclo, o último elemento
volta para o primeiro
com uma única mudança de bit.
Passo 3
Passo indutivo: suponha que já exista um código de Gray de ordem
, ou seja, uma sequência cíclica
onde cada
é uma palavra binária de comprimento
, palavras consecutivas diferem em um bit, e também
difere de
em apenas um bit.
Passo 4
Construção do código de Gray de ordem
. Definimos
Aqui em cada palavra estamos apenas concatenando um bit extra à esquerda: primeiro todas as palavras de
com prefixo
e depois as mesmas, em ordem reversa, com prefixo
.
Passo 5
Verificação de que
é um código de Gray cíclico de ordem
:
- Dentro do bloco
, cada par consecutivo difere em um bit, porque eram consecutivos em e o prefixo é o mesmo. - A transição de
para muda somente o bit de prefixo (de para ). - Dentro do bloco reverso
, cada par consecutivo difere em um bit, pois em os códigos reversos consecutivos diferiam em um bit, e o prefixo é constante. - Fechando o ciclo, de
de volta para 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
.
Resposta
Pela indução, acabamos de mostrar que para todo inteiro positivo
existe um código de Gray de ordem
e, portanto, o
-cubo
sempre possui um ciclo hamiltoniano.