RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 2013, том 54, номер 2, страницы 407–416 (Mi smj2429)

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

Многомерные латинские битрейды

В. Н. Потапов

Новосибирский гос. университет, Новосибирск

Аннотация: Подмножество $k$-значного $n$-мерного гиперкуба называется унитрейдом (объединенным битрейдом), если мощности его пересечений с одномерными гранями гиперкуба принимают только два значения $0$ и $2$. Унитрейд называется двудольным (гамильтоновым), если соответствующий ему подграф гиперкуба является двудольным (гамильтоновым). Пара долей двудольного унитрейда называется $n$-мерным латинским битрейдом. Для троичного $n$-мерного гиперкуба определено число различных унитрейдов и получена экспоненциальная нижняя оценка числа неэквивалентных латинских битрейдов. Перечислены все возможные $n$-мерные латинские битрейды мощности, меньшей чем $2^{n+1}$.
Подмножество $k$-значного $n$-мерного гиперкуба называется $t$-кратным МДР-кодом, если оно пересекается с каждой одномерной гранью гиперкуба ровно по $t$ элементам. Симметрическая разность двух однократных МДР-кодов является двудольным унитрейдом. Каждая из компонент соответствующего латинского битрейда является свитчинговой компонентой одного из этих МДР-кодов. Исследованы вопросы о мощностях компонент МДР-кодов и возможности получения латинских битрейдов заданной мощности из МДР-кодов. Кроме того, доказано, что любой МДР-код вкладывается в гамильтонов двукратный МДР-код.

Ключевые слова: МДР-код, латинский битрейд, унитрейд, компонента.

УДК: 519.14

Статья поступила: 17.03.2012


 Англоязычная версия: Siberian Mathematical Journal, 2013, 54:2, 317–324

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


© МИАН, 2024