RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2012, том 19, выпуск 2, страницы 75–83 (Mi da683)

Эта публикация цитируется в 1 статье

Построение гамильтоновых циклов с заданным спектром направлений рёбер в булевом $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.

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

УДК: 519.95

Статья поступила: 06.06.2011
Переработанный вариант: 22.11.2011


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2012, 6:3, 339–345

Реферативные базы данных:


© МИАН, 2024