Булев куб

[serval]

Пожалуйста, объясните, что такое $N$-мерные булев куб, $\pm1$-куб и соответствующие симплексы?
В каких областях математики наиболее полно развита их теория? Где об этом можно подробно прочесть?

[alcoholist]

Совершенно непонятно о чем Вы спрашиваете. Даже мне. Даже с утра.

[Sonic86]

serval в сообщении #489588 писал(а):

$N$-мерные булев куб

Это $\{ 0;1\}^N$ - граф на множестве векторов длины $N$ и нулями и единицами. Используется в аналитической геометрии, для решения задач булева линейного программирования (NP-задачи на графах) и еще много где.

serval в сообщении #489588 писал(а):

$\pm1$-куб

serval в сообщении #489588 писал(а):

соответствующие симплексы

$N$ - мерный симплекс - полный граф на $N+1$ линейно независимых точках в $N$-мерном пространстве (при $N=0$ - точка, при $N=1$ - отрезок, при $N=2$ - треугольник, при $N=4$ - треугольная пирамида и т.п.). Извините за кривое определение. Вообще, их начинают изучать в аналитической геометрии, а потом где только не используют.
$\pm 1$-симплекс -

[epros]

Sonic86 в сообщении #489638 писал(а):

serval в сообщении #489588 писал(а):

$\pm1$-куб

Предполагаю, что это то же самое, что и булев куб, но только с плюсиками там, где были единички, и с минусиками там, где были нолики.

[serval]

Цитата:

Совершенно непонятно о чем Вы спрашиваете.

Вот, вчера наткнулся, среди прочего

Информационные процессы, Том 8, № 4, 2008, стр. 201-204.
МАТЕМАТИЧЕСКИЕ МОДЕЛИ, ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ
"О квадратичных формах, равных единице на большом множестве вершин n-мерного куба"
Селиверстов, Любецкий

цитирую:

Цитата:

Кубом, или точнее n-мерным ±1-кубом, называется многогранник, вершинами которого являются точки с координатами ±1.

Я хотел узнать подробнее о свойствах этого куба. Похоже, это изобретение авторов статьи.

[epros]

serval в сообщении #489678 писал(а):

Цитата:

Кубом, или точнее n-мерным ±1-кубом, называется многогранник, вершинами которого являются точки с координатами ±1.

Я хотел узнать подробнее о свойствах этого куба. Похоже, это изобретение авторов статьи.

Понятно, значит по-сути это же самое, что и булев куб. И какие именно свойства Вас интересуют? Может просто стоит почитать процитированную книжку дальше?

[Sonic86]

epros в сообщении #489663 писал(а):

Предполагаю, что это то же самое, что и булев куб, но только с плюсиками там, где были единички, и с минусиками там, где были нолики.

Ааа, тогда понятно.
Я с перепугу подумал, что это размерность такая.

-- Ср окт 05, 2011 07:27:13 --

serval в сообщении #489678 писал(а):

Я хотел узнать подробнее о свойствах этого куба. Похоже, это изобретение авторов статьи.

Да обычный куб, образ при гомотетии булева $N$-мерного куба смотря, что авторы в нем откопали.

[serval]

Цитата:

И какие именно свойства Вас интересуют?

Сейчас я попробую сформулировать.

В $3$-мерном случае вершины куба имеют координаты: $(0,0,0),\ (1,0,0),\ (0,1,0),\ (1,1,0),\ (0,0,1),\ (1,0,1),\ (0,1,1),\ (1,1,1)$
а вершины его грани построенной на первых дух ортах: $(0,0,0),\ (1,0,0),\ (0,1,0),\ (1,1,0)$

Пусть размерность $N=4$.
Вершины грани гиперкуба построенной на первых трех ортах будут иметь координаты (к координатам вершин куба добавится $0$ в четвертой позиции): $(0,0,0,0),\ (1,0,0,0),\ (0,1,0,0),\ (1,1,0,),\ (0,0,1,0),\ (1,0,1,0),\ (0,1,1,0),\ (1,1,1,0)$
Тогда через любые $3$ из этих вершин можно провести прямую (или правильно будет сказать - гиперплоскость размерности $N-1$ ?), это верно? Например, через точки имеющие ровно $2$ ненулевые координаты - $(1,1,0),\ (1,0,1),\ (0,1,1)$

Пусть размерность $N$ произвольна.
Как пронумеровать подмножества вершин грани содержащие по $N-1$ вершине, каждая из которых имеет ровно $3$ ненулевые координаты?

Можно ли выписать эти подмножества (или, хотя бы, вершины) не выковыривая их по одной из всего множества сочетаний из $N-1$ по $3$?

Нельзя ли использовать, например, то свойство, что все такие вершины принадлежат одной грани, а их радиус-векторы имеют одинаковую длину и значит их кратчайший обход можно совершить по дуге окружности?

[Sonic86]

serval в сообщении #489702 писал(а):

Как пронумеровать подмножества вершин грани содержащие по $N-1$ вершине, каждая из которых имеет ровно $3$ ненулевые координаты?

В лоб. Вектору $\bar x = (x_1,..,x_n), x_j \in E$ можно поставить в соответствие число $a(\bar x) = \sum\limits_{k=0}^n x_k2^{k-1}$, номер вектора - это номер элемента в упорядоченном списке $a (\bar x)$. Причем условие $\sum\limits_k x_k = 3$ не требуется - это работает для любого числа единиц в векторе.

serval в сообщении #489702 писал(а):

Можно ли выписать эти подмножества (или, хотя бы, вершины) не выковыривая их по одной из всего множества сочетаний из $N-1$ по $3$?

Можно и не обязательно для 3-х единиц. Соответствующий код на С++ занимает ровно 7 строк. Чтобы их выписать, нужно Вам выписать все эти векторы, упорядочить их покомпонентно и внимательно на них посмотреть - порядок виден, он не сложный.

serval в сообщении #489702 писал(а):

Нельзя ли использовать, например, то свойство, что все такие вершины принадлежат одной грани, а их радиус-векторы имеют одинаковую длину и значит их кратчайший обход можно совершить по дуге окружности?

Может и можно Хотя говорить "дуга окружности" там не совсем правильно.

[serval]

Цитата:

не обязательно для 3-х единиц

В моей задаче это обязательное условие.

Цитата:

нужно Вам выписать все эти векторы

Все-таки, выписать все. Я надеялся, что существует способ аналитически ограничить это множество.

Цитата:

говорить "дуга окружности" там не совсем правильно

Я хотел сказать, что вдоль такой дуги вершины вписанного многоугольника имеющего эти вершины упорядочены естественным образом. Как бы вычислить порядок их следования?

[Sonic86]

serval в сообщении #489726 писал(а):

е-таки, выписать все. Я надеялся, что существует способ аналитически ограничить это множество.

Нет!!! Не поняли Вы меня.
Чтобы Вам увидеть закономерность в расположении упорядоченных векторов длины $n$ с $k$ единичками, Вам нужно самому взять например $n=6,k=3$ и ручками выписать все эти вектора, посмотреть на них и увидеть закономерность. После того, как Вы ее увидите, Вы сможете выписывать их сами или программно или даже через формулу для любых $n,k$ без полного перебора всех векторов.

serval в сообщении #489726 писал(а):

Я хотел сказать, что вдоль такой дуги вершины вписанного многоугольника имеющего эти вершины упорядочены естественным образом. Как бы вычислить порядок их следования?

Я имел ввиду, что если этот объект и есть, то это не дуга и не многоугольник (это плоские объекты) - нужно их называть соответствующими словами, указывающими на их $N$-мерность.

[serval]

Цитата:

ручками выписать все эти вектора, посмотреть на них и увидеть закономерность.

Я пробовал. Как раз для случая $N=6$ пытался придумать алгоритм пересчета (вроде пересчета всех сочетаний) - и затруднился. Поэтому и обратился с вопросом.

Цитата:

это не дуга

Пусть будет гипердуга
Можно я не буду лепить к каждому термину эту приставку? А то получается коряво. Просто будем понимать, по аналогии с гиперкубом, что все объекты имеют соответствующую размерность.
Но тут я запутался. С одной стороны, через $N-1$ такую точку можно провести прямую, а с другой - все они лежат на дуге окружности. где я ошибся? Или это шутки многомерия?

[Sonic86]

Я в многомерье не рублю - это не ко мне.

serval в сообщении #489737 писал(а):

Я пробовал. Как раз для случая $N=6$ пытался придумать алгоритм пересчета (вроде пересчета всех сочетаний) - и затруднился. Поэтому и обратился с вопросом.

Так там всего 20 векторов, на листочек влазит. Просто выпишите их хоть перебором и отсортируйте. Если так трудно - используйте Excel или возьмите $n=4,k=2$.
Попробуйте выписать из рекуррентных соображений: т.е. вектор длины 6, у него 1-й элемент, либо 1, либо 0 - по этому признаку множество векторов разбивается на 2 класса, причем 1-й класс - это множество всех векторов длины 5 с 2-я единичками (размерность уменьшилась!), а 2-й класс - это множество всех векторов длины 5 с 3-я единичками (размерность уменьшилась снова!). Это соответствует рекуррентной формуле $C_n^k = C_{n-1}^{k-1}+C_{n-1}^k$ - слагаемые - это мощности классов.
Пишите результат здесь. Это просто.

[serval]

Вот эти векторы для $N=6$ в порядке их появления при переборе сочетаний:

$(1,1,1,0,0,0)$
$(1,1,0,1,0,0)$
$(1,0,1,1,0,0)$
$(0,1,1,1,0,0)$
$(1,1,0,0,1,0)$
$(1,0,1,0,1,0)$
$(0,1,1,0,1,0)$
$(1,0,0,1,1,0)$
$(0,1,0,1,1,0)$
$(0,0,1,1,1,0)$
$(1,1,0,0,0,1)$
$(1,0,1,0,0,1)$
$(0,1,1,0,0,1)$
$(1,0,0,1,0,1)$
$(0,1,0,1,0,1)$
$(0,0,1,1,0,1)$
$(1,0,0,0,1,1)$
$(0,1,0,0,1,1)$
$(0,0,1,0,1,1)$
$(0,0,0,1,1,1)$

[ИСН]

Ну? А вопрос в чём? Да, они не лежат на дуге окружности. И на одной прямой не лежат. Приставку "гипер-" можно опустить, но только в том случае, если сами себя понимаете без неё.