EN|RU

Том 19, номер 2, 2012 г., Стр. 76-84

УДК 519.95
Потапов В. Н. 
Построение гамильтоновых циклов с заданным спектром направлений рёбер в булевом n-мерном кубе

Аннотация:
Спектром гамильтонова цикла (кода Грея) в булевом $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.

Ключевые слова: гамильтонов цикл, совершенное паросочетание, булев куб, код Грея.

Потапов Владимир Николаевич 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: vpotapov@math.nsc.ru

Статья поступила 6 июня 2011 г.
Исправленный вариант — 22 ноября 2011 г.

 © Институт математики им. С. Л. Соболева, 2015