Аннотация:Спектром гамильтонова цикла (кода Грея) в булевом $n$-мерном кубе называется набор $a=(a_1,\dots,a_n)$, где $a_i$ – число рёбер $i$-го направления в цикле. Известны необходимые условия существования кода Грея со спектром $a$: числа $a_i$ чётные и для любого $k=1,\dots,n$ сумма $k$ произвольных компонент набора $a$ не меньше чем $2^k$. Доказано существование такой размерности $N$, что если необходимые условия на спектр являются достаточными для существования гамильтонова цикла с таким спектром в булевом $N$-мерном кубе, то сформулированные выше условия являются достаточными и для всех размерностей $n$. Библиогр. 10.
Ключевые слова:гамильтонов цикл, совершенное паросочетание, булев куб, код Грея.
УДК:
519.95
Статья поступила: 06.06.2011 Переработанный вариант: 22.11.2011