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