Том 4, серия 1, номер 3, 1997 г., Стр. 9-17
УДК 519.6
О. М. Касим-Заде
О минимальных покрытиях булева куба центрированными антицепями
Аннотация:
Изучаются покрытия булева $n$-куба $B^n=\{0,1\}^n$ центрированными антицепями,
т. е. множествами, состоящими из попарно несравнимых наборов,
имеющих общую единичную компоненту; к числу центрированных антицепей
относится также одноэлементное множество $\{\widetilde0^n\}$. Установлено, что для всякого $n\geqslant 1$ минимальное число центрированных антицепей, объединение которых покрывает $n$-куб, равно $n[\log_2{n}]+2(n-2^{[\log_2{n}]})+2$. Дано явное описание минимальных покрытий.
Библиогр. б.
Касим-Заде О. М. 1
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия
е-mail: omkas@nw.math.msu.su
Статья поступила 28 апреля 1997 г.
|